计算机系统结构复习资料

1.6某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002求该计算机的有效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=575s1.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TT1.9假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：操作类型程序中的数量（百万条指令）改进前的执行时间（周期）改进后的执行时间（周期）操作11021操作2302015操作335103操作41541（1）改进后，各类操作的加速比分别是多少？（2）各类操作单独改进后，程序获得的加速比分别是多少？（3）4类操作均改进后，整个程序的加速比是多少？解：根据Amdahl定律SeFeFeSn)1(1可得操作类型各类操作的指令条数在程序中所占的比例Fi各类操作的加速比Si各类操作单独改进后，程序获得的加速比操作111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.144类操作均改进后，整个程序的加速比2.16)1(1iiinSFFS[例1-1]某一计算机用于商业外贸的事务处理，有大量的字符串处理操作。由于这种商务处理很普遍，有较大的市场，故而设计人员决定在下一代计算机的CPU中加入字符串操作的功能。经测试应用软件调查发现，字符串操作的使用占整个程序运行时间的50%。而增加此功能如用软件(如微程序)实现，则快5倍，增加CPU成本1/5倍；如果用硬件实现，则快100倍，CPU成本增加到5倍。问设计人员提出增加此功能是否恰当？如恰当则此功能应该用软件实现还是用硬件实现？设CPU成本占整机成本的1/3。解：首先来计算机器在两种情况下提高的性能和成本性能比。设：S为CPU未增加字符串功能时的CPU平均速度，Told为此时运行程序的时间，Tnew为增加字符串功能后程序运行的时间，则从上面的计算分析看到增加字符串操作功能提高了整机的性能，两种方法均提高性能，且程度相近。但用硬件实现时成本性能比增加了0.18倍，而用软件实现时成本性能比却下降了0.36倍。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有一指令流水线如下所示（1）求连续输入10条指令，该流水线的实际吞吐率和效率；（2）该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？解：（1）2200(ns)2009200)10050(50t)1n(tTmaxm1iipipeline)(ns2201TnTP1pipeline45.45%1154400TPmtTPEm1ii（2）瓶颈在3、4段。入1234出50ns50ns100ns200ns变成八级流水线（细分）850(ns)509850t1)(ntTmaxm1iipipeline)(ns851TnTP1pipeline58.82%17108400TPmtiTPEm1i重复设置部件)(ns851TnTP1pipeline58.82%1710885010400E3.13有一个流水线由4段组成，其中每当流经第3段时，总要在该段循环一次，然后才能流到第4段。如果每段经过一次所需要的时间都是，问：（1）当在流水线的输入端连续地每时间输入任务时，该流水线会发生什么情况？（2）此流水线的最大吞吐率为多少？如果每输入一个任务，连续处理ttt2123_13_24_14_4入出50ns50ns50ns50ns50ns50ns123_13_24_14_24_34_411112222333344445555666677778899101089108910850ns时间段10个任务时的实际吞吐率和效率是多少？（3）当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务时，其吞吐率提高多少？解：（1）会发生流水线阻塞情况。第1个任务S1S2S3S3S4第2个任务S1S2stallS3S3S4第3个任务S1stallS2stallS3S3S4第4个任务S1stallS2stallS3S3S4（2）54.35%925045TPE2310TnTp23T21TPpipelinepipelinemaxtttt（3）重复设置部件段时间12341111122222333334444455555666667777788888999991010101010t23123_13_24ΔtΔtΔtΔtΔttt751410TnTPpipeline吞吐率提高倍数＝tt231075＝1.643.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)；然后求总的结果。其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。12345乘法加法△t△t2△t△t△t)(41iiiBA段时间1123_13_24111122222333334444455555666667777788888999991010101010t14时间段12345012345678910111213141516输入A1B1A2B2A3B3A4B4ABCDABCDA×BA×BC×DA×B×C×DA=A1＋B1B=A2＋B2C=A3＋B3D=A4＋B4C×D1718由图可见，它在18个△t时间中，给出了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，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：51iiiizyx（1）画出时空图；（2）计算实际的吞吐率、加速比和效率。解：机器一共要做10次乘法，4次加法。S1S2S3S4S5乘法加法S661.18192ttS223.01853354E3.16在MIPS流水线上运行如下代码序列：LOOP：LWR1，0（R2）DADDIUR1，R1，#1SWR1，0（R2）DADDIUR2，R2，#4DSUBR4，R3，R2BNEZR4，LOOP其中：R3的初值是R2+396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件“定向”。问：（1）在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？（2）假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？（3）假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。解：寄存器读写可以定向，无其他旁路硬件支持。排空流水线。指令12345678910111213141516171819202122LWIFIDEXMWBDADDIUIFSSIDEXMWBSWIFSSIDEXMWBDADDIUIFIDEXMWBDSUBIFSSIDEXMWBBNEZIFSSIDEXMWBLWIFSSIFIDEXMWB第i次迭代（i＝0..98）开始周期：1＋（i×17）总的时钟周期数：（98×17）＋18＝1684有正常定向路径，预测分支失败。指令12345678910111131415LWIFIDEXMWBDADDIUIFIDSEXMWBSWIFSIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBLWIFmissmissIFIDEXMWB第i次迭代（i＝0..98）开始周期：1＋（i×1