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
3、 指令比 k 指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读 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 取指 时间0 1 2 3 4 5 6 7 8 92.23 有一条 5 个功能段的线性动态多功能流水线如图所示，其中 1235
5、 功能段组成加法流水线，145 功能段组成乘法流水线，设每个功能段的延迟时间均相等为 t。用这条流水线计算 F= ，画出流水线时空图，并计算流水线的实际吞吐率、加41()iiiab速比和效率。解：由于该流水线为动态双功能流水线，计算要求先加后乘，因此应先设置加法功能，连续计算出（a 1+b1） 、 （a 2+b2） 、 （a 3+b3） 、 （a 4+b4）四个加法后；再设置乘法功能，而且按(a1+b1)(a2+b2)(a3+b3)(a4+b4)顺序做 3 个乘法。因此可画出该流水线的时空图如图所示，图中 A=a1+b1，B=a 2+b2，C=a 3+b3，D=a 4+b4。由时空图可以看出，
6、在总共 12 个t 的时间内输出 7 个结果，所以有：TP = n/Tn = 7/12t而当用串行方法完成操作时，需要四次加法和三次乘法，完成一次加法需要 4t，完成一次乘法需要 3t，完成该运算总共需要时间为：T0 = 44t+33t = 25t所以 S = T 0/Tn = 2.08E = 有效时空区面积/全部时空区面积= (44t+33t)/(512t) = 0.422.24 有一条 3 个功能段的流水线如下图所示，每个功能段的延迟时间均为t，但是，功能段 S2的输出要返回到它自己的输入端循环执行一次。输入 输出t t t（1）如果每隔一个t 向流水线连续输入任务，这条流水线会发生什么问
7、题？S1 S2 S3S1 S2 S3 S5S4XY Z空间S5S4S3S2S1 1 2 3 4 三一 二一 二一 二1 2 3 4A B C D AB CD (AB)(CD) t7 t13a1b1a2b2a3b3a4b4ABCDABCD时间1 2 3 41 2 3 4三三（2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。（3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：（1）每个任务在段 S2要反馈循环一次，执行时间为 2t，其它各段的执行时间为t，因此应按瓶颈段的执行时间 2t 流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。（2）若连续输入 n 个任务，则流
8、水线的实际吞吐率、加速比和效率分别为：TP = n/（4t +2（n1）t）= n/2（n + 1）t 1/2tS = 4nt/（4t +2（n1）t）= 2n/（n + 1）2E = 4nt/3（4t +2（n1）t）= 2n/3（n + 1）2/3（3）为提高流水线的吞吐率，可重复设置段 S2，并使两个段 S2串连在一起，从而消除瓶颈段 S2，而且各段执行时间相等为 t，流水线的段数为 4。流水线的结构如下图所示。输入 输出t t t t2.25 在一个 5 段的流水线处理机上需经 9t 才能完成一个任务，其预约表为：（1）写出流水线的初始冲突向量。（2）画出流水线任务调度的状态有向图。（
9、3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。（4）按最优调度策略连续输入 8 个任务时，流水线的实际吞吐率是多少?解：（1）根据初始冲突向量的构成方法，对预约表各行中打“”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为 F =1，5，6，8 。由 F 可得到初始冲突向量为：C =（10110001）（2）根据后继冲突向量的递推规则 Cj = SHR（k） （C i）C 0则可得出所有的后继状态，具体有：C0四个后继状态：C 1 =SHR（2） （C 0）C 0 = 10111101 7C2 =SHR（3） （C 0）C 0 = 10110111 C3 =SH
10、R（4） （C 0）C 0 = 10111011 3 2C4 =SHR（7） （C 0）C 0 = 10110001=C0 7 4 7C1二个后继状态：C 5 =SHR（2） （C 1）C 0 = 10111111C6 =SHR（7） （C 1）C 0 = 10110001=C0 7C2二个后继状态：C 7 =SHR（4） （C 2）C 0 = 10111011=C3 3 4 7 2C8 =SHR（7） （C 2）C 0 = 10110001=C0C3二个后继状态：C 9 =SHR（3） （C 3）C 0 = 10110111=C2C10=SHR（7） （C 3）C 0 = 10110001=
11、C0时间 1 2 3 4 5 6 7 8 9流水段S1 S2 S3 S4 S5 延迟 D2 S1 S2 S3S210110001 C010110111 C2 10111101 C110111011 C3 10111111 C5C5一个后继状态：C 11=SHR（7） （C 5）C 0 = 10110001=C0由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。（3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略 平均延迟时间 特别地，从 C0出发的3， （4，3）也是一个（2，2，7） （2+2+7）t/3 = 3.67t 任务调度策略，除第一条有
12、向弧外，第二、三条（2，7） （2+7）t/2 = 4.5t 有向组成一个环路，该调度策略为（4，3） 。从表（3，4，7） （3+4+7）t/3 = 4.67t 中可以得到平均延迟时间最小的调度策略为（4，（3，7） （3+7）t/2 = 5t 3） ，该调度策略则为最优调度策略，相应的最小（4，3，7） （4+3+7）t/3 = 4.67t 平均延迟时间为 3.5t，所以流水线的最大吞吐（4，7） （4+7）t/2 = 5.5t 率为：（7） 7t TP max = 1/（3.5t）= 0.286/t3， （4，3） （4+3）t/2 = 3.5t （4）按最优调度策略3， （4，3）连续输入 8 个任务时，流水线的实际吞吐率为：TP = 8/（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）t = 0.24/t
