《计算机组织结构》课后作业参考答案-2013

 《计算机组织结构》课后作业习题参考答案  第一章 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=575s  1.7 将计算机系统中某一功能的处理速度加快10倍，但该功能的处理时间仅为整个系统运行时间的40%，则采用此增强功能方法后，能使整个系统的性能提高多少？ 解由题可知：可改进比例=40%=0.4部件加速比=10根据Amdahl定律可知：5625.1104.04.011系统加速比采用此增强功能方法后，能使整个系统的性能提高到原来的1.5625倍。  1.8 计算机系统中有三个部件可以改进，这三个部件的部件加速比为： 部件加速比1=30；   部件加速比2=20；  部件加速比3=10 （1）如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10？ （2）如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？ 解：（1）在多个部件可改进情况下，Amdahl定理的扩展： iiinSFFS)1(1 已知S1＝30，S2＝20，S3＝10，Sn＝10，F1＝0.3，F2＝0.3，得： ）（）（10/20/0.330/0.30.30.3-111033FF 得F3＝0.36，即部件3的可改进比例为36%。 （2）设系统改进前的执行时间为T，则3个部件改进前的执行时间为：（0.3+0.3+0.2）T = 0.8T，不可改进部分的执行时间为0.2T。 已知3个部件改进后的加速比分别为S1＝30，S2＝20，S3＝10，因此3个部件改进后的执行时间为：  TTTTTn045.0102.0203.0303.0'     改进后整个系统的执行时间为：Tn = 0.045T+0.2T = 0.245T 那么系统中不可改进部分的执行时间在总执行时间中占的比例是： 82.0245.02.0TT  第三章 3.9列举出下面循环中的所有相关，包括输出相关、反相关、真相关。 for (i=2; i100; i=i+1)  a[i]=b[i]+a[i]   ;/* s1 */   c[i+1]=a[i]+d[i] ; /* s2 */   a[i‐1]=2*b[i]  ; /* s3 */   b[i+1]=2*b[i] ;/* s4 */     解：展开循环两次： a[i] = b[i] + a[i] ; /* s1 */ c[i+1] = a[i] + d[i] ; /* s2 */ a[i‐1] = 2 * b[i] ; /* s3 */ b[i+1] = 2 * b[i] ; /* s4 */ a[i+1] = b[i+1] + a[i+1] ; /* s1’ */ c[i+2] = a[i+1] + d[i+1] ; /* s2 ‘*/ a[i] = 2 * b[i+1] ; /* s3 ‘*/ b[i+2] = 2 * b[i+1] ; /* s4 ‘*/  第一次循环引入的相关： 输出相关：无 反相关：无 真相关：S1&S2  由于第二次循环引入的相关：S4&S4’（真相关）、S1’&S4（真相关）、S3’&S4（真相关）、S1&S3’（输出相关、反相关）、S2&S3’（反相关）。  3.12 有一指令流水线如下所示 入1234出50ns50ns100ns200ns （1）求连续输入10条指令，该流水线的实际吞吐率和效率； （2）该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？ 解：（1） 2200(ns)2009200)10050(50t)1n(tTmaxm1iipipeline )(ns2201TnTP1pipeline  45.45%1154400TPmtTPEm1ii （2）瓶颈在3、4段。 变成八级流水线（细分）  850(ns)509850t1)(ntTmaxm1iipipeline )(ns851TnTP1pipeline 58.82%17108400TPmtiTPEm1i 重复设置部件 )(ns851TnTP1pipeline 58.82%1710885010400E 12 3‐1 3‐2 4‐1 4‐2 4‐3 4‐4 123_13_24_14_4入出50ns50ns50ns50ns50ns50ns123_13_24_14_24_34_411112222333344445555666677778899101089108910850ns时间段 3.14 有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算             ，画出其时空图，并计算其吞吐率、加速比和效率。  解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2、A3＋B3和A4＋B4；再计算(A1＋B1) ×(A2＋B2)和(A3＋B3) ×(A4＋B4)；然后求总的结果。 其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。  由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：                              tTP817                             如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t =29△t。所以加速比为：                                                                     该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：                                                                          3.15 动态多功能流水线由6个功能段组成，如下图：  12345乘法加法△t△t2△t△t△t)(41iiiBAS1S2S3S4S5乘法加法S6时间段12345012345678910111213141516输入A1B1A2B2A3B3A4B4ABCDABCDA×BA×BC×DA×B×C×DA=A1＋B1B=A2＋B2C=A3＋B3D=A4＋B4C×D171861.18192ttS223.01853354E 其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以昀快的方式用该流水计算：51iiiizyx （1）画出时空图； （2）计算实际的吞吐率、加速比和效率。 解：机器一共要做10次乘法，4次加法。  3.17 假设各种分支指令数占所有指令数的百分比如下： 条件分支 20%（其中的60%是分支成功的） 跳转和调用 5% 现有一条段数为4的流水线，无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能够被解析出来。第一个流水段是完全独立于指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是多少？  解：没有控制相关时流水线的平均CPI＝1 存在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支 要到第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 值给出，不必等待，所以无延迟： CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29  加速比     S=CPI/1 = 1.29     第五章 5.10 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数据Cache的失效率为4.82%，64KB的混合Cache的失效率为1.35%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？ 解：（1）根据题意，约75%的访存为取指令。因此，分离Cache的总体失效率为： （75%×0.39%）＋（25%×4.82%）＝1.50% 根据题意，容量为128KB的混合Cache的失效率为1.35%。也就是说，混合Cache的失效率比分离Cache的低一些。     （2）平均访存时间公式可以分为指令访问和数据访问两部分：       平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间＋数据失效率×失效开销）     根据这个公式，可求得两种结构的平均访存时间，分别为：   分离Cache的平均访存时间： 75%×（1＋0.39%×50）＋25%×（1＋4.82%×50）=1.7488（时钟周期）       混合Cache的平均访存时间： 75%×（1＋1.35%×50）＋25%×（1＋1＋1.35%×50）=1.9250（时钟周期） 因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。  5.11 给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？ （1）理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次； （2）两者Cache容量均为64KB，块大小都是32字节； （3）组相联Cache中的多路选择器使CPU的时钟周期增加了10％； （4）这两种Cache的失效开销都是80ns； （5）命中时间为1个时钟周期； （6）64KB直接映象Cache的失效率为1.4％，64KB两路组相联Cache的失效率