第二章练习题参考解答.doc

第 二 章

在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，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)画出指令执行过程的流水线时空图，并计算完成这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指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写—写”相关，k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对R0的写是在程序执行开始后的第八个时钟。k+2指令对R0的写对指令本身是第五个时钟，而k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。
（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 9

有一条5个功能段的线性动态多功能流水线如图所示，其中1→2→3→5功能段组成加法流水线，1→4→5功能段组成乘法流水线，设每个功能段的延迟时间均相等为△t。用这条流水线计算F=，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。
S1
S2
S3
S5
S4
X
Y
Z

解：由于该流水线为动态双功能流水线，计算要求先加后乘，因此应先设置加法功能，连续计算出（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四个加法后；再设置乘法功能，而且按[(a1+b1)×(a2+b2)]×[(a3+b3)×(a4+b4)]顺序做3个乘法。因此可画出该流水线的时空图如图所示，图中A=a1+b1，B=a2+b2，C=a3+b3，D=a4+b4。
空间
S5
S4
S3
S2
S1
1
2
3
4
三
一
二
一
二
一
二
1
2
3
4
A
B
C
D
A·B C·D
(A·B)×(C·D)
t7
t12
a1
b1
a2
b2
a3
b3
a4
b4
A
B
C
D
A·B
C·D
时间
1
2
3
4
1
2
3
4
三
三

由时空图可以看出，在总共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 =
E = 有效时空区面积/全部时空区面积
= (4×4△t+3×3△t)/(5×12△t) =

有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为△t，但是，功能段S2的输出要返回到它自己的输入端循环执行一次。
S1
S2
S3

输入 输出
△t △t △t
（1）如果每隔一个△t向流水线连续输入任务，这条流水线会发生什么问题
（2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。
（3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。
解：（1）每个任务在段S2要反馈循环一次，执行时间为2Δt，其它各段的执行时间为Δt，因此应按瓶颈段的执行时间2Δt流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。
（2）若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为：
TP = n/（4Δt +2（n–1）Δt）= n/2（n + 1）Δt →1/2Δt
S = 4nΔt/（4Δt +2（n–1）Δt）= 2n/（n + 1）→2
E = 4nΔt/3（4Δt +2（n–1）Δt）= 2n/3（n + 1）→2/3
（3）为提高流水线的吞吐率，可重复设置段S2，并使两个段S2串连在一起，从而消除瓶颈段S2，而且各段执行时间相等为Δt，流水线的段数为4。流水线的结构如下图所示。
S3
S2
S2
S1

输入 输出
△t △t △t △t

在一个5段的流水线处理机上需经9△t才能完成一个任务，其预约表为：
时间 1 2 3 4 5 6 7 8 9
流水段
S1 × ×
S2 × × ×
S3 ×
S4 × ×
S5 × ×
延迟D2 ×

（1）写出流水线的初始冲突向量。
（2）画出流水线任务调度的状态有向图。
（3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。
（4）按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少
解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =｛1，5，6，8｝。由F可得到初始冲突向量为：
C =（）
（2）根据后继冲突向量的递推规则Cj = SHR（k）（Ci）∨C0则可得出所有的后继状态，具体有：
10110001 C0
C0四个后继状态：C1 =SHR（2）（C0）∨C0 = 7
C2 =SHR（3）（C0）∨C0 =
C3 =SHR（4）（C0）∨C0 = 3 2
C4 =SHR（7）（C0）∨C0 = =C0 7 4 7
10111101 C1
10110111 C2
C1二个后继状态：C5 =SHR（2）（C1）∨C0 =
C6 =SHR（7）（C1）∨C0 = =C0 7
C2二个后继状态：C7 =SHR（4）（C2）∨C0 = =C3 3 4 7 2
10111011 C3
10111111 C5
C8 =SHR（7）（C2）∨C0 = =C0
C3二个后继状态：C9 =SHR（3）（C3）∨C0 = =C2
C10=SHR（7）（C3）∨C0 = =C0
C5一个后继状态：C11=SHR（7）（C5）∨C0 = =C0
由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。
（3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。
调度策略 平均延迟时间 特别地，从C0出发的[3，（4，3）]也是一个
（2，2，7） （2+2+7）△t/3 = △t 任务调度策略，除第一条有向弧外，第二、三条
（2，7） （2+7）△t/2 = △t 有向组成一个环路，该调度策略为（4，3）。从表
（3，4，7） （3+4+7）△t/3 = △t 中可以得到平均延迟时间最小的调度策略为（4，
（3，7） （3+7）△t/2 = 5△t 3），该调度策略则为最优调度策略，相应的最小
（4，3，7） （4+3+7）△t/3 = △t 平均延迟时间为△t，所以流水线的最大吞吐
（4，7） （4+7）△t/2 = △t 率为：
（7） 7△t TPmax = 1/（△t）= △t
3，（4，3） （4+3）△t/2 = △t
（4）按最优调度策略[3，（4，3）]连续输入8个任务时，流水线的实际吞吐率为：
TP = 8/[（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）△t] = △t