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

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

2、成这3 条指令共需要多少个时钟周期？解：（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 指令晚一个时钟

3、进入流水线， 则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，因此k+1 指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写写”相关，k+1 指令对 R0 的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对 R0的写是在程序执行开始后的第八个时钟。 k+2 指令对 R0的写对指令本身是第五个时钟，而k+2 指令比 k+1 指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对 R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此 k+2 指令应推迟一个时钟进入流水线，产生了流水线停顿。

4、另外，可分析“先读后写”相关不会产生流水线的停顿。（ 3）由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二和存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3 条指令顺序流动，共需要9 个时钟周期。空间存数K存数K+1存数 K+2 存数运二K+1运二运一K+1运一K+2运一取数K取数K+1取数K+2取数译码K译码K+1译码K+2译码取指K取指K+1取指K+2取指时间01234567891 / 42.23有一条 5 个功能段的线性动态多功能流水线如图所示，其中 12 35 功能段组成加法流水线， 1 4 5 功能段组成乘法流水线，设每个功能段的延迟时间均相等为t 。用这

5、条流水线计算 F= 4( a ib i ) ，画出流水线时空图，并计算流水线的实际吞吐率、加速比i1和效率。XS2S3S5ZY1SS4解：由于该流水线为动态双功能流水线，计算要求先加后乘，因此应先设置加法功能，连续计算出（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四个加法后； 再设置乘法功能， 而且按 (a 1+b1 )(a 2 +b2) (a 3+b3) (a 4+b4) 顺序做 3 个乘法。因此可画出该流水线的时空图如图所示，图中 A=a1+b1， B=a2+b2， C=a3+b3，D=a4+b4。空间ABCDABCD(AB)(CD)S51234一二三S4一二三S3123

6、4S21234S11234一二三t 7t 13时间a1a2a3a4ACA BC Db1b2b3b4BD由时空图可以看出，在总共12 个 t的时间内输出 7个结果，所以有：TP = n/Tn = 7/12 t而当用串行方法完成操作时，需要四次加法和三次乘法，完成一次加法需要4 t ，完成一次乘法需要3 t ，完成该运算总共需要时间为：T0 = 4 4 t+3 3 t = 25 t所以S = T0/Tn = 2.08E =有效时空区面积 / 全部时空区面积= (4 4 t+3 3 t)/(5 12 t) = 0.422.24有一条 3 个功能段的流水线如下图所示，每个功能段的延迟时间均为t ，但是

7、，功能段 S2 的输出要返回到它自己的输入端循环执行一次。S1S23输入S输出 t t t（1）如果每隔一个 t 向流水线连续输入任务，这条流水线会发生什么问题？（2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。2 / 4（3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：（ 1）每个任务在段 S2 要反馈循环一次，执行时间为 2 t ，其它各段的执行时间为 t ，因此应按瓶颈段的执行时间 2 t 流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。（ 2）若连续输入 n 个任务，则流水线的实际吞吐率、加速比和效率分别为：TP = n/（ 4t +2（ n 1） t

8、）= n/2 （n + 1 ） t1/2 tS = 4nt/（4t +2 （ n 1）t ）= 2n/ （ n + 1 ） 2E = 4nt/3 （4t +2 （n1）t ）= 2n/3 （ n + 1） 2/3（ 3）为提高流水线的吞吐率， 可重复设置段 S2，并使两个段 S2 串连在一起，从而消除瓶颈段 S2，而且各段执行时间相等为t ，流水线的段数为 4。流水线的结构如下图所示。S1S223输入SS输出 t t t t2.25 在一个 5 段的流水线处理机上需经9t 才能完成一个任务，其预约表为：时间123456789流水段S1S2S3S4S5（ 1）写出流水线的初始冲突向量。（ 2）画

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

10、1011011110110001 C 000（ 4）32C3 =SHR（ C0） C0 = 101110114（7）000747C =SHR（ C） C = 10110001=C1二个后继状态：5（2）1010110111 C 210111101 C 1CC =SHR（ C） C = 10111111C6（7）1007=SHR（ C） C = 10110001=C3 4722二个后继状态：7（4）203CC =SHR（ C） C = 10111011=C（ 7）C8 =SHR（ C2） C0 = 10110001=C 010111011 C 310111111 C 5C 二个后继状态：（ 3）

11、 C = 10110111=CC =SHR（ C23930（ 7）C10 =SHR（ C3） C0 = 10110001=C 0C5 一个后继状态：（ 7）C11=SHR（ C5） C0 = 10110001=C 03 / 4由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。（ 3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略平均延迟时间特别地，从 C 出发的 3 ，（ 4， 3） 也是一个0（ 2，2， 7）（ 2+2+7） t/3 = 3.67 t任务调度策略，除第一条有向弧外，第二、三条（2，7）（ 2+7） t/2 = 4.5 t有向组成一个环路，该调度策略为（4， 3）。从表（3，4， 7）（ 3+4+7） t/3 = 4.67 t中可以得到平均延迟时间最小的调度策略为（4，（3，7）（ 3+7） t/2 = 5 t3），该调度策略则为最优调度策略，相应的最小（ 4，3， 7）（ 4+3+7） t/3 = 4.67 t平均延迟时间为3.5 t