第5章 课后习题

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

2．假设一条指令的执行过程分为"取指令"、"分析"和"执行"三段，每一段的时间分别为Dt、2Dt和3Dt。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。
(1) 顺序执行方式。
(2) 仅"取指令"和"执行"重叠。
(3) "取指令"、"分析"和"执行"重叠。

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

4． 设有一个15000条指令的程序在一台时钟速率为25MHz的线性流水线处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指令和无序执行造成的损失。
(1) 用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者加以比较，并计算其加速比。
(2) 该流水线处理机的效率是多少？
(3) 计算该流水线的吞吐率。

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

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)/

7． 设有4段流水线处理机如下，此流水线的总求值时间为6个时钟周期，所有相继段必须在每个时钟周期之后才能使用。

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

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和最大吞吐率。

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

  1 2 3 4 5 6
S1 X         X
S2   X   X    
S3     X      
S4       X X  
(1) 哪些是禁止等待时间和初始冲突向量？
(2) 画出调度该流水线的状态变换图。
(3) 确定与最佳迫切循环相关联的MAL。
(4) 确定与MAL和给定的τ相对应的流水线吞吐率。
(5) 确定该流水线的MAL下限。从上面的状态图你得到最佳等待时间了吗？如果允许你在上面的流水线中插入一个非计算延迟段，使最短迫切循环中的等待时间为1，其目的是要产生一张新的预约表，以获得下限最佳等待时间。
(6) 画出5行7列修改后的预约表。
(7) 为得到最佳循环画出新的状态变换图。
(8) 根据状态图列出所有的简单循环和迫切循环。
(9) 证明新的MAL等于下限。
(10) 这条流水线的最佳吞吐率是多少？与上面的吞吐率相比，改善的百分比是多少？

10． 假设分支概率（相对于所有的指令）为：条件分支20%，跳转和过程调用：5%， 其中，条件成功分支有60%可能执行。在一个4段的流水线中，如果分支指令在第2个时钟周期末决定是否是条件失败分支，在第3个时钟周期末决定是否是条件成功分支。假定第1个时钟周期的操作和条件分支无关，并且忽略其他流水停顿，那么，如果没有控制相关的话，处理器能快多少？

11． 设有两个4段流水线加法器和若干个非计算延迟单元，每个延迟单元有一个单位的时间延迟。
(1) 用已有的加法器和延迟单元构成一个组合流水线部件，试对以下表达式求值： ，对于所有的 。组合流水线接收相继输入a(i)，对于 。
(2) 设有第三个4段流水线加法器，用这第三个加法器来扩大题(a)中的设计，使之能计算以下的递归表达式：，对于所有的 。注意，，其中b(i)是由题(a)中的组合流水线产生的。

12． 比较度为（m，n）的超流水线超标量处理机与度为（1，1）的基准表量处理机的性能。在下述限制情况下，试分析下面公式的加速比表达式：

（1）在1≤m≤4和1≤n≤6的范围内，对加速比S(m,n)最大化后的最佳流水线段数是多少？
（2）阻碍超标量度m增长的实际限制是什么？
（3）阻碍超流水度n增长的实际限制是什么？

13． 在一台单流水线处理机上执行下面的程序。每条指令都要经过"取指令"、"译码"、"执行"和"写结果"4个流水段，每个流水段的延迟时间都是5ns。在"执行"流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接，ALU部件产生的条件码也能够直接送入控制器。
1： 　　　SUB 　R0, R0 　 ;R0←0
2： 　　　LOAD　R1, #8 　 ;R1←向量长度8
3： LOOP：LOAD　R2, A(R1) ;R2←A向量的一个元素
4： 　　　MUL　 R2, R1 　 ;R2←(R2)×(R1)
5： 　　　ADD　 R0, R2 　 ;R0←(R0)＋(R2)
6： 　　　DNE　 R1, LOOP　;R1←(R1)－1,若(R1)≠0转向LOOP
7： 　　　STORE R0, S 　　;保存结果
(1)采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图（中间部分可以省略，图中可用指令序号表示），计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。
(2)采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。
(3)为了采用指令取消技术，请改写上面的程序，并计算程序的执行时间。

14． 在一台每个时钟周期发射两条指令的超标量处理机上运行下面一段程序。所有指令都要经过"取指令"、"译码"、"执行"和"写结果"4个阶段，其中，"取指令"、"译码"和"写结果"三个阶段各为一个流水段，其延迟时间都为10ns。在"执行"阶段，LOAD操作和AND操作各延迟10ns，ADD操作延迟20ns，MUL操作延迟30ns，4种操作部件各设置一个。ADD部件和MUL部件都采用流水线结构，每一级流水线的延迟时间都为10ns。
n1 ：LOAD　R0, A 　；R0←主存(A)单元
n2 ：ADD 　R1, R0　；R1←（R1）＋（R0）
n3 ：LOAD　R2, B　 ；R2←主存(B)单元
n4 ：MUL 　R3, R4　；R3←（R3）×（R4）
n5 ：AND 　R4, R5　；R4←（R4）∧（R5）
n6 ：ADD 　R2, R5　；R2←（R2）＋（R5）

(1)列出这个程序中所有的数据相关，包括写读数据相关、读写数据相关和写写数据相关。
(2)如果所有运算型指令都在"译码"流水段读寄存器，在"写结果"流水段写寄存器，采用顺序发射顺序完成调度方法，画出流水线的时空图，并计算执行这个程序所用的时间。
(3)如果所有运算型指令都在"译码"流水段读寄存器，在"写结果"流水段写寄存器，采用顺序发射乱序完成调度方法，画出流水线的时空图和各条指令完成的时间图，并计算执行这个程序所用的时间。
(4)如果每个操作部件的输出端都有直接数据通路与输入端相连，采用顺序发射乱序完成调度方法，画出流水线的时空图和各条指令完成的时间图，并计算执行这个程序所用的时间。