《计算机系统结构 第四章(习题解答)》由会员分享，可在线阅读，更多相关《计算机系统结构 第四章(习题解答)（15页珍藏版）》请在金锄头文库上搜索。
1、1. 假设一条指令的执行过程分为“取指令” 、 “分析”和“执行”三段，每一段的时间分别是t、2t 和 3t。在下列各种情况下，分别写出连续执行n 条指令所需要的时间表达式。顺序执行方式。仅“取指令”和“执行”重叠。“取指令” 、 “分析”和“执行”重叠。答：顺序执行方式1 21 21 2.T n(t2t3t)6ntn1i iii )tt(任任任仅“取指令”和“执行”重叠1 21 21 2.T6t 6t(n-1)(2t3t)(5n1)t1-ni ii)t(任任“取指令” 、 “分析”和“执行”重叠1 2 3 41 2 3 41 2 3 4.t 2t 3tt 2t 3tt 2t 3tT6t 6t
2、(n-1)(3t)(3n3)t1-nii)t(任2. 一条线性流水线有 4 个功能段组成，每个功能段的延迟时间都相等，都为t。开始 5 个任务，每间隔一个t 向流水线输入一个任务，然后停顿 2个t，如此重复。求流水线的实际吞吐率、加速比和效率。答：1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3、 16 17 18 19 20 21 22 23我们可以看出，在（7n+1）t 的时间内，可以输出 5n 个结果，如果指令的序列足够长（n） ，并且指令间不存在相关，那么，吞吐率可以认为满足： )n(t75)/17(t)n(5TP加速比为： )(20n/20t)17(4S从上面的时空图很容易看出，效率为： )(75/175t)n(45E3. 用一条 5 个功能段的浮点加法器流水线计算 。每个功能段的延迟10iiAF时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。答：首先需要考
4、虑的是“10 个数的和最少需要做几次加法？” ，我们可以发现，加法的次数是不能减少的：9 次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换律和结合律，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为 R，源操作数寄存器称为 A，最后结果寄存器称为 F，并假设源操作数已经在寄存器中，则指令如下：I1： R1A1+A2I2： R2A3+A4I3： R3A5+A6I4： R4A7+A8I5： R5A9+A10I6： R6R1+R2I7： R7R3+R4I8： R8R5+R6I9： FR7+R8这并不是唯一可能的计算方法。
5、假设功能段的延迟为 t。时空图如下（图中的数字是指令号）：1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21整个计算过程需要 21t，所以吞吐率为： t43.07t21TP加速比为： 29.5t9S效率为： 43.07t2159E4. 一条线性静态多功能流水线由 6 个功能段组成，加法操作使用其中的1、2、3、6 功能段，乘法操作使用其中的 1、4、5、6 功能段，每个功
6、能段的延迟时间均相等。流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。用这条流水线计算向量点积 ，i60ibaBA画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。答：我们安排运算次序如下：把中间结果寄存器称为 R，源操作数寄存器称为A、B，最后结果寄存器称为 F，并假设源操作数已经在寄存器中，则指令如下：I1： R0A0*B0 I8： R7R0+R1I2： R1A1*B1 I9： R8R2+R3I3： R2A2*B2 I10： R9R4+R5I4： R3A3*B3 I11： R10 R6+R7I5： R4A4*B4 I12： R11 R8+R9I6： R5A5*B
7、5 I13： FR10+R11I7： R6A6*B6假设功能段的延迟为 t。时空图如下（图中的数字是指令号）：1 2 3 4 5 6 7 8 9 10 11 12 131 2 3 4 5 6 71 2 3 4 5 6 78 9 10 11 12 138 9 10 11 12 131 2 3 4 5 6 7 8 9 10 11 12 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24整个计算过程需要 24t，所以吞吐率为： t54.0213TP加速比为： 17.26t47S效率为： 3.0t213E5. 一条有三个功能
8、段的流水线如下图。每个功能段的延迟时间均相等，都为t。其中功能段 S2 的输出要返回到它自己的输入端循环一次。如果每间隔一个t 向流水线的输入端连续输入新任务，问这条流水线会发生什么情况？求这条流水线能够正常工作的最大吞吐率、加速比和效率。有什么办法能够提高这条流水线的吞吐率，画出新的流水线。答：如果每间隔一个t 向流水线的输入端连续输入新任务，流水线 S2 功能段存在资源冲突。见下表：时间功能段 t1 t2 t3 t4 t5S1 X1 X2 X3 X4 X5S2 X1 X1,X2 X2,X3 X3,X4S1 S2 S3输入 输出t t tS3 X1 X2每间隔两个t 向流水线的输入端连续输入
9、新任务（如见下表所示）可获得最佳性能。时间功能段 t1 t2 t3 t4 t5 t6S1 X1 X2 X3S2 X1 X1 X2 X2 X3S3 X1 X2我们可以看出：在（2n+2）t 的时间内，可以输出 n 个结果，如果指令的序列足够长（n） ，并且指令间不存在相关，那么，吞吐率为： )(t21)n/2(t)n2(TP加速比为： )(/1t)(4S效率为： )n(32/3n2t)2(3nE如要提高这条流水线的吞吐率，可采用：将功能段 S2 重复设置一次，见下图：6. 一条有 4 个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns，它的预约表如下：时间流水段1 2 3 4 5
10、6 7S1 S2 S2输入t t tS3输出tS1 S2 S3 S4 写出流水线的禁止向量和初始冲突向量。 画出调度流水线的状态图。 求流水线的最小启动循环和最小平均启动距离。 求平均启动距离最小的恒定循环。 求流水线的最大吞吐率。 按照最小启动循环连续输入 10 个任务，求流水线的实际吞吐率。 画出该流水线各功能段之间的连接图。答： 禁止向量 F=（6,4,2） ；冲突向量 C=（101010） 。 简单循环 平均启动距离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） 4
11、i=1i7i=3i7i=5i=3i7i=5i=5i7101010111111101111101011C0C1C2C35，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 时： )n(t4182t7)1n(tt72TP 当任务数为奇数 2n+1 时
12、： )(tn/ttttnt1 流水线的最大吞吐率为： )s(M5.12ns04任 10 个任务的实际吞吐率：利用上式可得（偶数个任务）TP 10=1/4t=12.5M(任务 /s)。 该流水线的连接图为：7. 一条由 4 个功能段组成的非线性流水线的预约表如下，每个功能段的延迟时间都为 10ns。S1 S2 S3 S41234567输入输出时间流水段1 2 3 4 5 6S1 S2 S3 S4 写出流水线的禁止向量和初始冲突向量。画出调度流水线的状态图。求流水线的最小启动循环和最小平均启动距离。在流水线中插入一个非计算延迟功能段后，求该流水线的最佳启动循环及其最小平均启动距离。画出插入一个非计
13、算延迟功能段后的流水线预约表（5 行 8 列） 。画出插入一个非计算延迟功能段后的流水线状态变换图。分别计算在插入一个非计算延迟功能段前、后的最大吞吐率。如果连续输入 10 个任务，分别计算在插入一个非计算延迟功能段前、后的实际吞吐率。答：禁止向量 F=（5,2,1） ；冲突向量 C=（10011） 。简单循环 平均启动距离3 34 46 6最小启动循环为（3） ，最小平均启动距离为 3。10011 i=3i=4C0i6插入一个非计算延迟功能段后，最小平均启动距离为 2（因为预约表中每行至多 2 个） ，相应地可改进最小启动循环为（2） 。时间功能段 1 2 3 4 5 6 7 8S1 X X
14、S2 X XS3 XS4 X XD X X流水线的禁止向量为（1，3，7） ，流水线的冲突向量为 1000101，流水线的状态图如下：简单循环 平均启动距离2，4(C0-C1) 32，6(C0-C1) 42(C0-C1-C1) 24(C0-C0) 46(C0-C0) 65(C0-C2-C2) 55，4(C0-C2) 4.5100010110101011000111i=4,6i8i=4,6i8i=4,6i8 i=2i=2i=5C0C1C2i=55，6(C0-C2) 5.5流水线的最小启动循环为（2） ，最小平均启动距离为 2。插入前： )s/(103.ns10t3)1n(t6TP 7nmaxli
15、 任插入后： )s/(5ns102t2)1n(t6 7nmaxli 任连续输入 10 个任务，插入前的实际吞吐率为： )s/(103.ns103tt39t610TP 7任连续输入 10 个任务，插入后的实际吞吐率为： )s/(85.s26tt2t8 7任8. 在流水线处理机中，有独立的加法操作部件和乘法操作部件各一个，加法操作部件为 4 段流水线，乘法操作部件 6 段流水线，都在第一段从通用寄存器读操作数，在最后一段把运算结果写到通用寄存器中。每段的时间长度都相等，都是一个时钟周期。每个时钟周期发出一条指令。问可能发生哪几种数据相关? 写出发生相关的指令序列，分析相关发生的原因，并给出解决相关的具体办法。答：可能的数据相关性有：“先写后读” （RAW）相关 Read After 加法写。原因：还没有写好就已经读取寄存器中的数据了。DADD R1,R2,R3 ；（R2）（R3）（R1）
