计算机体系结构练习题参考解答

1、2.13在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVEADD?口MUL®作分别需要2个、3个和4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k：k+1:k+2：MOVER1,R0MULR0,R2,R1ADDR0,R2,R3;R1(R0);Rg(R2)X(R1);Rg(R2)+(R3)(1)就程序本身而言，可能有哪几种数据相关？(2)在程序实际执行过程中，哪几种数据相关会引起流水线停顿？(3)画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？解

2、：(1)就程序本身而言，可能有三种数据相关。若3条指令顺序流动，则k指令对R1寄存器的写与k+1指令对R1寄存器的读形成的“先写后读”相关。若3条指令异步流动，则k指令对R0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关，k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写一写”相关。(2)在程序实际执行过程中，二种数据相关会引起流水线停顿。一是“先写后读”相关，k指令对R1的写在程序执行开始后的第四个时钟；k+1指令对R1的读对指令本身是第三个时钟，但k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，

3、因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写一写”相关，k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对R0的写是在程序执行开始后的第八个时钟。k+2指令对R0的写对指令本身是第五个时钟，而k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。(3)由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、

4、运二和存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需要9个时钟周期。“空间存数K存数K+1存数K+2存数运二K+1运二运一K+1运一K+2运-取数K取数K+1取数K+2取数译码K译码K+1译码K+2译码取指1K取指7K+1取指K+2取指叼'01234567f392.23有一条5个功能段的线性动态多功能流水线如图所示，其中1一2一3一5功能段组成加法流水线，1一4一5功能段组成乘法流水线，设每个功能段的延迟时间均相等为t。用这条流水线计算F=4(ajbi),画出流水线时空图，并计算流水线的实际吞吐率、加速比i1和效率。XYZ解：由于该流水线为动态双功能流

5、水线，计算要求先加后乘，因此应先设置加法功能，连续计算出(a1+b1)、(a2+b2)、(aa+ba)>(a4+b4)四个加法后；再设置乘法功能，而且按(a1+b)x(a2+b)x(a3+b3)x(a4+b4)顺序做3个乘法。因此可画出该流水线的时空图如图所示，图中A=a+b，B=a+b2,C=a+b3,D=a+b4。空间一S5S4S3S2S11ftta13a3abb2b3blA-B22323434ABCDA-BC-DABC-D(AB)X(C-D)t13时间11_由时空图可以看出，在总共的时间内输出7个结果，所以有:而当用串行方法完成操作时，3At,完成该运算总共需要时间为:TP=n/T

6、n=7/12At需要四次加法和三次乘法，完成一次加法需要4At,完成一次乘法需要所以To=4X4At+3X3At=25AtS=To/Tn=2.08E=有效时空区面积/全部时空区面积=(4X4At+3X3At)/(5X12At)=0.422.24有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为t,但是,功能段&的输出要返回到它自己的输入端循环执行一次。输入一m公输出tAtAt(1)如果每隔一个t向流水线连续输入任务，这条流水线会发生什么问题?(2)求这条流水线能够正常工作的实际吞吐率、加速比和效率。(3)可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：(1)每个

7、任务在段&要反馈循环一次，执行时间为2At,其它各段的执行时间为At,因此应按瓶颈段的执行时间2At流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。(2)若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为：TP=n/(4At+2(n-1)At)=n/2(n+1)At-1/2AtS=4nAt/(4At+2(n-1)At)=2n/(n+1)一2E=4nAt/3(4At+2(n-1)At)=2n/3(n+1)2/3(3)为提高流水线的吞吐率，可重复设置段S2,并使两个段S2串连在一起，从而消除瓶颈段S2,而且各段执行时间相等为At,流水线的段数为4。流水线的结构如下图所示。输

8、入1S1"臼工一"输出tAtAtAt(1)写出流水线的初始冲突向量。(2)画出流水线任务调度的状态有向图。(3)求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。(4)按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少？解：(1)根据初始冲突向量的构成方法，对预约表各行中打“x”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F=1,5,6,8。由F可得到初始冲突向量为：C=(10110001)(2)根据后继冲突向量的递推规则C=SHRk)(C)VG则可得出所有的后继状态，具体有：G四个后继状态：G=SHR(G)VCo=10111101C2=

9、SHR3)(Q)VQ=10110111C3=SHR4)(Co)VC0=10111011G=SHR(G)VC0=10110001=C0C二个后继状态：C5=SHR(C)VCo=10111111C6=SHR7)(C)VC0=10110001=00G二个后继状态：G=SHR(G)VCo=10111011=03Q=SHR(02)VG=10110001=00G二个后继状态：Q=SHR(Q)VCo=10110111=02Co=ShR7)(G)Vco=10110001=00G一个后继状态：C1=SHR7)(C5)VG=10110001=00由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。(3)由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。8个任务时，流水线的实际吞吐率为:调度策略平均延迟时间(2,2,7)(2+2+7)At/3=3.67At(2,7)(2+7)At/2=4.5At(3,4,7)(3+4+7)At/3=4.67At(3,7)(3+7)At/2=5At(4,3,7)(4+3+7)At/3=4.67At(4,7)(4+7)At/2=5.5At(7)7t3,(4,3)(4+3)At/2=3.5At(4)按最优调度策略3,(4,3)连续输入特别地，从Co出发的3,(4,3)也是一个任务调度策略，除第一条有向弧