1、1.6 某 台 主频为 400MHz 的 计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下： 指令类型 指令执行数量 平均时钟周期数 整数 45000 1 数据传送 75000 2 浮点 8000 4 分支 1500 2 求该计算机的有效 CPI、 MIPS 和程序执行时间。 解：（ 1） CPI (45000 1 75000 2 8000 4 1500 2) / 129500 1.776 （ 2） MIPS 速率 f/ CPI 400/1.776 225.225MIPS （ 3）程序执行时间 = (45000 1 75000 2 8000 4 1500 2)400=575
2、s 1.7 将计算机系统中某一功能的处理速度加快 10 倍，但该功能的处理时间仅为整个系统运行时间的 40%，则采用此增强功能方法后，能使整个系统的性能提高多少？ 解 由题可知： 可改进比例 = 40% = 0.4 部件加速比 = 10 根据 Amdahl 定律可知： 5 6 2 5.110 4.04.01 1 系统加速比采用此增强功能方法后，能使整个系统的性能提高到原来的 1.5625 倍。 1.8 计算机系统中有三个部件可以改进，这三个部件的部件加速比 为 ： 部件加速比 1=30； 部件加速比 2=20； 部件加速比 3=10 （ 1） 如果部件 1 和部件 2 的可改进比例均为 30%
3、，那么当部件 3 的可改进比例为多少时，系统加速比 才 可以达到 10？ （ 2） 如果三个部件的可改进比例分别为 30%、 30%和 20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？ 解：（ 1）在多个部件可改进情况下， Amdahl 定理的扩展： iiin SFFS )1( 1已知 S1 30， S2 20， S3 10， Sn 10， F1 0.3， F2 0.3，得： ）（）（ 10/20/0.330/0.30.30.3-1 110 33 FF 得 F3 0.36，即部件 3 的可改进比例为 36%。 （ 2）设系统改进前的执行时间为 T，则 3
4、 个部件改进前的执行时间为：（ 0.3+0.3+0.2） T = 0.8T， 不可改进部分的执行时间为 0.2T。 已知 3 个部件改进后的加速比分别为 S1 30， S2 20， S3 10，因此 3 个部件改进后的执行时间为： TTTTT n 04 5.0102.0203.0303.0 改进后整个系统的执行时间为： Tn = 0.045T+0.2T = 0.245T 那么系统中不可改进部分的执行时间在总执行时间中占的比例是： 82.0245.0 2.0 TT 1.9 假设某应用程序中有 4类操作，通过改进，各操作获得不同的性能提高。具体数据 如 下表 所示 ： 操作类型 程序中的数量 （百
5、万条指令） 改进前的执行时间 （周期） 改进后的执行时间 （周期） 操作 1 10 2 1 操作 2 30 20 15 操作 3 35 10 3 操作 4 15 4 1 （ 1）改进后，各类操作的加速比分别是多少？ （ 2）各类操作单独改进后，程序获得的加速比分别是多少？ （ 3） 4 类操作均改进后，整个程序的加速比是多少？ 解： 根据 Amdahl 定律SeFeFeSn )1( 1可得 操作类型 各类操作的 指令条数在程序中所占的比例 Fi 各类操作的加速比 Si 各类操作单独改进后，程序获得的加速比 操作 1 11.1% 2 1.06 操作 2 33.3% 1.33 1.09 操作 3
6、38.9% 3.33 1.37 操作 4 16.7% 4 1.14 4类操作均改进后，整个程序的加速比 2 .1 6)1( 1 iiin SFFS例 1-1 某一计算机用于商业外贸的事务处理，有大量的字符串处理操作。由于这种商务处理很普遍，有较大的市场，故而设计人员决定在下一代计算机的CPU 中加入字符串操作的功能。经测试应用软件调查发现，字符串操作的使用占整个程序运行时间的 50%。而增加此功能如用软件 (如微程序 )实现，则快 5 倍，增加 CPU 成本 1/5 倍；如果用硬件实现，则快 100 倍， CPU 成本增加到 5倍。问设计人员提出增加此功能是否恰当？如恰当则此功能应该用软件实现
7、还是用硬件实现？设 CPU 成本占整机成本的 1/3。 解： 首先来计算机器在两种情况下提高的性能和成本 性能比。 设： S为 CPU 未增加字符串功能时的 CPU 平均速度， Told 为此时运行程序的时间， Tnew 为增加字符串功能后程序运行的时间，则 从上面的计算分析看到增加字符串操作功能提高了整机的性能，两种方法均提高性能，且程度相近。但用硬件实现时成本性能比增加了 0.18 倍，而用软件实现时成本性能比却下降了 0.36 倍。 3.9 列举出下面循环中的所有相关，包括输出相关、反相关、真相关。for (i=2; i100; i=i+1) ai=bi+ai ;/* s1 */ ci+
8、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 */ 输出相关：无 反相关：无 真相关：
9、S1&S2 由于循环引入的相关： S4&S4（真相关）、 S1 &S4（真相关）、 S3 &S4（真相关）、 S1&S3（输出相关、反相关）、 S2&S3（反相关）。 3.12 有一指令流水线如下所示 （ 1） 求连续输入 10 条指令，该流水线的实际吞吐率和效率； （ 2） 该流水线的 “ 瓶颈 ” 在哪 一段？请采取 两 种不同的措施消除此 “ 瓶颈 ” 。对于你所给出的 两 种新的流水线，连续输入 10 条指令时，其实际吞吐率和效率 各是多少？ 解：（ 1） 2 2 0 0 ( n s )2 0 092 0 0 )1 0 050( 5 0t)1n(tT m a xm1iip i p e
10、l i n e )( n s2201TnTP 1p i p e li n e 4 5 . 4 5 %1154400TPm tTPEm1i i （ 2）瓶颈在 3、 4段。 入 1 2 3 4 出 5 0 n s 5 0 n s 1 0 0 n s 2 0 0 n s 变成八级流水线（细分） 8 5 0 ( n s )509850t1)(ntT m a xm1iip i p e l in e )( n s851TnTP 1p ip e lin e 5 8 . 8 2 %171084 0 0TPm tiTPEm1i 重复设置部件 )( n s851TnTP 1p ip e lin e 5 8 .
11、8 2 %1710885010400E 3.13 有一个流水线由 4 段组成，其中每当流经第 3 段时，总要在该段循环一次，然后才能流到第 4段。如果每段经过一次所需要的时间都是 ，问： （ 1） 当在流水线的输入端连续地每 时间输入任务时，该流水线会发生什么情况？ （ 2） 此流水线的最大吞吐率为多少？如果每 输入一个任务，连续处理ttt21 2 3_1 3_2 4_1 4_4入 出50ns 50ns 50ns 50ns 50ns 50ns1 2 3_1 3_2 4_1 4_2 4_3 4_4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7
12、 7 7 7 8 8 9 9 10 10 8 9 10 8 9 10 850ns 时间 段 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） 5 4 . 3 5 %925045TPE2310TnTp23T21TPp
13、 ip e li n ep ip e li n em a xtttt（ 3）重复设置部件 段 时间 1 2 3 4 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 t 23 1 2 3_1 3_2 4 t t t t t tt 751410TnTP p i p e l i n e吞吐率提高倍数tt231075 1.64 3.14 有一条 静态 多功能流水线由 5段组成，加法用 1、 3、 4、 5 段，乘法用1、 2、 5 段，第 3
14、段的时间为 2 t，其余各段的时间均为 t，而且流水线的输出可以直接返回输入端或 暂存于相应的流水寄存器中。现要在该流水线上计算 ，画出其时空图，并 计算其吞吐率、 加 速比和效率。 解： 首先，应选择适合于流水线工作的算法。对于本题，应先计算 A1 B1、A2 B2、 A3 B3和 A4 B4；再计算 (A1 B1) (A2 B2)和 (A3 B3) (A4 B4)；然后求总的结果。 其次，画出完成该计算的时空图，如 图 所示，图中阴影部分表示该段在工作。 1 2 3 4 5 乘法 加法 t t 2 t t t )(41 ii i BA 段 时间 1 1 2 3_1 3_2 4 1 1 1
15、1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 t 14 时间 段 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输 入 A 1 B 1 A 2 B 2 A 3 B 3 A 4 B 4 A B C D A B C D A B A B C D A B C D A =A 1 B 1 B=A 2 B 2 C=A 3 B 3 D =A 4 B 4 C D 17 18 由图可见，它在 18 个 t 时间
16、中 ，给出 了 7 个结果。所以吞吐率为： tTP 817如果不用流水线，由于一次求 积 需 3 t， 一次求 和 需 5 t，则产生上述 7个结果共需（ 4 5+3 3） t =29 t。所以加速比为 ： 该流水线的效率可由阴影区 的面积 和 5个段总时空区的 面积的 比值求得 ： 3.15 动态多功能流水线由 6个功能段组成，如下图： 其中， S1、 S4、 S5、 S6 组成乘法流水线， S1、 S2、 S3、 S6 组成加法流水线，各个功能段时间均为 50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算： 51i iii zyx（
17、1） 画出时空图； （ 2） 计算实际的吞吐率、加速比和效率。 解：机器一共要做 10 次乘法， 4 次加法。 S1 S2 S3 S4 S5 乘法 加法 S 6 61.18192 ttS223.0185 3354 E3.16 在 MIPS 流水线上运行如下代码序列： LOOP： LW R1， 0（ R2） DADDIU R1， R1， #1 SW R1， 0（ R2） DADDIU R2， R2， #4 DSUB R4， R3， R2 BNEZ R4， LOOP 其中 ： R3 的初值是 R2+396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄
18、存器的读操作和写操作可以通过寄存器文件 “ 定向 ” 。问： （ 1） 在没有任何其它定向（或旁路）硬件的支持下， 请 画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中 Cache，那么执行上述循环需要多少个时钟周期？ （ 2） 假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中 Cache，那么执行上述循环需要多少个时钟周 期？ （ 3） 假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，
19、但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。 解： 寄存器读写可以定向，无其他旁路硬件支持。排空流水线。 指令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22L W IF ID EX M WBD A D D IU IF S S ID EX M WBSW IF S S ID EX M WBD A D D IU IF ID EX M WBD S U B IF S S ID EX M WBB N E Z IF S S ID EX M WBL W IF S S IF ID EX
20、M WB第 i 次迭代（ i 0.98）开始周期： 1（ i 17） 总的时钟周期数：（ 98 17） 18 1684 有正常定向路径，预测分支失败。 指令 1 2 3 4 5 6 7 8 9 10 11 1 13 14 15LW IF ID EX M WBD A D D IU IF ID S EX M WBSW IF S ID EX M WBD A D D IU IF ID EX M WBD S U B IF ID EX M WBB N E Z IF ID EX M WBLW IF m iss m iss IF ID EX M WB 第 i 次迭代（ i 0.98）开始周期： 1（ i 10
21、） 总的时钟周期数：（ 98 10） 11 991 有正常定向路径。单周期延迟分支。 LOOP: LW R1， 0(R2) DADDIUR2， R2， #4 DADDIU R1， R1， #1 DSUB R4， R3， R2 BNEZ R4， LOOP SW R1， -4(R2) 第 i 次迭代 （ i 0.98） 开始周期 ： 1（ i 6 ） 总的时钟周期数 ：（ 98 6） 10 598 指令 1 2 3 4 5 6 7 8 9 10 11L W IF ID EX M WBD A D D IU IF ID EX M WBD A D D IU IF ID EX M WBD S U B IF
22、 ID EX M WBB N E Z IF ID EX M WBSW IF ID EX M WBL W IF ID EX M WB 3.17 假设各种分支指令数占所有指令数的百分比如下： 条件分支 20%（其中的 60%是分支成功的） 跳转和调用 5% 现有一 条段数 为 4 的流水线，无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能够被解析出来。第一个流水段是完全独立于指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是多少？ 解：没有控制相关时流水线的平均 CPI 1 存
23、在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支 要到第 3个时钟周期结束时才能被解析出来。所以： （ 1）若使用排空流水线的策略，则对于条件分支，有两个额外的 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 值给出，不必等待，所以无延迟：
