计算机系统结构第二版张晨曦考前资料大题大全看完必过.doc

1. 将计算机系统中某一功能的处理速度加快15倍，但该功能的处理时间仅占整个系统运行时间的40%，则采用此方法改进后，能使整个系统的性能提高多少？注意：计算的是系统的加速比。用的是系统改进前的时间/系统改进后的时间。引入两个概念：可改进比例：Fe部件加速比：Se 公式是推倒出来的。解：由题意知：Se=15，Fe=40%=0.4根据Amdahl定律可知：Sn=采用此方法改进后，能使整个系统的性能提高原来的1.6倍2. 假设FP指令的比例为25%，其中，FPSQR占全部指令的比例为2%，FP操作的CPI为4，FPSQR操作的CPI为20，其他指令的平均CPI为1.33。现有两种改进方案，第一种是把PFSQR操作的CPI减至2，第二种是把所有FP操作的CPI减至2，试比较两种方案对系统性能的提高程度。（求得是系统的平均时钟周期CPI）注意几个公式：执行程序所需的时钟周期数：平均时钟周期*指令条数这个公式改进任何一个参数都可以提高CPU性能，但是这些参数往往是互相关联的，很难做到能单独的改进某一个参数指标而不影响其他的两个指标。所以用到了CPU时钟周期数。解：没有改进之前，每条指令的平均时钟周期CPI为：（1） 采用第一种方案：所有FP操作的CPI由CPIfp=4减至CPIfp=2，则整个系统的平均时钟周期为：CPI1=CPI-(CPIfp-CPIfp)x25%=2-(4-2)x25%=1.5（2） 采用第二种方案：将FPSQR操作的CPI由20减至2，则整个系统的指令的平均时钟周期数为：CPI2=CPI-(CPIfpsqr-CPIfpsqr)x2%=2-(20-2)x2%=1.64综上：从降低整个系统的指令平均时钟周期程度来看，第二种方案优于第一种方案。课后题：3.将计算机系统中某一功能的处理速度加快20倍，但该功能的处理时间仅占整个系统运行时间的40%，则采用该方法改进后，能使整个系统的性能提高多少？4.假设浮点数指令（FP）的比例为30%，其中浮点数平方根的指令（FPSQR）占全部指令的4%，FP操作的CPI为5,FPSQR操作的CPI 为，其他指令的平均CPI 为1.25。现在有两种改进方案。第一种是把FPSQR操作的CPU减至3。第二种改进方案是把所有FP操作的CPI减至3。试比较两种方案对系统性能的提高。第二章大题1. 流水线的性能指标吞吐率：TP(Through Put)：是指单位时间内流水线所完成的任务数量或输出结果的数量以上是在各段执行时间都相等的情况下的吞吐率。各段时间不相等时，流水线的最大吞吐量与实际吞吐率都有时间最长的段决定，这个段就成了这个流水线的瓶颈。这是瓶颈段一直处于忙碌状态，而其他各段在许多时间内都是空闲的硬件使用率低消除瓶颈段的方法：（1） 细分瓶颈段把瓶颈段细分成三个子流水功能段，从而使流水线各段的处理时间都相等。串行执行。（2） 重复设置瓶颈段根据前面段的多少设置一样多的瓶颈段，然后达到并行执行的效果，当然也要增加硬件设施。2. 流水线的加速比是指使用顺序处理一批任务所用的时间与流水线使用流水处理方式处理同一批任务所用的时间之比3. 流水线的效率即流水线设备的利用率。它是指流水线中设备实际使用时间与整个运行时间的比值每个段的效率：例3.1要在图3.3所示的静态流水线上计算，流水线的输出可以直接返回输入端或者暂存于相应的流水线寄存器中，试计算其吞吐率、加速比、与效率。解：首先选择合适的流水线工作算法。对于本题的算法如下：(1) 先计算加法a=A1+B1b=A2+B2c=A3+B3d=A4+B4(2) 再计算乘法e=axbf=cxd（3） 最后计算结果g=exf画出时空图（1） 由图可知：它在18个的时间中，给出了7个结果，所以吞吐率为：（2） 如果不用流水线，由于一次求与需6，一次求积需4，则产生上述7个结果共需要（4x6+3x4）=36所以加速比为（3） 该流水线的效率可以由阴影区的面积与8个段总时空区的面积的比值求得 例3.2有一条动态多功能流水线由5段组成，如图所示。加法用1.3.4.5段，乘法用1.2.5段。且第四段的时间为2t，其余各段时间为t，流水线的输出可以直接返回输入端或者暂存于相应的流水线寄存器中。若在该流水线计算，试计算其吞吐率、加速比、与效率。解：首先应该选择适合流水线工作的算法。对于本题算法如下： 先计算：再计算：最后计算：画出时空图如下图所示： （1） 由图所示，它在16个t的时间中给出了7个结果，所以吞吐率为：（2） 如果不使用流水线，由于求一次积需3t，一次求与需5t，则产生上述7个结果共需要（4x3+3X5）t=27t。所以加速比为：（3） 该流水线的效率可由阴影区的面积与5个段总时空区的面积的比值求得：3.一指令流水线如下所示（1） 求连续输入10条指令，该流水线的实际吞吐率与效率；（2） 该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率与效率各是多少？解：（1）（2）瓶颈在3、4段。n 变成八级流水线（细分）123-13-24-14-24-34-4n 重复设置部件3.14 有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2t，其余各段的时间均为t，而且流水线的输出可以直接返回输入端或 暂存于相应的流水寄存器中。现要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比与效率。解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1B1、A2B2、A3B3与A4B4；再计算(A1B1) ×(A2B2)与(A3B3) ×(A4B4)；然后求总的结果。其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。由图可见，它在18个t时间中，给出了7个结果。所以吞吐率为：如果不用流水线，由于一次求积需3t，一次求与需5t，则产生上述7个结果共需（4×5+3×3）t =29t。所以加速比为：该流水线的效率可由阴影区的面积与5个段总时空区的面积的比值求得：3.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。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作与写操作可以通过寄存器文件“定向”。问：（1） 在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？（2） 假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Cache，那么执行上述循环需要多少个时钟周期？（3） 假设该流水线有正常的定向路径与一个单周期延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。解：寄存器读写可以定向，无其他旁路硬件支持。排空流水线。 第i次迭代（i0.98）开始周期：1（i×17）总的时钟周期数：（98×17）181684有正常定向路径，预测分支失败。 第i次迭代（i0.98）开始周期：1（i×10） 总的时钟周期数：（98×10）11991 有正常定向路径。单周期延迟分支。 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 ）总的时钟周期数：（98×6）10598 2.13 在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVE、ADD与MUL操作分别需要2个、3个与4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。 k： MOVE R1，R0 ；R1 (R0)k+1： MUL R0，R2，R1 ；R0 (R2)×(R1)k+2： ADD R0，R2，R3 ；R0 (R2)+(R3)画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？ 解：由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二与存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需要9个时钟周期。链接技术：当前一条指令的结果寄存器是后一条指令的源寄存器、且不存在任何其他冲突时：（不存在功能部件冲突、不存在源寄存器冲突、不存在目的寄存器冲突如下：）就可以采用连接技术来提高性能。V3<-V1+V2V5<-V3xV4向量流水线链接：是指具有先写后读相关的两条指令，在不出现功能部件冲突与其他Vi冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。由于同步的要求，连接时Gray-1中把向量数据元素送往向量功能部件以及把结果存入向量寄存器都需要一拍时间。从存储器把数据送入访存功能部件也需要一拍时间。例4-1考虑在Cray-1上利用链接技术执行以下4条执行；V0<-存储器/访存取向量7拍V2<-V0+V1/向量加 3拍V3<-V2<A3/A3左移 4拍V5<-V3V4/与操作：2拍画出链接示意图，并求该链接流水线的通过时间，如果向量长度为64，则需要多少拍才能得到全部结果。解：对于这4条指令分析可知：它们即不存在部件冲突，也不存在寄存器冲突，相邻两条指令之间都存在先写后读相关，因而可以把访存流水线、向量加流水线、向量移位流水线以及向量逻辑运算流水线连接成一个较长的流水线。该链接流水线的通过时间为：通过时间=1+7+1+1+3+1+1+4+1+1+2=23 在向量长度为64的情况下，得到所有结果共需要：23+64=87拍。例4.2若要在Cray-1上进行向量运算：D=Ax（B+C），假设向量长度N<=64,向量元素为浮点数，且向量B/C已经存放在V0与V1中。画出链接示意图，并分析非链接执行与链接执行两种情况下的执行时间。解：用以下三条向量完成上述运算。v3<-A /访存取得向量AV2=V0+V1/ 向量B与向量C进行浮点加V4<-V2XV3 /浮点乘，结果存入V4分析：第1.2条向量既没有Vi冲突，也没有功能部件冲突，可以并行执行。第三条指令与第二条指令之间均存在先写后读相关。而且不存在功能部件冲突，因此可以将第三条与第（1）（2）条指令链接执行。（1） 如果全用串行的方式，执行时间为：(1+6+1)+(N-1)+(1+6+1)+(N-1)+(1+7+1)+(N-1)=3N+22（拍）（2） 如果前两条指令并行执行，然后再串行执行：(1+6+1)+(N-1)+(1+7+1)+(N-1)=2N+15（拍）（3） 如果前两条指令并行执行，并且与第三条指令链接执行：(1+6+1)+(1+7+1)+(N-1)=N+16（拍）课后题4.5：3.18在CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的执行时间），如果向量寄存器与功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？V0存储器（从存储器中取数：7拍）V2V0+V1（向量加：3拍）V3V2<A3（按（A3）左移：4拍）V5V3V4（向量逻辑乘：2拍）解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。课后题4.6：3.在CRAY-1机器上，按照链接方式执行下述5条向量指令（括号中给出了相应功能部件的执行时间），如果向量寄存器与功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？V0存储器（从存储器中取数：7拍）V2V0+V1（向量加：3拍）V3V2<A3（按（A3）左移：5拍）V5V3V4（向量逻辑乘：2拍）存储器<-V5练习题：指出下列指令存在什么冲突？请给后消除冲突的方法及消除冲突后的指令代码？（1） DIV.D F0, F2, F4（2） ADD.D F6, F0, F8（3） S.D F6, 0(R1)（4） SUB.D F8, F10, F14（5） MUL.D F6, F10, F8ADD与SUB存在反相关，会引起WAR读后写相关ADD与MUL存在输出相关，会引起WAW写后写相关Tomasulo算法(托马苏洛算法)可以通过使用寄存器重命名来消除。DIV.D F0, F2, F4ADD.D T2, F0, F8 ; 滞后S.D T2, 0(R1) ; 滞后SUB.D T1, F10, F14 ; 超前MUL.D F6, F10, T1 ; 超前Cache性能分析：不命中率与平均访问时间都不如 CPU 时间这个指标好： 例7.1：假设Cache不命中开销为50个时钟时期，当不考虑存储器停顿时，所有的指令的执行时间都是2.0个时钟周期，访问Cache的不命中率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。解：直接用公式计算 例7.2考虑两种不同组织结构的Cache；直接映像Cache与两路组相连Cache。假设：1. 理想Cache（命中率为100%）情况下CPI为2.0，时钟周期为2ns，平均，平均每条指令访存1.3次2. 两种Cache容量均为64KB，块大小都是32字节。3. 在组相连Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍，这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响。4. 这两种结构的不命中开销都是70ns。5. 命中时间为1个时钟周期（2ns），64kb直接映像cache的不命中率为1.4%。相同容量的两路组相连cache的不命中率为1.0%。试问它们对CPU的性能有什么影响？先求平均访存时间，然后再计算CPU性能。对于平均访存时间： =2.98（ns）平均访存时间2路=命中时间+不命中率x不命中开销=2.0+（0.010x70）=2.90（ns）两路组相连的Cache的平均访存时间比较低。CPU性能为CPU时间=ICX（CPIx时钟周期时间+每条指令的平均访存次数x不命中率x不命中开销x时钟周期时间）用70ns代替“不命中开销x时钟周期时间”，并用CPI=2，时钟周期时间=2，每条指令的平均访存时间=1.3带入的CPU时间1路=ICX2.0x2+（1.3x0.014x70）=5.17xICCPU时间2路=ICX2.0x2x1.10+（1.3x0.010x70）=5.31xIC相对性能比为：与平均访问时间的比较结果相反，直接映像Cache的平均性能稍好一些，这是因为在两路组相连的情况下，虽然不命中次数减少了，但所有指令的时钟周期时间都增加了10%。由于CPU是我们进行评价的标准。而且直接映像Cache更简单，所以本例中直接映像Cache是更好的选择。7.6组相连Cache的不命中率比相同容量直接映像的不命中率低，由此能否得出结论，采用组相连一定能带来性能上的提高？为什么？答：不一定。因为组相连命中率的提高是以增加命中时间为代价的，组相连需要增加多路选择开关。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.49% 容量为64KB的混合Cache的失效率略低一些，只有1.35%。    （2）平均访存时间公式可以分为指令访问与数据访问两部分：       平均访存时间指令所占的百分比×（读命中时间读不命中率×不命中开销）+数据所占的百分比×（数据命中时间数据不命中率×不命中开销）     所以，两种结构的平均访存时间分别为：   分离Cache的平均访存时间75%×（1+0.39%×50）+25%×（1+4.82%×50）=1.745 混合Cache的平均访存时间75%×(1+1.35%×50)+25%×(1+1+1.35%×50)=1.925因此，尽管分离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的失效率为1.0。 解：  平均访问时间命中时间不命中率×不命中开销 平均访问时间1-路=2.0+1.4% *80=3.12ns 平均访问时间2-路=2.0*(1+10%)+1.0% *80=3.0ns 两路组相联的平均访问时间比较低 CPU时间=ICX（CPIx时钟周期时间+每条指令的平均访存次数x不命中率x不命中开销x时钟周期时间）用80ns代替“不命中开销x时钟周期时间”，并用CPI=2，时钟周期时间=2，每条指令的平均访存时间=1.3带入的CPU 时间1路=IC(2.0*2+1.2*0.014*80)5.344IC CPU 时间2路=IC(2.2*2+1.2*0.01*80)5.36IC 相对性能比： 二路组相连映像的平均访问时间较好，而直接映像的CPU性能较好。6.10 在有Cache的计算机系统中，进行I/O操作时，会产生哪些数据不一致问题？如何克服？（1）存储器中可能不是CPU产生的最新数据，所以I/O系统从存储器中取出来的是陈旧数据。 （2）I/O系统与存储器交换数据之后，在Cache中，被CPU使用的可能就会是陈旧数据。 第一个问题可以用写直达Cache解决。 第二个问题操作系统可以保证I/O操作的数据不在cache中。如果不能，就作废Cache中相应的数据。通道流量是指：一个通道在传送期间，单位时间内能够传送的数据量。所用单位一般是字节/秒。也称为通道吞吐率，通道数据传输率等。一个通道在满负荷工作状态下的流量称为通道最大流量。通道最大流量主要与通道的种类，通道选择设备一次所用的时间，以及传送一个字节所用的时间等因素有关。用到的参数：:设备选择时间：从通道响应设备发出的数据传送请求开始，到通道实际为这台设备传送数据所需要的时间。:传送一个字节所用的时间。p：在一个通道上连接的设备台数，且这些设备同时都在工作.n:每台设备传送的字节数，这里假设每台设备传送的字节数都相同。k：数组多路通道传输一个数据块中包含的字节数。在一般情况下，k<n.对于磁盘、磁带等次表面存储器，通常k=512。通道每连接一台外设，只传送一个字节，然后又选择另一台设备连接，并传送一个字节。如此反复：p台设备每台传送n个数据总共所需的时间为：=(+)xpxn其最大流量为：实际流量为：设某个数组多路通道设备选择时间TS为1s，传送一个字节数据所需的时间TD为1s，一次传送定长数据块的大小k为512 B。现有8台外设的数据传输速率分别如表63所示，问哪些外设可连接到该通道上正常工作？9.设某个字节多路通道的设备选择时间Ts为9.8s，传送一个字节的数据所需的时间TD为0.2s。若某种低速外设每隔500s发出一次传送请求，请问：该通道最多可连接多少台这种外设？（1）字节多路通道的最大流量为：字节多路通道的实际流量为：其中，p为通道连接的外设台数，fi为外设i的数据传输速率。因为连接的是同样的外设，所以f1=f2=fp=f，故有fbyte=pf。通道流量匹配的要求有：fmax-bytefbyte即有：；可得：已知Ts = 9.8s，TD = 0.2s，1/f = 500s，可求出通道最多可连接的设备台数为：第 22 页