计算机系统结构第四章习题解答.doc

1. 假设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每一段的时间分别是△t、2△t和3△t在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式⑴　顺序执行方式⑵　仅“取指令”和“执行”重叠⑶　“取指令”、“分析”和“执行”重叠答：⑴　顺序执行方式△t2△t3△t12......1212T＝＝n(△t＋2△t＋3△t)＝6n△t⑵　仅“取指令”和“执行”重叠△t2△t3△t12......1212T＝6△t＋＝6△t＋(n-1)(2△t＋3△t)＝(5n＋1)△t⑶　“取指令”、“分析”和“执行”重叠精品.△t2△t3△t1234......12341234T＝6△t＋＝6△t＋(n-1)(3△t)＝(3n＋3)△t2. 一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为△t开始5个任务，每间隔一个△t向流水线输入一个任务，然后停顿2个△t，如此重复求流水线的实际吞吐率、加速比和效率答：123456789101112131415...1234567891011121314151234567891011121314151234567891011121314151234567891011121314151617181920212223我们可以看出，在（7n+1）Δt的时间内，可以输出5n个结果，如果指令的序列足够长（n→∞），并且指令间不存在相关，那么，吞吐率可以认为满足：加速比为：精品.从上面的时空图很容易看出，效率为：3. 用一条5个功能段的浮点加法器流水线计算。

每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率答：首先需要考虑的是“10个数的和最少需要做几次加法？”，我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关由于加法满足交换律和结合律，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6精品.I9： F←R7+R8这并不是唯一可能的计算方法假设功能段的延迟为Δt时空图如下（图中的数字是指令号）：123456789123456789123456789123456789123456789123456789101112131415161718192021整个计算过程需要21Δt，所以吞吐率为：加速比为：效率为：4. 一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。

流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器用这条流水线计算向量点积，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率精品.答：我们安排运算次序如下：把中间结果寄存器称为R，源操作数寄存器称为A、B，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：I1：R0←A0*B0I8：R7←R0+R1I2：R1←A1*B1I9：R8←R2+R3I3：R2←A2*B2I10：R9←R4+R5I4：R3←A3*B3I11：R10←R6+R7I5：R4←A4*B4I12：R11←R8+R9I6：R5←A5*B5I13：F←R10+R11I7：R6←A6*B6假设功能段的延迟为Δt时空图如下（图中的数字是指令号）：12345678910111213123456712345678910111213891011121312345678910111213123456789101112131415161718192021222324整个计算过程需要24Δt，所以吞吐率为：精品.加速比为：效率为：5. 一条有三个功能段的流水线如下图每个功能段的延迟时间均相等，都为△t。

其中功能段S2的输出要返回到它自己的输入端循环一次输出输入S3S2S1△t△t△t⑴　如果每间隔一个△t向流水线的输入端连续输入新任务，问这条流水线会发生什么情况？⑵　求这条流水线能够正常工作的最大吞吐率、加速比和效率⑶　有什么办法能够提高这条流水线的吞吐率，画出新的流水线答：⑴　如果每间隔一个△t向流水线的输入端连续输入新任务，流水线S2功能段存在资源冲突见下表：时间功能段t1t2t3t4t5S1X1X2X3X4X5S2X1X1,X2X2,X3X3,X4S3X1X2⑵　精品.每间隔两个△t向流水线的输入端连续输入新任务（如见下表所示）可获得最佳性能时间功能段t1t2t3t4t5t6S1X1X2X3S2X1X1X2X2X3S3X1X2我们可以看出：在（2n+2）Δt的时间内，可以输出n个结果，如果指令的序列足够长（n→∞），并且指令间不存在相关，那么，吞吐率为：加速比为：效率为：⑶　如要提高这条流水线的吞吐率，可采用：将功能段S2重复设置一次，见下图：输出S3△t△t△t输入S2S2S1△t6. 一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns，它的预约表如下：精品.时间流水段1234567S1××S2××S3×S4××⑴ 写出流水线的禁止向量和初始冲突向量。

⑵ 画出调度流水线的状态图⑶ 求流水线的最小启动循环和最小平均启动距离⑷ 求平均启动距离最小的恒定循环⑸ 求流水线的最大吞吐率⑹ 按照最小启动循环连续输入10个任务，求流水线的实际吞吐率⑺ 画出该流水线各功能段之间的连接图答：⑴ 禁止向量F=（6,4,2）；冲突向量C=（101010）⑵ i=1i≥7i=3i≥7i=5i=3i≥7i=5i=5i≥7101010111111101111101011C0C1C2C3精品.⑶ 简单循环平均启动距离1，7（C0-C1-C0）43，7（C0-C2-C0）55，7（C0-C3-C0）63，5，7（C0-C2-C3-C0）53，5（C0-C2-C3-C2-C3）45，3，7（C0-C3-C2-C0）55，3（C0-C3-C2-C3-C2）45（C0-C3-C3）57（C0-C0）7∴ 流水线的最小启动循环为：（1，7）或（3，5）或（5，3），最小平均启动距离为4⑷ 由上表可知：平均启动距离最小的恒定循环为（5）⑸ 采用最小平均启动距离为4的最小启动循环可获得流水线的最大吞吐率，以（1，7）为例：（其他类似，最大吞吐率皆相同）当任务数为偶数2n时：当任务数为奇数2n+1时：精品.∴ 流水线的最大吞吐率为：⑹ 10个任务的实际吞吐率：利用上式可得（偶数个任务）TP10=1/4△t=12.5M(任务/s)。

⑺ 该流水线的连接图为：S1S2S3S41234567输入输出7. 一条由4个功能段组成的非线性流水线的预约表如下，每个功能段的延迟时间都为10ns时间流水段123456S1××S2××S3×S4××⑴　写出流水线的禁止向量和初始冲突向量⑵　画出调度流水线的状态图⑶　求流水线的最小启动循环和最小平均启动距离精品.⑷　在流水线中插入一个非计算延迟功能段后，求该流水线的最佳启动循环及其最小平均启动距离⑸　画出插入一个非计算延迟功能段后的流水线预约表（5行8列）⑹　画出插入一个非。