1、第 1 章 计算机系统结构的基本概念1.6 某台主频为 400MHz 的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：指令类型 指令执行数量 平均时钟周期数整数 45000 1数据传送 75000 2浮点 8000 4分支 1500 2求该计算机的有效 CPI、MIPS 和程序执行时间。解：（1）CPI (4500017500028000415002) / 1295001.776（2）MIPS 速率f/ CPI 400/1.776 225.225MIPS（3）程序执行时间= (4500017500028000415002) 400=575s 没有错误， 但是不严密，指令
2、数量的单位是 MIPS. 1.7 将计算机系统中某一功能的处理速度加快 10 倍，但该功能的处理时间仅为整个系统运行时间的 40%，则采用此增强功能方法后，能使整个系统的性能提高多少？解 由题可知： 可改进比例 = 40% = 0.4 部件加速比 = 10根据 Amdahl 定律可知： 562.104.1系 统 加 速 比采用此增强功能方法后，能使整个系统的性能提高到原来的 1.5625 倍。1.8 计算机系统中有三个部件可以改进，这三个部件的部件加速比为：部件加速比 1=30； 部件加速比 2=20； 部件加速比 3=10（1） 如果部件 1 和部件 2 的可改进比例均为 30%，那么当部件
3、 3 的可改进比例为多少时，系统加速比才可以达到 10？（2） 如果三个部件的可改进比例分别为 30%、30% 和 20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？解：（1）在多个部件可改进情况下，Amdahl 定理的扩展：iinSFS)1(已知 S130，S 220，S 310 ，S n10，F 10.3，F 20.3 ，得： ）（）（ 10/0.3/.0.-13得 F30.36，即部件 3 的可改进比例为 36%。（2）设系统改进前的执行时间为 T，则 3 个部件改进前的执行时间为：（0.3+0.3+0.2） T = 0.8T，不可改进部分的执行时间
4、为 0.2T。已知 3 个部件改进后的加速比分别为 S130，S 220，S 310，因此 3 个部件改进后的执行时间为： TTTn045.03. 改进后整个系统的执行时间为：Tn = 0.045T+0.2T = 0.245T那么系统中不可改进部分的执行时间在总执行时间中占的比例是： 82.045.T1.9 假设某应用程序中有 4 类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：操作类型 程序中的数量（百万条指令） 改进前的执行时间 （周期） 改进后的执行时间 （周期）操作 1 10 2 1操作 2 30 20 15操作 3 35 10 3操作 4 15 4 1（1）改进后，各
5、类操作的加速比分别是多少？（2）各类操作单独改进后，程序获得的加速比分别是多少？（3）4 类操作均改进后，整个程序的加速比是多少？解：根据 Amdahl 定律 可得SeFSn)1(操作类型 各类操作的指令条数在 程序中所占的比例 Fi各类操作的加速比 Si 各类操作单独改进后， 程序获得的加速比操作 1 11.1% 2 1.06操作 2 33.3% 1.33 1.09操作 3 38.9% 3.33 1.37操作 4 16.7% 4 1.144 类操作均改进后，整个程序的加速比： 2.16)1(iinSFS讨论：这道题答案我认为是错了。我的参考答案：算法一，用最原始的加速比公式：加速比 = 改进
6、前执行时间/改进后执行时间 = （10*2+30*20+35*10+15*4）/ （10*1+30*15 + 35*3+15*1） = 1030/580 = 1.78算法二，部件比例。注意定义：部件比例的定义是 可改进的部分的执行时间在总的执行时间中所占的比例。因此操作类型 各类操作的在总的执行 时间中所占的比例 Fi各类操作的加速比 Si操作 1 20/1030 2操作 2 600/1030 20/15操作 3 350/1030 10/3操作 4 60/1030 4/1加速比 = iinSFS)1(= 1.78第 3 章 流水线技术3.4 设一条指令的执行过程分成取指令、分析指令和执行指令三
7、个阶段，每个阶段所需的时间分别为t、t 和 2t 。分别求出下列各种情况下，连续执行 N 条指令所需的时间。（1）顺序执行方式；（2）只有“取指令”与“执行指令”重叠；（3） “取指令” 、 “分析指令”与“执行指令”重叠。解：（1）每条指令的执行时间为：tt 2t4t连续执行 N 条指令所需的时间为： 4Nt（2）连续执行 N 条指令所需的时间为： 4t3（N-1） t（3N1）t（3）连续执行 N 条指令所需的时间为： 4t2（N-1） t（2N2）t3.9 列举出下面循环中的所有相关，包括输出相关、反相关、真相关。for (i=2; i100; i=i+1)ai=bi+ai ;/* s1
8、 */ci+1=ai+di ; /* s2 */ai-1=2*bi ; /* s3 */bi+1=2*bi ;/* s4 */解：展开循环两次：ai = bi + ai ; /* s1 */ci+1 = ai + di ; /* s2 */ai-1 = 2 * bi ; /* s3 */bi+1 = 2 * bi ; /* s4 */ai+1 = bi+1 + ai+1 ; /* s1 */ci+2 = ai+1 + di+1 ; /* s2 */ai = 2 * bi+1 ; /* s3 */bi+2 = 2 * bi+1 ; /* s4 */输出相关：无反相关：无真相关：S1&S2由于循环
9、引入的相关：S4&S4 （真相关） 、S1 &S4（真相关） 、S3&S4 （真相关） 、S1&S3（输出相关、反相关） 、S2&S3 （反相关） 。3.12 有一指令流水线如下所示 入 1 2 3 4 出 50ns 50ns 10ns 20ns （1） 求连续输入 10 条指令，该流水线的实际吞吐率和效率；（2） 该流水线的“ 瓶颈”在哪一段？请采取两种不同的措施消除此 “瓶颈”。对于你所给出的两种新的流水线，连续输入 10 条指令时，其实际吞吐率和效率各是多少？解：（1） 20(ns)209)5t1(tTmaxm1iipieln)(nsP1piel 45.%0TPmtE1ii （2） 瓶颈
10、在 3、4 段。 变成 八级流水线（细分）850(ns)9t1)(tTmaxm1iipieln)(ns85P1piel58.2%1704TPmtE1i 重复设置部件1 23-13-24-14-24-34-4 耲 弳 1 弳 耲 弴 耱 弴 4 獮 獮 獮 獮 獮 獮 )(ns851TnP1piel.82%7040E3.13 有一个流水线由 4 段组成，其中每当流经第 3 段时，总要在该段循环一次，然后才能流到第 4 段。如果每段经过一次所需要的时间都是 t，问：（1） 当在流水线的输入端连续地每 t时间输入任务时，该流水线会发生什么情况？（2） 此流水线的最大吞吐率为多少？如果每 2输入一个任
11、务，连续处理 10 个任务时的实际吞吐率和效率是多少？（3） 当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理 10 个任务时，其吞吐率提高多少？解：（1）会发生流水线阻塞情况。第 1 个任务 S1 S2 S3 S3 S4第 2 个任务 S1 S2 stall S3 S3 S4第 3 个任务 S1 stall S2 stall S3 S3 S4第 4 个任务 S1 stall S2 stall S3 S3 S4（2）1 23_1 24_1 24_3 1 1 1 22233 3 4 4455 5 6 6677 7 8 910 89 1089 10850ns 时 间 段 段 时 间 1 2
12、3 4 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 t 2354.3%9205TPE1np32Pipelielmaxttt（3）重复设置部件 tt75140TnPpiel吞吐率提高倍数 1.64t2310753.14 有一条静态多功能流水线由 5 段组成，加法用 1、3、4、5 段，乘法用 1、2、5段，第 3 段的时间为 2t，其余各段的时间均为 t ，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。 1 2 3 4 5 乘 法 加
13、法 t t 2 t t t )(41iiiBA1 2 3_1 3_2 4 t t t t t 段 时 间 1 2 3_1 2 4 1 1 22 23 3 3 44 45 5 5 66 67 7 7 88 89 9 9 10 10 10 t 14解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1B 1、A 2B 2、A 3B 3 和 A4B 4；再计算(A 1B 1) (A2B 2)和(A 3B 3) (A4B 4)；然后求总的结果。其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。由图可见，它在 18 个t 时间中，给出了 7 个结果。所以吞吐率为：tTP81如果
14、不用流水线，由于一次求积需 3t，一次求和需 5t，则产生上述 7 个结果共需（45+33）t =29 t。所以加速比为：该流水线的效率可由阴影区的面积和 5 个段总时空区的面积的比值求得：3.15 动态多功能流水线由 6 个功能段组成，如下图：其中，S1、S4、S5 、S6 组成乘法流水线，S1、S2、S3 、S6 组成加法流水线，各个功能段时间均为 50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算： 51iizyx（1） 画出时空图；（2） 计算实际的吞吐率、加速比和效率。解：机器一共要做 10 次乘法，4 次加法。S1 S2 S3
15、 S4 S5 乘 法 加 法 S6 时 间 段 1 2 3 4 5 0 2 3 4 5 6 7 8 9 10 12 3 14 5 16 输入 A1B 2 3 AB4 A B C D AB CD ABAB CD ABCD A=1 B1 2 2C3 3 D=A4 B4CD 7 18 61.892tS23.014E3.16 在 MIPS 流水线上运行如下代码序列：LOOP： LW R1， 0（R2 ）DADDIU R1，R1，#1SW R1， 0（R2 ）DADDIU R2，R2，#4DSUB R4，R3，R2BNEZ R4，LOOP其中：R3 的初值是 R2+396。假设：在整个代码序列的运行过程
16、中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件“定向”。问：（1） 在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中 Cache，那么执行上述循环需要多少个时钟周期？（2） 假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？（3） 假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进行调度，你可以重新组织指
17、令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。解：寄存器读写可以定向，无其他旁路硬件支持。排空流水线。指 令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22LW IF ID EX M WBDADDIU IF S S ID EX M WBSW IF S S ID EX M WBDADDIU IF ID EX M WBDSUB IF S S ID EX M WBBNEZ IF S S ID EX M WBLW IF S S IF ID EX M
18、 WB第 i 次迭代（i0.98）开始周期：1（i17）总的时钟周期数：（9817）181684有正常定向路径，预测分支失败。指 令 1 2 3 4 5 6 7 8 9 10 11 1 13 14 15LW IF ID EX M WBDADDIU IF ID S EX M WBSW IF S ID EX M WBDADDIU IF ID EX M WBDSUB IF ID EX M WBBNEZ IF ID EX M WBLW IF miss miss IF ID EX M WB第 i 次迭代（i0.98）开始周期：1（i10）总的时钟周期数：（9810）11991有正常定向路径。单周期延迟分
19、支。LOOP: LW R1，0(R2)DADDIU R2，R2，#4DADDIU R1，R1，#1DSUB R4，R3，R2BNEZ R4，LOOPSW R1，-4(R2)第 i 次迭代（i 0.98）开始周期：1（i 6 ）总的时钟周期数：（986）10598指 令 1 2 3 4 5 6 7 8 9 10 11LW IF ID EX M WBDADDIU IF ID EX M WBDADDIU IF ID EX M WBDSUB IF ID EX M WBBNEZ IF ID EX M WBSW IF ID EX M WBLW IF ID EX M WB3.17 假设各种分支指令数占所有指
20、令数的百分比如下：条件分支 20%（其中的 60%是分支成功的）跳转和调用 5%现有一条段数为 4 的流水线，无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能够被解析出来。第一个流水段是完全独立于指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是多少？解：没有控制相关时流水线的平均 CPI1存在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第 3 个时钟周期结束时才能被解析出来。所以：（1）若使用排空流水线的策略，则对于条件分支，有两个额外的
21、stall，对无条件分支，有一个额外的 stall：CPI = 1+20%*2+5%*1 = 1.45 加速比 S=CPI/1 = 1.45（2） 若使用预测分支成功策略，则对于不成功的条件分支，有两个额外的 stall，对无条件分支和成功的条件分支，有一个额外的 stall 1：CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比 S=CPI/1 = 1.33（3）若使用预测分支失败策略，则对于成功的条件分支，有两个额外的 stall；对无条件分支，有一个额外的 stall；对不成功的条件分支，其目标地址已经由 PC 值给出，不必等待，所以无延迟：CPI =
22、1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比 S=CPI/1 = 1.293.18 在 CRAY-1 机器上，按照链接方式执行下述 4 条向量指令（括号中给出了相应功能部件的执行时间） ，如果向量寄存器和功能部件之间的数据传送需要 1 拍，试求此链接流水线的通过时间是多少拍？如果向量长度为 64，则需多少拍才能得到全部结果？V0存储器 （从存储器中取数：7 拍）V2V 0+V1 （向量加：3 拍）V3V 2A3 （按（A 3）左移：4 拍）V5V 3V4 （向量逻辑乘：2 拍）解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。存 储 器访 存向 量 加 左 移 向 量 逻辑 乘V0 V1 V2 V3 V4 V5A3（ 拍 ） （ （ 拍 ） ） （） （） （ （ 通 过总 共通 过 862164T 2311437
