计算机系统结构第1-8章部分作业答案

计算机系统结构第1-8章部分作业答案第一章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(或MIPS)（3）程序执行时间=(45000×1＋75000×2＋8000×4＋1500×2)／400=575s1.9假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：操作类型程序中的数量（百万条指令）改进前的执行时间（周期）改进后的执行时间（周期）操作11021操作2302015操作335103操作41541（1）改进后，各类操作的加速比分别是多少？（2）各类操作单独改进后，程序获得的加速比分别是多少？（3）4类操作均改进后，整个程序的加速比是多少？解：根据Amdahl定律可得操作类型各类操作的指令条数在程序中所占的比例Fi各类操作的加速比Si各类操作单独改进后，程序获得的加速比操作111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.144类操作均改进后，整个程序的加速比：1.10第二章变长编码，哈夫曼编码第三章3.12有一条指令流水线如下所示：50ns50ns50ns100ns200ns1234（2）当任务流过第三段时要在该段循环一次，相当于要占用第三段2△t时间，则该流水线可看成是具有瓶颈段的线性流水线，瓶颈段即第三段，所需时间为2△t。每2△t输入一个任务，连续处理10个任务的时空图如下：则：（3）重复设置部件。重复的部件可并联在流水线上，也可串联于流水线中。如下图所示：采用并联方式时的时空图如下：吞吐率提高倍数＝＝1.64△t△t2△t△t1△t△t2△t△t12345△t解：此题容易出的问题是忽略静态流水线的特点，当加法任务流入流水线后紧跟着启动乘法任务。正确的做法是当所有加法任务完成从流水线流出后再启动乘法任务，同时还应注意到流水线中的第三段所用时间为2△t。（1）任务分析（2）画时空图123456712341234567123456718△t（3）计算流水线性能吞吐率：加速比：效率：3.18在CRAY-l机器上，按照链接方式执行下述4条向量指令(括号中给出了相应功能部件时间)，如果向量寄存器和功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果。V0←存储器 （从存储器中取数：７拍）V2←V0＋V1 （向量加：３拍）V3←V2＜A3 （按(A3)左移：４拍）V5←V3∧V4 （向量逻辑乘：２拍）解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。说明：若考虑数据从存储器送访存部件也有1拍延迟，则通过时间应为24拍，完成全部任务所用时间相应为87拍。3.19某向量处理机有16个向量寄存器，其中V0-V5种分别存放有向量A,B,C,D,E,F,向量的长度是8,向量各元素均为浮点数；处理部件采用两个单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似CRAY-1的链接技术，先计算(A+B)×C,在流水线不停的情况下，接着计算(D+E)×F。（1）求此链接流水线的通过时间是多少拍?（设寄存器出入各需1拍）（2）假如每排时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件的时间吞吐率为多少MFLOPS?解：（1）我们在这里假设A＋B的中间结果放在V6中，（A＋B）×C地最后结果放在V7中，D＋E地中间结果放在V8中，（D＋E）×F的最后结果放在V9中。具体实现参考下图：通过时间应该为前者（（A＋B）×C）通过的时间：T通过=(1+2+1)+(1+3+1)=9（拍）（2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通过时间了。=1200×10-9（s）题目中所问为吞吐率是多少MFLOPS，显然是让求以MFLOPS为单位的吞吐率。MFLOPS是指每秒完成多少百万次浮点运算，因此要明确所有任务中共多少浮点运算。显然共有4条浮点向量指令，而每条指令完成8个浮点运算，因此浮点运算总数为32个。所以：吞吐率：第四章4.4假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。（1）求程序执行的CPI。（2）相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？解：（1）程序执行的CPI=CPI基本+分支延迟=1+15%×[90%×（1-90%）×4=（1-90%）×3]=1.099（2）采用固定的2个时钟周期延迟时，程序执行的CPI=CPI基本+分支延迟=1+15%×2=1.3显然采用分支目标缓冲器时程序执行时间更少，即速度更快。4.5假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分之目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少？假设无条件分支指令不进入分支目标缓冲时程序执行的CPI为1.1解：无条件分支指令的特点是只要执行肯定分支成功。因此，对于进入分支目标缓冲器的无条件分支指令，分支预测的精度为100%，也就不会带来分支延迟。而没有进入分支目标缓冲器的无条件分支指令会带来一定分支延迟。首先要求出一条无条件分支指令的分支延迟是多少，不妨设为x个时钟周期。由题知无条件分支指令不进入分支目标缓冲时程序执行的CPI为1.1，而程序中没有无条件转移指令的CPI为1，因此有CPI=CPI无分支指令+无条件分支延迟=1+5%x=1.1所以x=2因此，允许无条件分支指令进入分支目标缓冲器时，CPI=CPI无分支指令+5%×（1-90%）×2=1.01第五章存储层次5.1解释下列术语（不要求写在作业本上，但应作为复习内容）存储系统全相联映像直接映像组相联映像写直达法写回法按写分配法不按写分配法命中时间失效率强制性失效容量失效冲突失效2：1经验规则相联度答：（答案略）5.2简述“Cache-主存”层次与“主存-辅存”层次的区别。答：存储层次比较项目“Cache—主存”层次“主存—辅存”层次目的为了弥补主存速度的不足为了弥补主存容量的不足存储管理实现全部由专用硬件实现主要由软件实现访问速度的比值（第一级比第二级）几比一几百比一典型的块（页）大小几十个字节几百到几千个字节CPU对第二级的访问方式可直接访问均通过第一级失效时CPU是否切换不切换切换到其它进程5.3地址映像方法有哪些？它们各有什么优缺点？答：（1）全相联映像。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。（2）直接映像。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。（3）组相联映像。组相联是直接映像和全相联的一种折中。5.4降低cache失效率有哪几种方法？答：（1）增加Cache块大小（2）提高相联度（3）增加Cache的容量（4）VictimCache（5）伪相联Cache（6）硬件预取技术（7）由编译器控制的预取（8）编译器优化。5.5简述减小cache失效开销的几种方法。答：(1)让读失效优先于写。(2)写缓冲合并。(3)请求字处理技术。(4)非阻塞Cache或非锁定Cache技术。(5)采用二级Cache。5.8组相联Cache的失效率比相同容量直接映像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）分离Cache的总体失效率：而容量为64KB的混合Cache的失效率略低一些，只有1.35%。（2）平均访存时间分析所以：平均访存时间分离＝75%×(1+0.39%×50)+25%×(1+4.82%×50)＝(75%×1.195)+(25%×3.41)＝1.74875平均访存时间混合＝75%×(1+1.35%×50)+25%×(1+1+1.35%×50)＝(75%×1.675)+(25%×2.675)＝1.925因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。5.11给定以下的假设，试计算直接映像Cache和2路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？（1）理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次。（2）两者Cache容量均为64KB，块大小都是32B。（3）组相联映像Cache中的多路选择器使CPU的时钟周期增加了10%。（4）这两种Cache的失效开销都是80ns。（5）命中时间为1个时钟周期。（6）64KB直接映像Cache的失效率为1.4%，64KB2路组相联Cache的失效率为1.0%。解：（1）平均访问时间＝命中时间＋失效率×失效开销平均访问时间1-路=2.0+1.4%×80=3.12ns平均访问时间2-路=2.0×(1+10%)+1.0%×80=3.0ns两路组相联的平均访问时间比较低（2）CPU时间=（CPU执行周期+存储等待周期）×时钟周期时间=IC（CPI执行+总失效次数/指令总数×失效开销）×时钟周期=IC（（CPI执行×时钟周期）+（每条指令的访存次数×失效率×失效开销×时钟周期））所以：CPU时间1路=IC(2.0×2+1.2×0.014×80)＝5.344ICCPU时间2路=IC(2.2×2+1.2×0.01×80)＝5.36IC相对性能比：5.36/5.344=1.003直接映象cache的访问速度比两路组相联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。因此这里选择两路组相联。第七章互连网络7.1解释下列术语（不要求写在作业本上，但应作为复习内容）线路交换分组交换静态网络动态网络互连网络互连函数网络直径结点度网络规模等分宽度对称网络答：答案略7.3设E为交换函数，S为均匀洗牌函数，B为蝶式函数，PM2I为移数函数，函数的自变量是十进制数表示的处理机编号。现在有32台处理机，其编号为0，1，2，….，31。（1）分别计算下列互连函数E2(12)S(8)B(9)PM2I+3(28)E0(S(4))S(E0(18))（2）用E0和S构成均匀洗牌交换网（每步只能使用E0和S一次），网络直径是多少？从5号处理机发送数据到7号处理机，最短路径要经过几步？请列出经过的处理几号。（3）采用移数网络构成互连网络，网络直径是多少？结点度是多少？与2号处理机距离最远的是几号处理机？解：（1）共有32台处理机，因此用log232=5比特表示各处理器编号。E2(12)十进制=E2(01100)二进制=（01000）二进制=(8)十进制S(8)十进制=S（01000）二进制=（10000）二进制=(16)十进制B(9)十进制=B（01001）二进制=（11000）二进制=(24)十进制PM2I+3(28)=(28+23)mod32=4E0(S(4))十进制=E0(S（00100））二进制=E0（01000）=（01001）二进制=(9)十进制S(E0(18))十进制=S(E0（10010））二进制=S（10011）=（00111）二进制=(7)十进制（2）2n个结点的均匀洗牌交换网的网络直径是2n-1，32个结点的均匀洗牌交换网