流水线课后习题

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

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

3、+1)t3用一条5个功能段的浮点加法器流水线计算F。每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。第3题假设每个功能段的延迟时间为t。F =(A1+1A2)+6(A3+2A4)+8(A5+3A6)+9(A7+4A8)+7(A9+5A10)由上面的时空图可以看出，在20t时间内共完成9个加法操作。因此：吞吐率为：TP= 9/20=0.45 加速比为：Sp= 9*5/20=2.5效率为： E= 45/(20*5)=45%4 设有一个15000条指令的程序在一台时

4、钟速率为25MHz的线性流水线处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指令和无序执行造成的损失。 (1) 用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者加以比较，并计算其加速比。(2) 该流水线处理机的效率是多少？(3) 计算该流水线的吞吐率。第4题(1) 等效的非流水处理机执行一条指令需要的时间是5个时钟周期。依照加速比定义，(2) 效率E为(3) 吞吐率TP为5 设有5段流水线处理机的预约表如下：(1) 列出禁止等待时间和冲突向量集。(2) 画出状态转换图，说明不引起流水线冲突的所有可能的启动序列（循环）。(

5、3) 根据状态图列出所有简单循环。(4) 从简单循环中找出迫切循环。(5) 此流水线的最小平均等待时间(MAL)是多少？(6) 使用此流水线时，列出可允许的最小恒定循环。(7) 该流水线的最大吞吐率是多少？(8) 如果使用最小恒定循环，则吞吐率是多少？123456S1XXS2XXS3XS4XS5XX第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) 设该流水线的时钟周期为

6、，则该流水线的最大吞吐率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： IncR0 /R0(R0)+1/I2： M

7、ulACC,R0 /ACC(ACC)(R0)/I3： StoreR1,ACC /R1(ACC)/I4： Add ACC,R0 /ACC(ACC)+(R0)/I5： StoreM,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的输出

8、寄存器(如R0表示寄存器，而Acc表示表示累加器)，I(I2)表示指令I2的输入寄存器。下面的调度方法能够避免相关的发生：其中，Stall表示流水线停顿，通过这种方法，可以避免相关的发生。7 设有4段流水线处理机如下，此流水线的总求值时间为6个时钟周期，所有相继段必须在每个时钟周期之后才能使用。(1) 列出这一流水线的4行六列预约表。(2) 列出任务启动之间的禁止等待时间集。(3) 画出表示所有可能的等待时间循环的状态图。(4) 根据状态图列出所有的迫切（最小启动）循环。(5) 最小平均等待时间值是多少？ 第7题可能会有多种方案。答案一：(1) 预约表如下所示：123456S1XXS2XXS3

9、XS4X(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) 预约表如下所示：123456

10、S1XXS2XXXS3XXS4X(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。组合流水线的使用也是用组合的预约表来

11、描述的。(1) 为此组合流水线填充下列预约表： 123456789101112S1XS2XS3XT1T2T3XU1XU2U3(2) 写出禁止启动循环和初始冲突向量。(3) 画出能清楚表示所有等待时间循环的状态图。(4) 列出所有简单循环和迫切（最小启动）循环。(5) 计算此组合流水线的MAL和最大吞吐率。第8题(1) 预约表如下：123456789101112S1XXS2XXS3XXXXT1XXT2XT3XU1XXU2XU3X(2) 禁止等待时间为：8，1，7，9，3，2；初始冲突向量为：(111000111)(3) 状态转换图如下：(4) 简单循环为：(5)，(6)，(10)，(4，6)，(

12、4，10)，(5，6)，(5，10)；其中最小启动循环为：(5)和(4，6)；(5) 最小平均启动距离为：(6) 最大吞吐量为；9 假设一个四段流水线（其时钟周期=20ns）的预约表如下：123456S1XXS2XXS3XS4XX(1) 哪些是禁止等待时间和初始冲突向量？(2) 画出调度该流水线的状态变换图。(3) 确定与最佳迫切循环相关联的MAL。(4) 确定与MAL和给定的相对应的流水线吞吐率。(5) 确定该流水线的MAL下限。从上面的状态图你得到最佳等待时间了吗？如果允许你在上面的流水线中插入一个非计算延迟段，使最短迫切循环中的等待时间为1，其目的是要产生一张新的预约表，以获得下限最佳等

13、待时间。(6) 画出5行7列修改后的预约表。 (7) 为得到最佳循环画出新的状态变换图。(8) 根据状态图列出所有的简单循环和迫切循环。(9) 证明新的MAL等于下限。(10) 这条流水线的最佳吞吐率是多少？与上面的吞吐率相比，改善的百分比是多少？第9题(1) 禁止等待时间为：1，2，5；初始冲突向量为：（10011）；(2) 状态转移图如下：(3) 最小平均等待时间为： (4) 最大吞吐量为：(million operation per second)(5) 最小的平均等待时间为2，因此，这种调度方法不是最优的。(6) 插入非计算性延迟后，预约表如下所示：1234567S1XXS2XXS3X

14、S4XXDX(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，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段的流水线中，如果分支指令在

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

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

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

18、，也就是不发生的分支的目标地址，而且由于条件分支的目的地址在第3个时钟周期末确定，所以会产生一个时钟周期的流水线停顿。(3) 各种控制流指令发生的概率。题目已经给出了数据，所以，实际的平均停顿数为：由此，实际的流水线加速比为： 比较理想情况和实际情况，我们可以得到如果没有控制相关的情形下，在现有的系统基础上得到的加速比为： 11 设有两个4段流水线加法器和若干个非计算延迟单元，每个延迟单元有一个单位的时间延迟。(1) 用已有的加法器和延迟单元构成一个组合流水线部件，试对以下表达式求值： ，对于所有的 。组合流水线接收相继输入a(i)，对于 。(2) 设有第三个4段流水线加法器，用这第三个加法器

19、来扩大题(a)中的设计，使之能计算以下的递归表达式：，对于所有的 。注意，其中b(i)是由题(a)中的组合流水线产生的。第11题 (1) 组合流水线: (2) 第三个加法器的连接: 12 比较度为（m，n）的超流水线超标量处理机与度为（1，1）的基准表量处理机的性能。在下述限制情况下，试分析下面公式的加速比表达式： （1）在1m4和1n6的范围内，对加速比S(m,n)最大化后的最佳流水线段数是多少？（2）阻碍超标量度m增长的实际限制是什么？（3）阻碍超流水度n增长的实际限制是什么？第12题 (1) 对于给定的m和n的范围，我们有不等式：我们对超流水超标量机的加速比公式进行改写如下：根据上面的公

20、式，可以知道当mnk取最小值时，S(m,n)有最大值，因此，为了使加速比最大，流水线的段数应该是1。(2) 指令级的并行度限制了超标量度的增长。(3) 时钟多相的技术（各部件间的同步存在困难）限制了超流水度的增长。13 在一台单流水线处理机上执行下面的程序。每条指令都要经过取指令、译码、执行和写结果4个流水段，每个流水段的延迟时间都是5ns。在执行流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接，ALU部件产生的条件码也能够直接送入控制器。1： SUB R0, R0 ;R002： LOADR1, #8

21、 ;R1向量长度83： LOOP：LOADR2, A(R1) ;R2A向量的一个元素4： MUL R2, R1 ;R2(R2)(R1)5： ADD R0, R2 ;R0(R0)(R2)6： DNE R1, LOOP;R1(R1)1,若(R1)0转向LOOP7： STORE R0, S ;保存结果(1)采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图（中间部分可以省略，图中可用指令序号表示），计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。(2)采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效

22、率。(3)为了采用指令取消技术，请改写上面的程序，并计算程序的执行时间。第13题(1)采用静态分支预测技术，每次都预测转移不成功。(2)采用静态分支预测技术，每次都预测转移成功。(3)采用指令取消技术。SUBR0, R0;R00LOAD R1, #8;R1向量长度8LOAD R2, A(R1) ;R2A向量的一个元素MULR2, R1;R2(R2)(R1)LOOP：ADDR0, R2;R0(R0)(R2)DNER1, LOOP;R1(R1)1,若(R1)0转向LOOPLOAD R2, A(R1) ;R2A向量的一个元素MULR2, R1;R2(R2)(R1)STORER0, S ;保存结果程序的执行时间为：5ns40200ns14 在一台每个时钟周期发射两条指令的超标量处理机上运行下面一段程序。所有指令都要经过取指令、译码、执行和写结果4个阶段，其中，取指令、译码和写结果三个阶段各为一个流水段，其延迟时间都为10ns。在执行阶段，LOAD操作和AND操作各延迟10ns，ADD操作