第05章流水线课后习题

第5章 课后习题 1．填空题

(1) 衡量流水线性能的主要指标有 、 和 。 (2) 指令乱序流动可能造成 、 、 三种数据相关。 (3) 解决数据相关主要有 法和 法。 (4) 超标量处理机开发的是 并行性，而超流水线处理机开发的是 并行性。

(1). 吞吐率、加速比、效率 (2). 先写后读、先读后写、写写 (3). 推后分析、设置专用路径 (4). 空间、时间

2．假设一条指令的执行过程分为"取指令"、"分析"和"执行"三段，每一段的时间分别为△t、2△t和3△t。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。

(1) 顺序执行方式。 (2) 仅"取指令"和"执行"重叠。 (3) "取指令"、"分析"和"执行"重叠。 第2题 (1) 顺序执行时每条指令用时=△t+2△t+3△t=6△t， 因此n条指令所需要的时间=6n*△t (2) 第一条指令完成需要时间=△t+2△t+3△t=6△t，根据题义，下一条指令的"取指令"与上一条指令"执行"的最后一个△t重叠。因此，自从第一条指令完成后，每隔4△t完成一条指令。所以余下的n-1条指令用时(n-1)*4△t.

所以，n条指令所需要的时间=6△t+(n-1)*4△t=2(2n+1)△t。

(3) 第一条指令完成需要时间=△t+2△t+3△t=6△t，由于一条指令的"取指令"和"分析"阶段和下一条指令的"执行"阶段重叠，因此，此后每3△t 完成一条指令，余下的n-1条指令用时(n-1)*3△t.

因此n条指令所需要的时间=6△t+(n-1)*3△t=3(n+1)△t

3．用一条5个功能段的浮点加法器流水线计算F＝。每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。

第3题 假设每个功能段的延迟时间为△t。

F＝ =[(A1+1A2)+6(A3+2A4)+8(A5+3A6)]+9[(A7+4A8)+7(A9+5A10)]

由上面的时空图可以看出，在20△t时间内共完成9个加法操作。因此： 吞吐率为：TP= 9/20=0.45 加速比为：Sp= 9*5/20=2.5 效率为： E= 45/(20*5)=45% 4． 设有一个15000条指令的程序在一台时钟速率为25MHz的线性流水线处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指令和无序执行造成的损失。

(1) 用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者加以比较，并计算其加速比。

(2) 该流水线处理机的效率是多少？ (3) 计算该流水线的吞吐率。 第4题 (1) 等效的非流水处理机执行一条指令需要的时间是5个时钟周期。依照加速比定义，

(2) 效率E为 (3) 吞吐率TP为

5． 设有5段流水线处理机的预约表如下： (1) 列出禁止等待时间和冲突向量集。 (2) 画出状态转换图，说明不引起流水线冲突的所有可能的启动序列（循环）。 (3) 根据状态图列出所有简单循环。 (4) 从简单循环中找出迫切循环。 (5) 此流水线的最小平均等待时间(MAL)是多少？ (6) 使用此流水线时，列出可允许的最小恒定循环。 (7) 该流水线的最大吞吐率是多少？ (8) 如果使用最小恒定循环，则吞吐率是多少？ 1 2 3 4 5 6 S1 X X S2 X X S3 X S4 X S5 X X

第5题 (1) 禁止等待时间是：3，4，5。冲突向量为(11100)。

(2) 状态转换图如下所示：

(3) 简单循环如下：(1，1，6)，(2，6)，(6)，(1，6) (4) 迫切(最小启动)循环为(1，1，6) (5) 最小平均等待时间MAL为 (6) 最小恒定循环为(6)。 (7) 设该流水线的时钟周期为τ，则该流水线的最大吞吐率TPMAX为

(8) 使用最小恒定循环时，设该流水线的时钟周期为τ，该流水线的吞吐率为

6． 下列汇编代码在一台3段流水线处理机上执行，每一段都有冒险(相关)检测和分解。这三段是取指令、取操作数（根据要求取一个或者多个）和执行（包括写回操作）。试说明在代码执行中所有可能的相关情况。

Inc R0 /R0←(R0)+1/ Mul ACC,R0 /ACC←(ACC)×(R0)/ Store R1,ACC /R1←(ACC)/ Add ACC,R0 /ACC←(ACC)+(R0)/ Store M,ACC /M←(ACC)/ 第6题 我们首先给上面的指令序列编号如下： I1： Inc R0 /R0←(R0)+1/ I2： Mul ACC,R0 /ACC←(ACC)×(R0)/ I3： Store R1,ACC /R1←(ACC)/ I4： Add ACC,R0 /ACC←(ACC)+(R0)/ I5： Store M,ACC /M←(ACC)/ 我们使用IF、OF和EX来分别代表流水线的取指令、取操作数和执行三段。下面的图表显示了执行的序列： 图中的箭头方向是同一条指令在流水线中的流动方向，从图中我们可以看出： 在t3时刻：O(I1)∩ I(I2)= {R0} ，会发生RAW相关； 在t4时刻：O(I2)∩ I(I3)= {Acc} ，会发生RAW相关； 在t6时刻：O(I4)∩ I(I5)= {Acc} ，会发生RAW相关。 其中我们用O(I1)表示指令I1的输出寄存器(如R0表示寄存器，而Acc表示表示累加器)，I(I2)表示指令I2的输入寄存器。

下面的调度方法能够避免相关的发生：

其中，Stall表示流水线停顿，通过这种方法，可以避免相关的发生。 7． 设有4段流水线处理机如下，此流水线的总求值时间为6个时钟周期，所有相继段必须在每个时钟周期之后才能使用。

(1) 列出这一流水线的4行六列预约表。 (2) 列出任务启动之间的禁止等待时间集。 (3) 画出表示所有可能的等待时间循环的状态图。 (4) 根据状态图列出所有的迫切（最小启动）循环。 (5) 最小平均等待时间值是多少？

第7题 可能会有多种方案。 答案一： (1) 预约表如下所示： 1 2 3 4 5 6 S1 X X S2 X X S3 X S4 X

(2) 禁止等待时间为：4，冲突向量为：(1000)。

(3) 状态转移图如下：

(4) 简单循环如下所示： (1，5)，(1，1，5)，(1，1，1，5)，(1，2，5)，(1，2，3，5)， (1，2，3，2，5)，(1，2，3，2，1，5)，(2，5)，(2，1，5) (2，1，2，5)，(2，1，2，3，5)，(2，3，5)，(3，5)，(3)， (3，2，5)，(3，2，1，5)，(3，2，1，2，5)，(5)，(3，2，1，5)

(5) 最小启动循环如下： (1，1，1，5)和(1，2，3，2)

(6) 平均最小等待时间为：

(7) 最大的吞吐量为： 答案二： (1) 预约表如下所示： 1 2 3 4 5 6 S1 X X S2 X X X S3 X X S4 X

(2) 禁止等待时间为：2和4，冲突向量为：(1010)。

(3) 状态转移图如下： (4) 简单循环如下所示： (3)，(5)，(1，5)和(3，5) (5) 最小启动循环如下：(1，5)和(3)

(6) 最小平均等待时间为：

(7) 最大吞吐量为：

8． 三条功能流水线f1，f2和f3可用下面的预约表来描述：

用这三条流水线还可形成一个组合流水线网络如下： 通过此组合流水线的每个任务按以下的次序使用流水线：第一是f1，其次是f2和f3，再是f1，然后得到输出。双多路转换器从（A,B）或（X,Y）中选择一对输入，并把他们输入给f1。组合流水线的使用也是用组合的预约表来描述的。 (1) 为此组合流水线填充下列预约表： 1 2 3 4 5 6 7 8 9 10 11 12 S1 X S2 X S3 X T1 T2 T3 X U1 X U2 U3

(2) 写出禁止启动循环和初始冲突向量。 (3) 画出能清楚表示所有等待时间循环的状态图。 (4) 列出所有简单循环和迫切（最小启动）循环。 (5) 计算此组合流水线的MAL和最大吞吐率。 第8题 (1) 预约表如下： 1 2 3 4 5 6 7 8 9 10 11 12 S1 X X S2 X X S3 X X X X T1 X X T2 X T3 X U1 X X U2 X U3 X

(2) 禁止等待时间为：8，1，7，9，3，2； 初始冲突向量为：(111000111)

(3) 状态转换图如下：

(4) 简单循环为：(5)，(6)，(10)，(4，6)，(4，10)，(5，6)，(5，10)； 其中最小启动循环为：(5)和(4，6)；

(5) 最小平均启动距离为： (6) 最大吞吐量为；

9． 假设一个四段流水线（其时钟周期τ=20ns）的预约表如下： 1 2 3 4 5 6