流水线课后习题

1、文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持第5章课后习题和和.填空题(1)衡量流水线性能的主要指标有指令乱序流动可能造成解决数据相关主要有三种数据相关。(4)超标量处理机开发的是并行性，而超流水线处理机开发的是行性。(1),吞吐率、加速比、效率2).先写后读、先读后写、写写(3),推后分析、设置专用路径.空间、时间.假设一条指令的执行过程分为“取指令、分析和执行三段，每一段的时间分别为 t、24t和34t。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。(1)顺序执行方式。(2)仅取指令和执行重叠。(3)取指令、分析和执行重叠。第2题(1)顺序执行时每条指令用时

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

3、条指令所需要的时间 =6 At+(n-1)*3 At=3(n+1)At10z.用一条5个功能段的浮点加法器流水线计算F=】才。每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。1文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持第3题假设每个功能段的延迟时间为t10F= i=l =(A1+ iA2)+ 6(A3+2A4)+8(A5+3A6)+ 9(A7+ 4A8)+7(A9+ 5A10)动出1

4、a4事1 fi甘由设4r%6飞rv由频，|1i46T*咖獭士1t&,e1139赚设1a4心To41 一i2aL产TI立JI*则jTJSj|1$匝由上面的时空图可以看出，在 204t时间内共完成9个加法操作。因止匕:I吞吐率为：TP= 9/20=0.45加速比为：Sp= 9*5/20=2.5效率为：E= 45/(20*5)=45%.设有一个15000条指令的程序在一台时钟速率为25MHz的线性流水线处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指令和无序执行造成的损失。(1)用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者

5、 加以比较，并计算其加速比。(2)该流水线处理机的效率是多少?(3)计算该流水线的吞吐率。第4题(1)等效的非流水处理机执行一条指令需要的时间是5个时钟周期。依照加速比定义,广 滋15000 x575000/ 八八1nHS =兀+ 5-D 5 + (15000-5 15004(2)效率E9997R , 9997浜 + (w- 1)(3)吞吐率TP为7F =变一上+ S -1)_ 150QO 紫25M 1。甩-15004=2A 9QMIPS.设有5段流水线处理机的预约表如下：(1)列出禁止等待时间和冲突向量集。2文档来源为：从网络收集整理,wo

6、rd版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持(2)画出状态转换图，说明不引起流水线冲突的所有可能的启动序列(循环)(3)根据状态图列出所有简单循环。(4)从简单循环中找出迫切循环。(5)此流水线的最小平均等待时间 (MAL)是多少？(6)使用此流水线时，列出可允许的最小恒定循环。(7)该流水线的最大吞吐率是多少？(8)如果使用最小恒定循环，则吞吐率是多少？123456S1XXS2XXS3XS4XS5XX第5题(1)禁止等待时间是：3, 4, 5。冲突向量为(11100)。(2)状态转换图如下所示:(2)状态转换图如下所示:(3)简单循环如下：(1,1

7、, 6), (2, 6), (6) , (1, 6) (4)迫切(最小启动)循环为(1,1, 6)(5)最小平均等待时间 MAL为MAL =1 6 = 2.67(6)最小恒定循环为(6)。(7)设该流水线的时钟周期为T；(7)设该流水线的时钟周期为T；则该流水线的最大吞吐率TPMAX 为max(8)使用最小恒定循环时，设该流水线的时钟周期为q该流水线的吞吐率为TP =6T3文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持.下列汇编代码在一台3段流水线处理机上执行，每一段都有冒险(相关)检测和分解。这三段是取指令、取操作数(

8、根据要求取一个或者多个)和执行(包括写回操作)。试说明在代码执行中所有可能的相关情况。Inc R0 /R0 (R0)+1/MulACC,R0 /ACC(ACC) X (R0)/Store R1,ACC /R1-(ACC)/AddACC,R0 /ACC(ACC)+(R0)/Store M,ACC/M(ACC)/第6题我们首先给上面的指令序列编号如下：I1 : Inc R0/R0 (R0)+1/I2 : MulACC,R0 /ACC (ACC) X (R0)/I3 : Store R1,ACC /R1 - (ACC)/I4 : Add ACC,R0 /ACC(ACC)+(R0)/I5: Store

9、 M,ACC /M (ACC)/我们使用IF、OF和EX来分别代表流水线的取指令、 取操作数和执行三段。下面的图表显示了执行的序列:tlu131516r7IFIzEMdStoreAddStore5CROr屈斯KU工AccAu刖K工IUKAoc图中的箭头方向是同一条指令在流水线中的流动方向，从图中我们可以看出：在t3时刻：O(I1) n I(I2)= R0,会发生 RAW相关；在 t4 时刻：O(I2) n I(I3)= Acc,会发生 RAW 相关；在 t6 时刻：O(I4) n I(I5)= Acc,会发生 RAW 相关。其中我们用O(I1)表示指令I1的输出寄存器(如R0表示寄存器，而 A

10、cc表示表示累加器)，I(I2)表示指令I2 的输入寄存器。下面的调度方法能够避免相关的发生：UE5MliE?tlGIFMd、-LMiror*富康Acc、AceKOsunLEX* ROAccEMURIACCsun4M其中，Stall表示流水线停顿，通过这种方法，可以避免相关的发生.设有4段流水线处理机如下，此流水线的总求值时间为6个时钟周期，所有相继段必须在每个时钟周期之后才能使用。(1)列出这一流水线的4行六列预约表(2)列出任务启动之间的禁止等待时间集.4文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持(3)画出表示所

11、有可能的等待时间循环的状态图。(4)根据状态图列出所有的迫切(最小启动)循环(5)最小平均等待时间值是多少？第7题可能会有多种方案。答案一：(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,3,5), (2, 3,5), (3, 5), (3),(3,2

12、,5),(3 , 2,1,5),(3, 2, 1 , 2,5), (5), (3, 2, 1,5)(5)最小启动循环如下：(1,1,1, 5)和(1, 2, 3, 2)5文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持(6)平均最小等待时间为:MAL = 2(7)最大的吞吐量为:T 1TP =丁答案二:文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持12(6)平均最小等待时间为:MAL = 2(7)最大的吞吐量为:T 1TP =丁答案二:文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持123456S1XXS2XXXS3XXS4X(1)预约表如下所示:(2)禁

13、止等待时间为：2和4,冲突向量为：(1010)。(4)简单循环如下所示：(3), (5), (1, 5)和(3, 5)最小启动循环如下:(1, 5)和(3)(6)最小平均等待时间为:MAL = 38.最大吞吐量为：三条功能流水线fl ,f2和f3可用下面的预约表来描述:6文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持用这三条流水线还可形成一个组合流水线网络如下：通过此组合流水线的每个任务按以下的次序使用流水线：第一是 fl ,其次是f2和f3,再是fl ,然后得到输 出。双多路转换器从(A,B)或(X,Y)中选择一对输入

14、，并把他们输入给fl。组合流水线的使用也是用组合的预约表来描述的。(1)为此组合流水线填充下列预约表：123456789101112S1XS2XS3XT1T2T3XU1XU2U3(2)写出禁止启动循环和初始冲突向量。(3)画出能清楚表示所有等待时间循环的状态图(4)列出所有简单循环和迫切(最小启动)循环(5)计算此组合流水线的 MAL和最大吞吐率第8题(1)预约表如下:123456789101112S1XXS2XXS3XXXXT1XXT2XT3XU1XXU2XU3X(2)禁止等待时间为：8, 1, 7, 9, 3, 2;初始冲突向量为：(1)(3)状态转换图如下：7文档来源为：从网络收集整理,

15、word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持(4)简单循环为：(5), (6), (10), (4, 6) , (4, 10), (5 , 6), (5, 10);其中最小启动循环为：(5)和(4, 6);(5)最小平均启动距离为：= 5TP = (6)最大吞吐量为；9.假设一个四段流水线(其时钟周期t =20nS的预约表如下:123456S1XXS2XXS3XS4XX(1)哪些是禁止等待时间和初始冲突向量？(2)画出调度该流水线的状态变换图。(3)确定与最佳迫切循环相关联的MAL o(4)确定与MAL和给定的环目对应的流水线吞吐率。(5)确定该

16、流水线的 MAL下限。从上面的状态图你得到最佳等待时间了吗？如果允许你在上面的流水线中插入一个非计算延迟段，使最短迫切循环中的等待时间为1,其目的是要产生一张新的预约表,以获得下限最佳等待时间。(6)画出5行7列修改后的预约表。(7)为得到最佳循环画出新的状态变换图。(8)根据状态图列出所有的简单循环和迫切循环。(9)证明新的MAL等于下限。(10)这条流水线的最佳吞吐率是多少？与上面的吞吐率相比，改善的百分比是多少？第9题(1)禁止等待时间为：1, 2, 5;初始冲突向量为：(10011);8文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本

17、可编辑.欢迎下载支持(2)状态转移图如下:(3)最小平均等待时间为：(4)最大吞吐量为：TP= =5一年 = 16.87Mop3鱼 3x20 x10(million operation per second)(5)最小的平均等待时间为 2,因此，这种调度方法不是最优的。(6)插入非计算性延迟后，预约表如下所示:1234567S1XXS2XXS3XS4XXDX(7)状态转换图变成如下所示:(8)简单循环如下：(4), (5),(7),(3,1), (3,4),(3,5,4), (3,5,7),(1,7)(5,4),(5,7),(3,7),( 1,3,4) , ( 1 , 3, 5,4), ( 1

18、 ,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)9文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持其中最小启动循环为（1,3）（9）此时的最小启动距离为:= - = 22（1。）此时的最大吞吐率为：（1。）此时的最大吞吐率为：分12r.假设分支概率（相对于所有的指令）为：条件分支20%,跳转和过程调用：5%,其中，条件成功分支有60%可能执行。在一个4段的流水线中，如果分支指令在第2个时钟周期末决定是否是条件失败分支，在第3个时钟周期末

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

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

21、可以用来更新PC的地址），在第2个时钟周期末，跳转和调用的目的地址已经确定，所以流水线在第三个时钟10文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持周期再次执行IF以取回正确的指令，这样引起了一个时钟周期的停顿。条件分支发生的情形如下表：指令123456发生的条件分支IFIDEXWBi+1IFstallIFIDi+2stallstallIFi+3stallstall因为条件分支的目的地址在第 3个时钟周期末才能决定，所以出现了2个时钟周期的停顿。条件分支不发生的情形如下表：指令123456不发生的条件分支IFIDEXWB

22、i+1IFstallIDEXi+2stallIFIDi+3stallIF注意到第2个时钟周期取到的是下一条顺序指令，也就是不发生的分支的目标地址，而且由于条件分 支的目的地址在第3个时钟周期末确定，所以会产生一个时钟周期的流水线停顿。(3)各种控制流指令发生的概率。题目已经给出了数据，所以，实际的平均停顿数为:流水线平均停做数 1K泌M 2X12%M 1通人0.37由此，实际的流水线加速比为：- - 比较理想情况和实际情况，我们可以得到如果没有控制相关的情形下，在现有的系统基础上得到的加速比 为:.设有两个4段流水线加法器和若干个非计算延迟单元，每个延迟单元有一个单位的时间延迟。(1)用已有的

23、加法器和延迟单元构成一个组合流水线部件，试对以下表达式求值：既)虱工)+碉-D+诚-2) +式L 3),对于所有的L心1理。组合流水线接收相继输入 a(i),对于L L2,，拜。(2)设有第三个4段流水线加法器，用这第三个加法器来扩大题(a)中的设计，使之能计算以下的递归表达式：耳(i) =值+ XG-D,对于所有的1=4二,4。注意，界,3+戏T)+ WD +冗。-2)炖)+成-4),其中b(i)是由题(a)中的组合流水线产生的。11文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持第11题(1)组合流水线(1)组合流水线

24、(2)第三个加法器的连接：聆k 4段加法f器12.比较度为(m, n)的超流水线超标量处理机与度为(1, 1)的基准表量处理机的性能。在下述限制情况下，试分析下面公式的加速比表达式：. 丁E M 1阳轼* * NT)3 (也 加)=-=r；=k寸(M-陋)/(也用)常料ktN一闸(1)在1&mc4和1wn06的范围内，对加速比 S(m,n)最大化后的最佳流水线段数是多少?(2)阻碍超标量度 m增长的实际限制是什么？(3)阻碍超流水度n增长的实际限制是什么？第12题(1)对于给定的m和n的范围，我们有不等式:僧题(卅-1) 1 NT 葡-m我们对超流水超标量机的加速比公式进行改写如下:、, 用月

25、(N-D +用然上、(W-网)+博号上 一区(附,用)=22 1(M-用。(M-附)斗烟月上根据上面的公式，可以知道当mnk取最小值时，S(m,n)有最大值，因此，为了使加速比最大，流水线的段数应t是1。(2)指令级的并行度限制了超标量度的增长。(3)时钟多相的技术(各部件间的同步存在困难)限制了超流水度的增长。13.在一台单流水线处理机上执行下面的程序。每条指令都要经过“取指令、译码、执行和写结果4个流水段，每个流水段的延迟时间都是5ns。在执行流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接，AL

26、U部件产生的条件码也能够直接送入控制器。12文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持SUBR0, R0;R0-0LOADR1, #8；R1一向量长度 8LOOP : LOAD R2, A(R1) ;R2 A向量的一个元素MULR2, R1;R2 (R2) X (R1)ADDR0, R2;R0 -(R0)+(R2)DNE R1, LOOP ;R1 (R1)1,若(R1)，造向 LOOPSTORE R0, S;保存结果(1)采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图(中间部分可以省略，图中 可用

27、指令序号表示)，计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。(2)采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部 件和ALU部件的使用效率。(3)为了采用指令取消技术，请改写上面的程序，并计算程序的执行时间。第13题(1)采用静态分支预测技术，每次都预测转移不成功。(1)采用静态分支预测技术，每次都预测转移不成功。吞吐率 TP =加速忆”空巨巴一出 52吞吐率 TP =加速忆”空巨巴一出 52译码部件的效率，g的彳|匹度时或出;减件的效率：5- -*0.45152 0用3 52(2)采用静态分支预测技术，每次都预测转移成功。

28、5x(3+4x8-b 2 + 353 = 5x(3+4x8-b 2 + 353 = (4 乂打4 = 39175(25)40的用=0.9004025屈在行=一 =0.&2写40或-0 87541?(3)采用指令取消技术。SUB R0, R0;R0-013文档来源为：从网络收集整理13文档来源为：从网络收集整理,word版本可编辑,欢迎下载支持.文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持LOAD R1, #8；R1一向量长度 8LOAD R2, A(R1) ;R2 A向量的一个元素文档来源为：从网络收集整理,word版本可编辑.欢迎下载支持LOAD R1, #8；R1一向量长度

29、 8LOAD R2, A(R1) ;R2 A向量的一个元素MUL R2, R1;R2(R2) X(R1)LOOP: ADD R0, R2;R0 -(R0)+(R2)DNE R1, LOOP ;R1(R1) 1,若(R1) 10转向 LOOPLOAD R2, A(R1) ;R2 A向量的一个元素MULR2, R1;R2(R2) X(R1)STORE R0, S;保存结果程序的执行时间为：5nsX40 = 200ns14.在一台每个时钟周期发射两条指令的超标量处理机上运行下面一段程序。所有指令都要经过“取指令、译码、执行和写结果”4个阶段，其中，取指令、译码和写结果”三个阶段各为一个流水段，其延 迟时间都为10ns。在执行”阶段，LOAD操作和AND操作各延迟10ns, ADD操作延迟20ns, MUL操作 延迟30ns, 4种操作部件各设置一个。ADD部件和MUL部件都采用流水线结构，每一级流水线的延迟时间都为10ns。n1 :LOADR