计算机体系结构习题
一、名词解释
第一章:
计算机组成:指的是计算机系统结构的逻辑实现,包含物理机器中的数据流和控制流的组成以及逻辑设计等。它着眼于物理机器级内各事物的排序方式与控制方式、各部件的功能以及各部件之间的联系。
计算机实现:指的是计算机组成的物理实现,包括处理机、主存等部件的物理结构,器件的集成度和速度,模块、插件、底板的划分与连接,信号传输,电源、冷却及整机装配技术等。它着眼于器件技术和微组装技术,其中器件技术在实现技术中起主导作用。
程序的局部性原理:指程序执行时所访问的存储器地址不是随机分布的,而是相对簇聚。常用的经验规则:程序执行时间的90%都是在执行程序中的10%的代码。数据访问也具有局部性。
第二章:
RISC:即精简指令集计算机,它是尽可能地把指令系统简化,不仅指令的条数少,而且指令的功能比较简单。(P36页)
CISC:即复杂指令集计算机,它是增强指令功能,把越来越多的功能交由硬件实现,指令的数量也越来越多。(P36页)
寻址方式:指指令系统中如何形成所要访问的数据的地址。
第三章:
流水线技术:(P53页)把一个重复的过程分解为若干个子过程(相当于上面的工序),每个子过程由专门的功能部件来实现,把多个处理过程在时间上错开,依次通过各功能段,这样,每个子过程就可以与其他的子过程并行进行,这就是流水线技术。
线性流水线:(见P57页)线性流水线是指各段串行连接、没有反馈回路的流水线。数据通过流水线中的各段时,每个段最多只流过一次。
非线性流水线:(见P57页)非线性流水线是指各段除了有串行的连接外,还有反馈回路的流水线。
数据相关:(见P73页)考虑两条指令i和j,i在j的前面,如果下述条件之一成立,则称指令j与指令i数据相关:(1)指令j使用指令i产生的结果;(2)指令j与指令k数据相关,而指令k又与指令i数据相关。
系统级流水线(P55)是把多个处理机串行连接起来,对同一数据流进行处理,,每个处理机完成整个任务中的一部分。前一台处理机的输出结果存入存储器中,作为后一台处理机的输入。这种流水线又称宏流水线。
9、单功能流水线(P55):是指流水线各段之间的连接固定不变、只能完成一种固定功能的流水线。
10、多功能流水线(P55):是指各段可以进行不同的连接,以实现不同功能的流水线。
静态流水线(P55):是指在同一时间内,多功能流水线中的各段只能按同一种功能的连接方式工作的流水线
动态流水线(P55):是指在同一时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能的流水线。
第四章:
向量的横向处理方式:在横向处理方式中,是按行的方式从左到右横向的进行计算的。
向量的纵向处理方式:在纵向处理方式中,向量计算是按列的方式从上到下纵向的进行的。也就是说,是将整个向量按相同的运算处理完之后,再去进行别的运算。
向量的纵横处理方式:纵横处理方式又称为分组处理方式,是横向处理方式和纵向处理方式的一种结合。它是把向量分成若干组,组内按纵向方式处理,依次处理各组。
向量的分段开采技术:(见P102页)当向量的长度大于向量寄存器的长度时,必须把长向量分成固定的段,然后循环分段处理,每一次循环只处理一个向量段,这种技术称为分段开采技术。
向量流水线链接:(P100页):是指具有先写后读相关的两条指令,在不出现功能部件冲突和其他向量寄存器冲突的情况下,可以把功能部件链接起来进行流水处理,以达到加快执行的目的。
第五章及第六章:
1、指令级并行:(P112页)是指指令之间存在的一种并行性,利用它,计算机可以并行执行两条或两条以上的指令。
2、循环展开:(P156)是指把循环体的代码复制多次并按顺序排放,然后相应地调整循环的结束条件。通过循环展开,多个循环迭代的代码可以合到一起调度,给编译器进行指令调度带来了更大的空间,而且还能够消除中间的分支指令和循环控制指令引起的开销。
第七章:
Cache的全相连映像(P194):是指主存中的任意一块可以被放置到Cache中的任意一个位置。Cache的组相连映像(P195):Cache被等分为若干组,每组由若干个块构成,主存中的每一块可以被放置到Cache中唯一的一个组中任何一个位置
第九章:
自适应寻径:(P293)通信的通路每一次是根据资源或者网络的情况来进行选择,这样可以避开拥挤的或者有故障的节点,从而使网络的利用率得到改进。
确定寻径方法:(P293)通信路径完全由源节点地址和目的地址来决定,也就是说,寻径路径是预先唯一确定好了的,而与网络的状况无关。
存储转发:(P288)它是最简单的分组交换方式,在这种方式中,包是信息传递的基本单位,包从源节点经过一系列中间节点到达目的节点。存储转发要求所经过的每个中间节点都要设置一个包缓冲器,用于保存所传递的包。当一个包到达某个中间节点时,该节点先把这个包全部存储起来,然后再出口链路可用、而且下一个节点的包缓冲器也可用的情况下,传递给下一个节点。
虫蚀方式:(P289)它把信息包“切割”成更小的单位——“片”,而且使信息包中各片的传送按流水方式进行,所以不仅可以减少节点中缓冲器的容量,而且还能缩短传送延迟的时间。细粒度多线程技术:(P326)在每条指令之间都能进行线程的切换,从而使得多个线程可以交替执行,通常以时间片轮转的方法是先这样的交替执行,在轮转的过程中跳过处于停顿的线程。
粗粒度多线程技术:(P327 )它是针对细粒度多线程的缺点而提出的。粗粒度多线程之间的切换只发生在时间较长的停顿(例如第二季Cache不命中)出现的时候。这一改变使得粗粒度多线程不需要像细粒度多线程那样自由的切换,减少了切换次数。并且也不太会降低单个线程的执行速度,这是因为只有当线程发生时间较长的停顿时才会执行其他线程的指令。
二、简答题
共享存储器通信与消息传递通信机制各有哪些主要的优点?(P301)
答:共享存储器通信优点:
1、与常用的对称式多处理机使用的通信机制兼容;
2、当处理机之间通信方式复杂或在执行过程中动态变化时,采用共享存储器通信,
编程容易,同时在简化编译器设计方面也占有优势;
3、采用大家所熟悉的共享存储器模型开发应用程序,而把重点放在解决对性能影
响较大的数据访问上;
4、当通信数据量较小时,通信开销较小,带宽利用较好;
5、可以通过采用Cache 技术来减少远程通信的频度。
消息传递通信优点:
1、硬件更简单;
2、通信时显式的,因此更容易搞清楚何时发生通信以及通信开销是多少;
3、显式通信可以让编程者重点注意并行计算的主要通信开销,使之有可能开发出
结构更好、性能更高的并行程序;
4、同步很自然地与发送消息相关联,能减少不当的同步带来错误的可能性。
简述流水线技术的特点。(P54)
答:流水技术有以下特点:
1、流水线把一个处理过程分解为若干个子过程,每个子过程由一个专门的功能部
件来实现。因此,流水线实际上是把一个大的处理功能部件分解为多个独立的功能
部件,并依靠它们的并行工作来提高吞吐率。
2、流水线中各段的时间应尽可能相等,否则将引起流水线堵塞和断流。
3、流水线每一个功能部件的前面都要有一个缓冲寄存器,称为流水寄存器。
4、流水技术适合于大量重复的时序过程,只有在输入端不断地提供任务,才能充
分发挥流水线的效率。
5、流水线需要有通过时间和排空时间。在这两个时间段中,流水线都不是满负荷
工作。
可采用哪些方法来提高向量处理机的性能(P98)
答:可采用多种方法:
1、设置多个功能部件,使它们并行工作;
2、采用链接技术,加快一串向量指令的执行;
3、采用循环开采技术,加快循环的处理;
4、采用多处理机系统,进一步提高性能。
在某个给定系统上运行某个程序所花费时间是1000000个周期。如果该系统获得的CPI值为40,问:运行该程序时执行了多少条指令?
答:
CPI=运行程序所用的周期数/执行的指令数
可得出指令数=1000000/40=25000
即运行该程序时执行了25000条指令
区别不同指令集结构的主要因素是什么?根据这个主要因素可将指令集结构分为哪3类?
答:区别不同指令集结构的主要因素是CPU中用来存储操作数的存储单元,存储单元有三种:堆栈、累加器、通用寄存器。据此将指令系统结构分为3类:堆栈结构、累加器结
构和通用寄存器结构。
简述Tomasulo算法的基本思想。
答:核心思想是:①记录和检测指令相关,操作数一旦就绪就立即执行,把发生RAW 冲突的可能性减小到最少;②通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现,它保存等待流出和正在流出指令所需要的操作数。
基本思想:只要操作数有效,就将其取到保留站,避免指令流出时才到寄存器中取数据,这就使得即将执行的指令从相应的保留站中取得操作数,而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而,对于连续的寄存器写,只有最后一个才真正更新寄存器中的内容。一条指令流出时,存放操作数的寄存器名被换成为对应于该寄存器保留站的名称(编号)。
同步总线和异步总线各有什么优缺点?
答:
同步总线:同步总线的控制线有一个时钟,所有设备通过这个时钟进行同步。
优点是:总线速度快、成本低,因为它不需要设备之间互相确定时序的逻辑;
其缺点:1)由于时钟通过长距离传输后会扭曲,所以不能用于长距离的连接
2)总线上的设备都必须以相同的时钟频率工作。
异步总线:异步总线上的设备之间没有统一的时钟,各设备有自己的定时,总线上的发送设备和接收设备采用握手协议。
优点:由于不使用统一的时钟来定时,可以连接各种不同的设备设备,传输的距离长,容易适应更广泛的设备类型,扩充总线时不用担心时钟时序和时钟
同步问题。
缺点:传输时,异步总线需要额外的开销,而且速度较慢。。
试比较三种通道(字节多路通道、选择通道、数组多路通道)的优缺点及适用场合。
答:
字节多路通道:一种简单的共享通道,主要为多台低速或中速的外围设备服务。设备一般是以字节为宽度进行I/O的,以字节交叉的方式分时轮流为这些设备
服务的,其相邻的两次传送之间的等待时间较长,
选择通道:这个通道的速度较高,为多台高速外围设备(如磁盘存储器等)服务的。
是按照一定的规则对要服务的设备进行选择,处理完后,再重新选择要
服务的设备。但在一段时间内只被一台高速外设独占使用。
数组多路通道:适于为高速设备服务。采用字节多路通道和选择通道的特点,它是以数据块为单位,传送完固定长度的数据块后,重新选择其它的设备,分时
轮流地为这些设备服务的。
什么是多处理机Cache一致性问题?给出解决一致性的监听协议和目录协议的工作原理。答:
多处理机的cache一致性问题:是指如果允许共享数据进入Cache,就可能出现多个处理器的Cache中都有同意存储块的副本,当其中某个处理器对其Cache中的数据进行修改时,就会使得Cache中的数据与其他Cache中的数据不一致,这就是多处理机的Cache一致性问题。
监听协议的工作原理:每个Cache除了包含物理存储器中块的数据拷贝之外,也保存着
各个块的共享状态信息。Cache通常连在共享存储器的总线上,当某个Cache需要访问存储器时,它会把请求放到总线上广播出去,其他各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有,就进行相应的操作。
目录协议的工作原理:采用一个集中的数据结构——目录。对于存储器中的每一个可以调入Cache的数据块,在目录中设置一条目录项,用于记录该块的状态以及哪些Cache中有副本等相关信息。目录协议根据该项目中的信息以及当前要进行的访问操作,依次对相应的Cache发送控制消息,并完成对目录项信息的修改。此外,还要向请求处理器发送响应信息。
评价互连网络性能的主要参数有哪些?
答:时延和带宽是用来评估互连网络性能的两个基本指标;其中包括:
1、通信时延;
2、网络时延;
3、端口带宽;
4、聚集带宽;
5、等分带宽。
采用动态分支预测技术的目的是什么?在所采用的方法中,需要解决哪些关键问题?
答:目的有两个:分支预测是否成功和尽快找到分支目标地址(或指令),从而避免控制相关造成流水线停顿。
需要解决的两个关键问题:如何记录分支的历史信息;如何根据这些信息来预测分支的去向,甚至提前取出分支目标地址(或指令)。
记分牌算法中,记分牌中记录的信息由哪三部份构成?
答:记分牌中的记录信息由下面三个部分构成:
(1)指令状态表:记录正在执行的各条记录已经进入到了哪一段
(2)功能部件状态表:记录各个功能部件的状态,每个功能部件都有一项,其由9个字段组成:Busy Op Fi Fj Fk Qj Qk Rj Rk
(3)结果寄存器状态表Result:每个寄存器在该表中都有一项,用于指出哪个功能部件(编号)将结果写入该寄存器。如果当前正在运行的指令都不以它为目的
寄存器,则其相应项为”no“。Result各项的初值为”no”(全0).
三、应用题
1、设有某台计算机是由高速缓冲存储器Cache与主存构成二级存储器系统,其中Cache的存取周期T1=50nS,主存的存取周期T2=400nS,访问Cache的命中率为98%。试问该存储器系统的等效访存时间T是多少?访问效率e是多少?
解:已知T1=50nS,T2=400nS,命中率H=0.98,使用简单算式得:
T=HT1+(1-H )T2=0.98×50+(1-0.98)×400=57nS
e=T1/T=50/57≈0.877
2、设有一个磁盘,其平均寻道时间为5ms,传输率为10MBps,控制开销为2ms,驱动电机的转速为7200r/min,求读/写一个512字节的扇区所用的时间。
解:根据题意:平均寻道时间为5ms,
传送512字节数据的传输时间为512/10=51.2μs,
旋转延迟时间为60/7200×0.5=4.17ms,
控制延迟时间为2ms ,
则读/写一个512字节的扇区所用的时间为: 5ms+51.2μs+4.17ms+2ms=11.22ms。
3、若在整个测试程序的执行时间中,求浮点数平方根FPSQR 的操作占10%。现有两种改进方案:一种是采用FPSQR 硬件,使其速度加快到10倍;另一种是使所有浮点数指令FP 速度加快到4倍,并设FP 指令占整个程序执行时间的40%。请比较两种方案的优劣。 解:硬件方案:F e =0.1,S e =10,则
FP 加速方案:F e =0.4,S e =4,则
由结果比较可知,FP 加速方案更优。需注意结论的前提是程序量的40%为FP 指令。
4、设有两台机器A 和B ,对条件转移采用不同方法。CPUA 采用比较指令和条件转移指令处理方法,实现一次条件转移需执行两条指令,条件转移指令和比较指令各占执行指令总数的15%。CPUB 采用比较和条件转移指令合一方法,实现一次条件转移只需执行一条指令。若规定两台机器执行条件转移指令需2个时钟周期,其他指令只需1个时钟周期。CPUB 的时钟周期比CPUA 慢20%。请比较:
(1)CPUA 和CPUB 哪个工作速度更快?
(2)若CPUB 的时钟周期只比CPUA 慢10%,哪个CPU 工作速度更快? 解:(1)计算机器A CPIA =0.15×2+0.85×1=1.15
CPUA 时间=ICA ×CPIA ×TA =1.15TA ×ICA
ICA 是CPUA 的指令条数。因CPUB 无比较指令ICB =0.85ICA 使CPUB 的转移
指令所占比例为15%÷85%=17.65%≈18%
计算机器B CPIB =0.18×2+0.82×1=1.18
又因CPUB 的TB 比CPUA 的TA 慢20%,所以TB =1.2TA
CPUB 时间=ICB ×CPIB ×TB =1.1 TA ×ICA
比较可知, CPUA 时间<CPUB 时间,故CPUA 比CPUB 工作速度快。
(2)此时有TB =1.1TA ,据前结论
CPUA 时间=1.15TA ×ICA
CPUB 时间=0.85ICA ×1.18×1.1TA =1.1 TA ×ICA
()43.17
.01
4
4
.04.011
n ≈=
+-=
S ()10.191
.01
10
1
.01.011
n ≈=
+
-=
S
因CPUB时间<CPUA时间,故CPUB的工作速度更快些。
5、假设一个网络的频宽为10Mb/S,发送方开销为230us,接收方开销分别为270us。如果两台机器相距100米,现在要发送一个1000字节的消息给另一台机器,试计算总时延。如果两台机器相距1000公里,那么总时延为多大?光的速度为299792.5KM/S,信号在导体中传递速度大约是光速的50%。
解:光的速度为299792.5KM/S,信号在导体中传递速度大约是光速的50%。
相距100米时总时延为:
相距1000公里时的总时延为:
6、一条是有5个功能级的流水线,每级的时间均为△t,反映各运行时续的预约表如下图
(1)根据预约表画出相应的流水线线框图(包括各反馈线)
(2)写出全部禁止向量和初始冲突向量。
(3)画出流水线的调度状态图。
(4)求出流水线的最小平均时间间隔?
(5)求出此流水线的最大吞吐率?
解:
(1)根据预约表画出相应的流水线线框图(包括各反馈线)
(2)写出全部禁止向量和初始冲突向量。
解:禁止向量F(1,3,4,8) 初始冲突向量C=(10001101)
(3)画出流水线的调度状态图。
(4)求出流水线的最小平均时间间隔?
解:有其调度状态图可计算得其最小平均时间间隔为:
T=(2△t+5△t)/2=3.5△t
(5)求出此流水线的最大吞吐率?
解:根据公式TP=n/T k 可得:TP=△t/3.5△t≈0.2857
7、若有一静态多功能流水线分5段,如下图所示:其中乘法流水线由1、2、3、5段组成,加法流水线由1、4、5段组成,每段的通过时间如图中所示。
需要处理的计算任务为:a1?b1 + a2?b2 + a3?b3+ a4?b4 。
试指出并说明在流水线方式下所涉及的运算的最佳输入次序,给出在该次序下该计算任务需要多少时间完成,以及与非流水线顺序执行方式相比的加速比。
解:运算次序:
首先四个乘法,即a1?b1 ,a2?b2 ,a3?b3,a4?b4
其次两个加法,即(a1?b1) + (a2?b2),(a3?b3) + (a4?b4)
最后一个加法,即(a1?b1 +a2?b2) + (a3?b3 + a4?b4)
流水线执行方式:
首先四个乘法完成时间= 4?2t + (4-1) ?1t = 11t
其次两个加法完成时间= 3?t + (2-1) ?t = 4t
最后一个加法完成时间= 3t
一共完成时间= 18t
顺序执行方式:
乘法完成时间= 4?(t + t + 2t+ t) = 20t
加法完成时间= 3?(t + t + t) = 9t
一共完成时间= 29t
因此,加速比=29t/18t≈1.61
8、设FP指令的比例为25%,其中,FPSQR战全部指令的比例为2%,FP操作的CPI为4%,FPSQR操作的CPI为20,其他指令的平均CPI为1.4%。现有两种改进方案,第一种是把FPSQR的CPI减至2,第二种是把所有的FP操作的CPI减至2,是比较两种方案对系统性能的提高程度。(见教材P9)
解:
改进前指令的平均CPI:
(1)采用第一种方案
FPSQR操作的CPI由CPI FPSQR=20减至CPI’FPSQR=2,则整个系统的指令平均时钟周期数为:
CPI1=CPI―(CPI FPSQR―CPI’FPSQR)×2%=2―(20―2)×2%=1.64
(2)采用第二种方案
所有FP操作的CPI由CPI FP=4减至CPI’FP=2,则整个系统的指令平均时钟周期数为:CPI2=CPI―(CPI FP―CPI’FP)×25%=2―(4―2)×25%=1.5
所以,从降低整个系统的指令平均时钟周期数的程度来看,第二种方案优于第一种方案。
9、有一个流水线由4段组成,其中每当流经第三段时,总要在该段循环一次,然后才能流到第四段。如果每段经过一次所需要的时间都是⊿t:
1)当在流水线的输入端连续地每⊿t 时间输入一个任务时,该流水线会发生什么情况? 2)此流水线的最大吞吐率为多少?如果每2⊿t 输入一个任务,连续处理10个任务时的实际吞吐率和效率是多少?
3)当每段时间不变时,如何提高该流水线的吞吐率?连续处理10个任务时,其吞吐率提高到多少?(见教材91) 解:(1)在第三段会发生流水线阻塞情况。
(2)
54.35%
92
5045TP E 2310
T n
Tp 23T 21TP pipeline
pipeline max ≈=??=??==?=?=t t
t t
(3)重复设置部件
t
t
??=??==75
1410
T n
TP pipeline
吞吐率提高倍数=
t
t ??2310
75=1.64
10、将计算机系统中某一功能的处理速度加快10倍,但该功能的处理时间仅为整个系统运行时间的40%,则采用此增强功能方法后,能使整个系统的性能提高多少? 解:
由题可知: 可改进比例 = 40% = 0.4 部件加速比 = 10 根据Amdahl 定律可知:
()5625.110
4
.04.011
系统加速比=+-=
采用此增强功能方法后,能使整个系统的性能提高到原来的1.5625倍。
11、有一条静态多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第3段的时间为2△t ,其余各段的时间均为△t ,而且流水线的输出可以直接返回输入端或 暂存于相应的流水寄存器中。现要在该流水线上计算 ,画出其时空图,并计算其吞吐率、加速比和效率。
解:
首先,应选择适合于流水线工作的算法。对于本题,应先计算A 1+B 1、A 2+B 2、A 3+B 3和A 4+B 4;再计算(A 1+B 1) ×(A 2+B 2)和(A 3+B 3) ×(A 4+B 4);然后求总的结果。
段
t
? 14
乘法
加法
)(41
i i i B A
+∏
=
其次,画出完成该计算的时空图,如图所示,图中阴影部分表示该段在工作。
由图可见,它在18个△t 时间中,给出了7个结果。所以吞吐率为:
t
TP ?=
817
如果不用流水线,由于一次求积需3△t ,一次求和需5△t ,则产生上述7个结果共需(4×5+3×3)△t =29△t 。所以加速比为:
该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得:
12、假设有一条长流水线,仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期,缓冲不命中的开销为3个时钟周期。假设:命中率为90%,预测精度为90%,分支频率为15%,没有分支的基本CPI 为1。
(1) 求程序执行的CPI 。
(2) 相对于采用固定的2个时钟周期延迟的分支处理,哪种方法程序执行速度更快? 解:
(1)程序执行的CPI = 没有分支的基本CPI (1) + 分支带来的额外开销
分支带来的额外开销是指在分支指令中,缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。
分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10%没命中×3)= 0.099
所以,程序执行的CPI = 1 + 0.099 = 1.099
(2)采用固定的2 个时钟周延迟的分支处理CPI = 1 + 15%×2 = 1.3 由(1)(2)可知分支目标缓冲方法执行速度快。
13、假设分支目标缓冲的命中率为90%,程序中无条件转移指令的比例为5%,没有无条件转移指令的程序CPI 值为1。假设分支目标缓冲中包含分支目标指令,允许无条件转移指令进入分支目标缓冲,则程序的CPI 值为多少? 解:设每条无条件转移指令的延迟为x ,则有:
1+5%×x =1.1
时间
段
输 入
A 1
B 1 A 2 B 2 A 3 B 3 A 4 B 4
A B C
D
A ×
B
C ×D
61
.18192=??=
t
t S 22
3.018
53
354=??+?=
E
x =2
当分支目标缓冲命中时,无条件转移指令的延迟为0。 所以 程序的CPI = 1 + 2 × 5% ×(1 -90%) =1.01
14、设指令流水线由取指令、分析指令和执行指令3个部件构成,每个部件经过的时间为△t ,连续流入12条指令。分别画出标量流水处理机以及ILP 均为4的超标量处理机、超长指令字处理机、超流水处理机的时空图,并分别计算它们相对于标量流水处理机的加速比。 解:标量流水处理机的时空图:
执行完12条指令需T 1=14△t 。
超标量流水处理机与超长指令字处理机的时空图:
超标量流水处理机中,每一个时钟周期同时启动4条指令。执行完12条指令需T 2=5△t ,相对于标量流水处理机的加速比为:
8.2514212=?Λ==t t T T S
超长指令字处理机中,每4条指令组成一条长指令,共形成3条长指令。执行完12条
指令需T 3=5△t ,相对于标量流水处理机的加速比为:
8.2514313=?Λ==t
t T T S
超流水处理机的时空图:
超标量处理机时空图
时间
超长指令字处理机时空图
超流水处理机中,每1/4个时钟周期启动一条指令。执行完12条指令需T 4=5.75△t ,相对于标量流水处理机的加速比为:
435.2.75514414=?Λ==t t T T S
15、假设对指令Cache 的访问占全部访问的75%;而对数据Cache 的访问占全部访问的25%。Cache 的命中时间为1个时钟周期,失效开销为50 个时钟周期,在混合Cache 中一次load 或store 操作访问Cache 的命中时间都要增加一个时钟周期,32KB 的指令Cache 的失效率为0.39%,32KB 的数据Cache 的失效率为4.82%,64KB 的混合Cache 的失效率为1.35%。又假设采用写直达策略,且有一个写缓冲器,并且忽略写缓冲器引起的等待。试问指令Cache 和数据Cache 容量均为32KB 的分离Cache 和容量为64KB 的混合Cache 相比,哪种Cache 的失效率更低?两种情况下平均访存时间各是多少? 解:(1)根据题意,约75%的访存为取指令。
因此,分离Cache 的总体失效率为:(75%×0.15%)+(25%×3.77%)=1.055%; 容量为128KB 的混合Cache 的失效率略低一些,只有0.95%。 (2)平均访存时间公式可以分为指令访问和数据访问两部分:
平均访存时间=指令所占的百分比×(读命中时间+读失效率×失效开销)+
数据所占的百分比×(数据命中时间+数据失效率×失效开销)
所以,两种结构的平均访存时间分别为:
分离Cache 的平均访存时间=75%×(1+0.15%×50)+25%×(1+3.77%×50) =(75%×1.075)+(25%×2.885)=1.5275
混合Cache 的平均访存时间=75%×(1+0.95%×50)+25%×(1+1+0.95%×50) =(75%×1.475)+(25%×2.475)=1.725 因此,尽管分离Cache 的实际失效率比混合Cache 的高,但其平均访存时间反而较低。分离Cache 提供了两个端口,消除了结构相关。
16、设某个字节多路通道的设备选择时间Ts 为9.8μs ,传送一个字节的数据所需的时间T D 为0.2μs 。若某种低速外设每隔500μs 发出一次传送请求,那么,该通道最多可连接多少台这种外设?
解:字节多路通道的最大流量为:D
S byte T T f +=-1
m ax
字节多路通道的实际流量为:∑==p
i i byte f f 1
其中,p 为通道连接的外设台数,f i 为外设i 的数据传输速率。因为连接的是同样的外设,所以f 1=f 2=…=f p =f ,故有f byte =pf 。 通道流量匹配的要求有:f max-byte ≥f byte 即有:
pf T T D S ≥+1;可得:f
T T p D S )(1
+≤
已知Ts = 9.8μs ,T D = 0.2μs ,1/f = 500μs ,可求出通道最多可连接的设备台数为:
50)2.08.9(500)(1
=+=+≤
s
s f T T p D S μμ
17、一个具有32台处理机的系统,对远程存储器访问时间是2000ns 。除了通信以外,假设计算中的访问均命中局部存储器。当发出一个远程请求时,本地处理机挂起。处理机的时钟周期时间是10ns ,假设指令基本的CPI 为1.0(设所有访存均命中Cache )。对于下述两种情况:
(1) 没有远程访问;
(2) 0.5%的指令需要远程访问。 试问前者比后者快多少?
解:已知远程访问率 p = 0.5%,远程访问时间 t = 2000ns ,时钟周期 T = 10ns 远程访问开销 C = t/T = 2000ns/10ns = 200(时钟周期数) 有 0.5%远程访问的机器的实际 CPI 2 为:
CPI 2 = CPI 1 + p ×C = 1.0 + 0.5%×200 = 2.0 只有局部访问的机器的基本 CPI 1 = 1.0 CPI 2/ CPI 1 = 2.0/1.0 = 2(倍)
因此,没有远程访问状态下的机器速度是有0.5% 远程访问的机器速度的2 倍。
18、设某个数组多路通道设备选择时间TS 为1μs,传送一个字节数据所需的时间TD 为1μs,一次传送定长数据块的大小k 为512 B 。现有8台外设的数据传输速率分别如表6.3所示,问哪些外设可连接到该通道上正常工作?
解
19、假设在4500次访存中,第一级Cache 不命中150次,第二级Cache 不命中70次。试问:在这种情况下,该Cache 系统的局部不命中率和全局不命中率各是多少? 解:
局部不命中率 = 该级Cache 的不命中次数/到达该级Cache 的访存次数 不命中率L1 = 150/4500 = 0.0333,不命中率L2 = 70/150 = 0.467, 全局不命中率L1 = 不命中率L1 = 0.0333,
全局不命中率L2 = 不命中率L1×不命中率L2 = 0.0333×0.46750 = 0.0156
25、一条是有4个功能级的流水线,每级的时间均为△t ,反映各运行时续的预
约表如下图 1 2 3 4 5 6 7 8 S1 ×
×○
×
○
S2 × ×○
S3 ×
× ○
×○ S4
×
○
(1) 根据预约表画出相应的流水线线框图(包括各反馈线)
(2) 写出全部禁止向量和初始冲突向量。
S2 S3 S4
S1
前 馈
输出
输入
反馈
解:禁止向量F(1,3,4,6) 初始冲突向量C=(101101) (3)画出流水线的调度状态图。
(4)求出流水线的最小平均时间间隔?
解:有其调度状态图可计算得其最小平均时间间隔为: T=(2△t+5△t)/2=3.5△t
(5)求出此流水线的最大吞吐率?
解:根据公式TP=n/T
k 可得:TP=△t/3.5△t≈0.2857
101101
101111
2
5
5