第05章流水线课后习题

1、第5章课后习题1. 填空题指令乱序流动可能造成衡量流水线性能的主要指标有和三种数据相关。解决数据相关主要有法和法。超标量处理机开发的是并行性，而超流水线处理机开发的是并行性。(1) .吞吐率、加速比、效率(2) .先写后读、先读后写、写写(3) .推后分析、设置专用路径(4) .空间、时间2. 假设一条指令的执行过程分为 -取指令"、"分析"和"执行"三段，每一段的时间分别为 t、2t和3 to 在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。(1) 顺序执行方式。(2) 仅"取指令"和"执行&quo

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

3、quot;阶段重叠，因此，此后每假设每个功能段的延迟时间为to= t+2 t+3 t=6 t，由于一条指令的-取指令"和"分析-阶段和下一条指令的3 t完成一条指令，余下的n-1条指令用时(n-1)*3 t.因此n条指令所需要的时间=6At+(n-1)*3 t=3(n+1) t10工3. 用一条5个功能段的浮点加法器流水线计算F=i司。每个功能段的延迟时间均相等，流水线的输出端 与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流 水线时空图，计算流水线的实际吞吐率、加速比和效率。10F= 1 司 =(A1+ 1A2)+ 6(A3+2

4、A4)+8(A5+3A6)+ 9(A7+ 4A8)+7(A9+ 5A10)1254£s B11踰社毘11i4s45KJ功曲Ml1i斗seTs1 >1t:4斗t<Tqa 11s4Tai &I跡！4$X5昏Ts31kItIEleB n由上面的时空图可以看出，在 20t时间内共完成9个加法操作。因此:吞吐率为:TP= 9/20=0.45 缶加速比为:Sp= 9*5/20=2.5效率为:E= 45/(20*5)=45%4. 设有一个15000条指令的程序在一台时钟速率为25MHz的线性流水线处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指

5、令和无序执行造成的损失。(1) 用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者 加以比较，并计算其加速比。(2) 该流水线处理机的效率是多少?(3) 计算该流水线的吞吐率。(1) 等效的非流水处理机执行一条指令需要的时间是5个时钟周期。依照加速比定义,15000x5f =需56(2) 效率E为灿七十 3-1)15004(3) 吞吐率TP为TP士+ a-l)=15Q0Q 减IQ% 片 EfMmsVQ1500424.99曲朋5.设有5段流水线处理机的预约表如下:(1)列出禁止等待时间和冲突向量集。画出状态转换图，说明不引起流水线冲突的所有可能的启动序列(循

6、环)。根据状态图列出所有简单循环。从简单循环中找出迫切循环。(5)此流水线的最小平均等待时间 (MAL)是多少?(6)使用此流水线时，列出可允许的最小恒定循环。(7)该流水线的最大吞吐率是多少?(8)如果使用最小恒定循环，则吞吐率是多少?123456S1XXS2XXS3XS4XS5XX(1)禁止等待时间是：3, 4，5。冲突向量为(11100)。(2) 状态转换图如下所示:简单循环如下：(1, 1, 6)，(2，6)，(6)，(1, 6)迫切(最小启动)循环为(1,1，6)(5)最小平均等待时间MAL为胚= 2.67（6）最小恒定循环为（6）。（7）设该流水线的时钟周期为T则该流水线的最大吞吐

7、率TPMAX为（8）使用最小恒定循环时，设该流水线的时钟周期为T该流水线的吞吐率为6.下列汇编代码在一台3段流水线处理机上执行，每一段都有冒险（相关）检测和分解。这三段是取指令、取操作数（根据要求取一个或者多个）和执行（包括写回操作）。试说明在代码执行中所有可能的相关情况。Inc R0/R0 J (R0)+1/Mui ACC,R0 /ACC (ACC) X (R0)/Store R1,ACC /R1 (ACC)/Add ACC,R0 /ACC (ACC)+(R0)/Store M,ACC /M (ACC)/我们首先给上面的指令序列编号如下:I1:IncI2 :MuiI3 :StoreI4 :A

8、ddI5 :StoreR0ACC,R0 /ACC (ACC) X (R0)/R1,ACC /R1 (ACC)/ACC,R0 /ACC (ACC)+(R0)/M,ACC /M (ACC)/R0 (R0)+1/我们使用IF、OF和EX来分别代表流水线的取指令、 取操作数和执行三段。下面的图表显示了执行的序列:u13IFMdAddStareFRdA»,EU)鼻 Accf Act用AwDCpRaFMeFRlAcc图中的箭头方向是同一条指令在流水线中的流动方向，从图中我们可以看出:在t3时刻:0(11)1(12)= RO，会发生RAW相关;在t4时刻:0(12)1(13)= Acc，会发生RA

9、W相关;在t6时刻:0(14)1(15)= Acc，会发生RAW相关。其中我们用0(11)表示指令11的输出寄存器(如R0表示寄存器，而 Acc表示表示累加器)，1(12)表示指令I2的输入寄存器。下面的调度方法能够避免相关的发生:1 口E4aE70w 1加 IIF J叫strflMiSU1-Face、AceKflEmiEX 1r moeuu1 彌4R1SUfl r M其中，Stall表示流水线停顿，通过这种方法，可以避免相关的发生。7.设有4段流水线处理机如下，此流水线的总求值时间为6个时钟周期，所有相继段必须在每个时钟周期之后才能使用。(1)列出这一流水线的4行六列预约表。(2) 列出任务

10、启动之间的禁止等待时间集。(3) 画出表示所有可能的等待时间循环的状态图。(4) 根据状态图列出所有的迫切(最小启动)循环。(5) 最小平均等待时间值是多少？可能会有多种方案。答案一:(1)预约表如下所示:123456S1XXS2XXS3XS4X(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

11、,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 ,2)(6) 平均最小等待时间为:(7) 最大的吞吐量为:答案二:(1)预约表如下所示:123456S1XXS2XXXS3XXS4X(2)禁止等待时间为：2和4 ,冲突向量为：(1010)。(3)状态转移图如下:(4) 简单循环如下所示:(3), (5), (1, 5)和(3, 5)(5)最小启动循环如下:(1 , 5)和(3)(6)最小平均等待

12、时间为:MAL = 3(7)最大吞吐量为：8.三条功能流水线f1，f2和f3可用下面的预约表来描述:123413341234SIXTIXU1X£3XT3XU2XS3XXT3U3X用这三条流水线还可形成一个组合流水线网络如下:f1，其次是f2和f3，再是f1，然后得到输通过此组合流水线的每个任务按以下的次序使用流水线：第一是出。双多路转换器从（A,B ）或（X,Y ）中选择一对输入，并把他们输入给f1。组合流水线的使用也是用组合的预约表来描述的。为此组合流水线填充下列预约表:1 23456789101112S1XS2XS3XT1T2T3XU1XU2U3写出禁止启动循环和初始冲突向量。画

13、出能清楚表示所有等待时间循环的状态图。(5)计算此组合流水线的 MAL和最大吞吐率。列出所有简单循环和迫切（最小启动）循环。（1）预约表如下:123456789101 1112S1XXS2XXS3XXXXT1XXT2XT3XU1XXU2XU3X(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)最小平均启动距离为：MU =(6)TP = 最大吞吐量为；勺'9

14、.假设一个四段流水线(其时钟周期T =20n)的预约表如下:1 1 1 231456S1XXS2XXS3XS4XX哪些是禁止等待时间和初始冲突向量?画出调度该流水线的状态变换图。确定与最佳迫切循环相关联的MAL。确定与MAL和给定的T相对应的流水线吞吐率。(5)确定该流水线的MAL下限。从上面的状态图你得到最佳等待时间了吗？如果允许你在上面的流水(5)线中插入一个非计算延迟段，使最短迫切循环中的等待时间为1,其目的是要产生一张新的预约表,以获得下限最佳等待时间。(6)(6)画出5行7列修改后的预约表。(7)(7)为得到最佳循环画出新的状态变换图。(8)(8)根据状态图列出所有的简单循环和迫切循

15、环。证明新的MAL等于下限。(1)禁止等待时间为：1, 2,5；(9)(9)(10) (10)这条流水线的最佳吞吐率是多少？与上面的吞吐率相比，改善的百分比是多少?初始冲突向量为：(10011)(2)状态转移图如下:(3)最小平均等待时间为:MAL = 3(4)最大吞吐量为:(million op eration per second)(5) 最小的平均等待时间为 2,因此，这种调度方法不是最优的。（6）插入非计算性延迟后，预约表如下所示:1234567S1XXS2XXS3XS4XXDX（7）状态转换图变成如下所示:（8）简单循环如下:(4)，（5）,（ 7），（ 3, 1），（ 3，4），（

16、 3，5, 4），（ 3, 5，7），（ 1，7）(5，4），（ 5，7），（ 3，7），（ 1，3, 4），（ 1，3, 5，4），（ 1，3, 5，7）(1 ,3, 7),( 1, 4, 3),( 1, 4, 4),( 1 , 4, 7),( 5, 3, 4),( 5, 3, 7)(5,3, 1 , 7)其中最小启动循环为（1, 3）（9）此时的最小启动距离为:=（10）此时的最大吞吐率为：10. 假设分支概率（相对于所有的指令）为：条件分支20%，跳转和过程调用：5%,其中，条件成功分支有60%可能执行。在一个4段的流水线中，如果分支指令在第2个时钟周期末决定是否是条件失败分支，在第3个

17、时钟周期末决定是否是条件成功分支。假定第1个时钟周期的操作和条件分支无关，并且忽略其 他流水停顿，那么，如果没有控制相关的话，处理器能快多少?1斗流水鑽平均停顿数第10题我们使用加速比来衡量控制相关引起的流水线的效率下降。考虑如下的公式:这个公式中假设输入的任务数目足够多，并且我们假设所有的流水线停顿都由控制相关引起（因为我们只 关心控制相关），而式中的流水线平均停顿数定义为平均每条指令执行过程流水线停顿的时钟周期数，该 公式可以看成是流水线加速比公式的极限情况。理想状态下，如果没有控制相关，也就没有流水线停顿，于是，有为了得到因为控制相关引起的流水线平均停顿数，我们需要三方面的信息: （1）

18、我们需要知道程序中的控制流指令类型。本题中有三种：条件分支发生，条件分支不发生，跳转和子 程序调用。IF、ID、EX（2）我们需要知道每一种控制流指令引起的流水线平均停顿数。我们假设流水线的四段分别为 和WB （分别代表取指令、指令分析、指令执行和写回）。首先我们考虑跳转和调用的情形。如下面的表所示:指令123456跳转或调用IFIDEXWBi+1IFIFIDEXi+2stallIFIDi+3stallIF由于流水线的第一级总是可以提前进行（即不管下一条指令的内容），所以在第2个时钟周期（相对于跳转或调用指令），下一条指令依然进入IF段（因为此时i+1指令的地址是这时知道的唯一一个可以用来更新

19、PC的地址)，在第2个时钟周期末，跳转和调用的目的地址已经确定，所以流水线在第三个时钟 周期再次执行IF以取回正确的指令，这样引起了一个时钟周期的停顿。条件分支发生的情形如下表:指令123456发生的条件分支IFIDEXWBi+1IFstallIFIDi+2stallstallIFi+3stallstall因为条件分支的目的地址在第 3个时钟周期末才能决定，所以出现了2个时钟周期的停顿。条件分支不发生的情形如下表:指令123456不发生的条件分支IFIDEXWBi+1IFstallIDEXi+2stallIFIDi+3stallIF注意到第2个时钟周期取到的是下一条顺序指令，也就是不发生的分支

20、的目标地址，而且由于条件分 支的目的地址在第3个时钟周期末确定，所以会产生一个时钟周期的流水线停顿。(3)各种控制流指令发生的概率。题目已经给出了数据，所以，实际的平均停顿数为:新水钱平均停顿教=C 1X璃讯2X UVM0.37由此，实际的流水线加速比为："一1十0审一 23 比较理想情况和实际情况，我们可以得到如果没有控制相关的情形下，在现有的系统基础上得到的加速比4为：2311. 设有两个4段流水线加法器和若干个非计算延迟单元，每个延迟单元有一个单位的时间延迟。(1)用已有的加法器和延迟单元构成一个组合流水线部件，试对以下表达式求值：- 口+，对于所有的i - 4,5; &quo

21、t;+ 。组合流水线接收相继输入a(i)，对于 i。(2) 设有第三个4段流水线加法器，用这第三个加法器来扩大题(a)中的设计，使之能计算以下的递归表达式：砒对于所有的J = 4壬诃 。注意，蛊-诚)UQ -1) 诡)珂(30-1)4盂点-2)姻+甘4)，其中b(i)是由题(a)中的组合流水线产生的。第11题(1) 组合流水线：(2) 第三个加法器的连接：12. 比较度为(m, n)的超流水线超标量处理机与度为(1，1)的基准表量处理机的性能。在下述限制 情况下，试分析下面公式的加速比表达式：W 、 T(U)更 + 鮎-1嗣：+ 旳-1)E跑町=网M)上十聊)f(朋月J阿诞+ N-聊(1)(2

22、)阻碍超标量度 m增长的实际限制是什么?(3)阻碍超流水度n增长的实际限制是什么?在1<mC4和1<n<6的范围内，对加速比 S(m,n)最大化后的最佳流水线段数是多少?第12题(1)对于给定的m和n的范围，我们有不等式:我们对超流水超标量机的加速比公式进行改写如下:z V 用曲(N-D +.(M-啊1 + 朋沖k .=Z> 1(M-即+ 朋旳左根据上面的公式，可以知道当mnk取最小值时，S(m,n)有最大值，因此，为了使加速比最大，流水线的段数应该是1。指令级的并行度限制了超标量度的增长。时钟多相的技术(各部件间的同步存在困难)限制了超流水度的增长。13.个流水段，每

23、个流水段的延迟时间都是在一台单流水线处理机上执行下面的程序。5ns。每条指令都要经过-取指令"、"译码-、"执行-和"写结果"4在"执行"流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接,ALU部件产生的条件码也能够直接送入控制器。1:SUBR0, R0 ;R0 j02:LOADR1, #8;R1 j向量长度83:LOOP : LOADR2, A(R1) ;R2 jA向量的一个元素4:MULR2, R1;R2 j (R2) X (R

24、1)5:ADDR0, R2;R0 j (R0) + (R2)6:DNER1, LO OP;R1 J(R1)- 1,若(R1)工转向 LOOP7:STORE R0, S;保存结果(1)采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图(中间部分可以省略，图中 可用指令序号表示)，计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。(2)采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部 件和ALU部件的使用效率。(3)为了采用指令取消技术，请改写上面的程序，并计算程序的执行时间。第13题卜13ITTmrrrrm10'

25、;11lalId 14i，.SO51敢ft1$J5467 1ALU£4&ft4ICu3-A.ATT11:廊1ascstf34llhi67J3nnnnm3d&11u(1)采用静态分支预测技术，每次都预测转移不成功。呑坤吩"；2心吟蹈加速吐蚩g-2旳4X8 + 352译码部件的致率I民盯一-6旳呂或 -0,67? 5252陽P件的数率、甌-更-(vm52(2)采用静态分支预测技术，每次都预测转移成功。40超連區=0 ?004025 珈 -0.&2540我 = 0.87540(3)米用指令取消技术。SUBRO, RO;R0TLOADR1, #8；R1J向量

26、长度8LOADR2, A(R1) ;R2 jA向量的一个元素MULR2, R1;R2j(R2) X(R1)LOOP：ADDR0, R2;R0 j (R0) + (R2)DNER1, LOOP;R1J(R1) - 1,若(R1)工0专向 LOOPLOADR2, A(R1) ;R2 jA向量的一个元素MULR2, R1;R2j(R2)X(R1)STORER0, S; 保存结果程序的执行时间为：5nsX40= 200ns所有指令都要经过 "取指令 "、14 在一台每个时钟周期发射两条指令的超标量处理机上运行下面一段程序。"译码"、"执行"和

27、"写结果 "4个阶段，其中， "取指令 "、"译码"和"写结果"三个阶段各为一个流水段，其延 迟时间都为10ns。在"执行"阶段，LOAD操作和AND操作各延迟10ns, ADD操作延迟20ns, MUL操作延迟 30ns， 4 种操作部件各设置一个。 ADD 部件和 MUL 部件都采用流水线结构，每一级流水线的延迟时 间都为 10ns。n1 ： LOADR0, A;RZ主存(A)单元n2 ： ADDR1, R0； R1j(R1)(R0)n3 ： LOADR2, B;R2j主存(B)单元n4 ：MULR3, R4； R3jR3)X ( R4)n5 ： ANDR4, R5； R4jR4)A( R5)n6 ： ADDR2, R5； R2jR2)( R5)(1)列出这个程序中所有的数据相关，包括写读数据相关、读写数据相关和写写数据相关。(2)如果所有运算型指令都在"译码&q