计算机系统结构第1

1、计算机系统结构第1-8章部分作 业答案第一章1.6某台主频为400MHz的计算机执行标准 测试程序，程序中指令类型、执行数量和平均时 钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002求该计算机的有效CPI、MIPS和程序 执行时间。解：(1)CPI = (45000X 1 + 75000X 2+ 8000 X 4+ 1500X 2) / 129500= 1.776(2) MIPS 速率=f/ CPI = 400/1.776 =225.225MIPS(或 5180 mips)(3)程序执行时间=(45000 X 1 + 75000

2、X 2+ 8000X 4+ 1500X 2)/400=575 s1.9假设某应用程序中有4类操作，通过改 进，各操作获得不同的性能提高。具体数据如下 表所示：操作类型程序中的数量 （百万条指令）改进前的执行时间（周期）改进后的执行时间（周期）操作11021操作2302015操作335103操作41541（1）改进后，各类操作的加速比分别是多少？(2)各类操作单独改进后，程序获得的加 速比分别是多少？(3) 4类操作均改进后，整个程序的加速比是多少?可得解：根据Amdahl定律囱=Fe (1 -Fe)=Se操作类型各类操作的指令条数在程序中所占的比例Fi各类操作的加速比Si各类操作单独改进后，

3、程序获得的加速比操作111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.144类操作均改进后，整个程序的加速比:Sn-2.16(1R)、Si1.10第二章变长编码，哈夫曼编码第三章3.12有一条指令流水线如下所示：(1) 求连续输入10条指令的情况下，该流水线 的实际吞吐率和效率。(2) 该流水线的瓶颈在哪一段？请采用两种不 同的措施消除此瓶颈。对于你所给出的两种新的 流水线，连续输入10条指令时，其实际吞吐率 和效率各是多少？解：(1)本题主要考察对各功能段用时不等的线性 流水线的性能计算公式的掌握情况。kT流水八巾(n -1) tma

4、xi 二= (50 50 100 200) 9 200二 2200(ns)TnT 流水二 1220(ns_1)k545.45%11需要充分400Ef TP W注意：对于公式不能死记硬背，理解，注意公式的适用条件。(2)瓶颈在3、4段。变成八级流水线(细分瓶颈段方法)2?4_4巳kT 流水二' ti (n - 1) tmaxi =1=508950=850(ns)T P = n t= 1 85 (ns u )I流水85k':二 tiy400 10E =TP) TP58.82%k817重复设置瓶颈段方法58.82%E=400 10850 83.13有一个流水线由4段组成，其中每当流过

5、 第三段时，总要在该段循环一次，然后才能流到 第4段。如果每段经过一次所需的时间都是 4， 问：（1）当在流水线的输入端连续地每 时间输入 一个任务时，该流水线会发生什么情况？（2）此流水线的最大吞吐率为多少？如果每 2A t输入一个任务，连续处理10个任务时，其实际 吞吐率和效率是多少？（3）当每段时间不变时，如何提高流水线的吞 吐率？人连续处理10个任务时，其吞吐率提高 多少？解：（1）会发生流水线阻塞情况(2)当任务流过第三段时要在该段循环一次， 相当于要占用第三段24时间，则该流水线可 看成是具有瓶颈段的线性流水线，瓶颈段即第 三段，所需时间为24。每24输入一个任务, 连续处理10个

6、任务的时空图如下：则:TP12 tmaxT流水二23 tTP =%流水=1%3飢E = TP 5 4 = 509254.35%(3) 重复设置部件。重复的部件可并联在流 水线上，也可串联于流水线中。如下图所示：tttttt采用并联方式时的时空图如下:Stage43_23_12112345678910224466881010! i113355779912345678910i11123456789101tTime914 tTP =% 流水吞吐率提高倍数=57t =1023't1.643.14有一条静态多功能流水线由 5段组成，加 法用1、3、4、5段，乘法用1、2、5段，第3 段的时间为2

7、牛其余各段的时间均为 ，而且 流水线的输出可以直接_应的流水线寄存器。现在该流水线上计算'4: (Ai Bi)，画出时空图，并计算其吞吐率、加速比i生和效率。解：此题容易出的问题是忽略静态流水线的特 点，当加法任务流入流水线后紧跟着启动乘法任 务。正确的做法是当所有加法任务完成从流水线 流出后再启动乘法任务，同时还应注意到流水线中的第三段所用时间为24(1 )任务分析n（4 +爲）=（4 + A）x （2+2） x（4 +53）x+尿）7(2 )画时空图123456712341234567123456718 (3 )计算流水线性能吞吐率：TpT 18 t加速比：cT串行4沃5心t +

8、33t 29Sp -T流水18118效率：实际占用面积4 5.Vt 3 3t 29一时空区总面积5x18也t- 903.18 在CRAY-I机器上，按照链接方式执行下 述4条向量指令（括号中给出了相应功能部件时 间），如果向量寄存器和功能部件之间的数据传 送需要1拍，试求此链接流水线的通过时间是多 少拍？如果向量长度为64，则需多少拍才能得 到全部结果。Vg存储器（从存储器中取数：7拍）V2- V0+ V1（向量加：3拍）V*V2v A3（按（A3）左移：4 拍）V5 V3A V4（向量逻辑乘：2拍）解：通过时间就是每条向量指令的第一个操 作数执行完毕需要的时间，也就是各功能流 水线由空到满的

9、时间，具体过程如下图所示。 要得到全部结果，在流水线充满之后，向量 中后继操作数继续以流水方式执行，直到整 组向量执行完毕。T 通过=(7+1) + (1+3+1) + (1+4+1) + (1+2+1)= 2(拍)T 总共=T 通过+(64-1)= 23+63=8(拍)说明：若考虑数据从存储器送访存部件也有 1拍 延迟，则通过时间应为24拍，完成全部任务所 用时间相应为87拍。3.佃 某向量处理机有16个向量寄存器，其中V0-V5种分别存放有向量A,B,C,D,E,F,向量的长 度是8,向量各元素均为浮点数；处理部件采用两 个单功能流水线，加法功能部件时间为2拍，乘 法功能部件时间为3拍。采

10、用类似CRAY-1的链 接技术，先计算(A+B) X C,在流水线不停的情况 下，接着计算(D+E) X F。(1) 求此链接流水线的通过时间是多少拍 ？(设 寄存器出入各需1拍(2) 假如每排时间为50ns,完成这些计算并把 结果存进相应寄存器，此处理部件的时间吞吐率 为多少MFLOPS?解：(1) 我们在这里假设A + B的中间结果放在V6 中，(A + B)X C地最后结果放在 V7中，D + E 地中间结果放在 V8中，(D + E)X F的最后结果放在V9中。具体实现参考下图:V0AV1BEl=cV3DV4E向量加V6V2C11V8V5F向量乘V7V9通过时间应该为前者（A + B）

11、x C）通过的 时间：T 通过=（1+2+1）+（1+3+1） =9（拍）（2）在做完（A+ B）xC之后，作（C + D）x E就不需要通过时间了。V6 =A B;V7 =V6 C;V8 = D E;V9 =V8 F;T =T通过+（81 + 8 = 24（拍）=12OO（ns）=1200X 10（ S）题目中所问为吞吐率是多少MFLOPS，显然是让求以MFLOPS为单位的吞吐率。MFLOPS是 指每秒完成多少百万次浮点运算，因此要明确所 有任务中共多少浮点运算。显然共有4条浮点向 量指令，而每条指令完成8个浮点运算，因此浮点运算总数为32个。所以：吞吐率：TP = tE2；厂莎厂八 和7

12、MFLOPS第四章4.4假设有一条长流水线，仅仅对条件转移指令 使用分支目标缓冲。假设分支预测错误的开销为 4个时钟周期，缓冲不命中的开销为 3个时钟周 期。假设：命中率为90%，预测精度为90%， 分支频率为15%，没有分支的基本CPI为1。(1) 求程序执行的CPI。(2) 相对于采用固定的2个时钟周期延迟的分 支处理，哪种方法程序执行速度更快？解：(1) 程序执行的CPI = CPI基本+分支延迟=1+15% X 90% X(1-90%) X 4 =(1-90% ) X 3=1.099(2) 采用固定的2个时钟周期延迟时， 程序执行的CPI = CPI基本 +分支延迟=1 + 15% X

13、 2=1.3显然采用分支目标缓冲器时程序执行时间更少，即速度更快4.5假设分支目标缓冲的命中率为 90% ,程序中 无条件转移指令的比例为5%，没有无条件转移 指令的程序CPI值为1。假设分支目标缓冲中包 含分之目标指令，允许无条件转移指令进入分支 目标缓冲，则程序的 CPI值为多少？假设无条 件分支指令不进入分支目标缓冲时程序执行的 CPI 为 1.1 解：无条件分支指令的特点是只要执行肯定分支 成功。因此，对于进入分支目标缓冲器的无条件 分支指令，分支预测的精度为100%，也就不会 带来分支延迟。而没有进入分支目标缓冲器的无 条件分支指令会带来一定分支延迟。首先要求出 一条无条件分支指令的

14、分支延迟是多少，不妨设 为x个时钟周期。由题知无条件分支指令不进入分支目标缓冲 时程序执行的CPI为1.1，而程序中没有无条件 转移指令的CPI为1,因此有CPI = CPI 无分支指令 +无条件分支延迟 =1 + 5%x =1.1 所以 x= 2因此，允许无条件分支指令进入分支目标缓冲 器时，CPI = CPI 无分支指令 + 5% X( 1-90% ) X 2 =1.01第五章存储层次5.1解释下列术语（不要求写在作业本上，但应 作为复习内容存储系统全相联映像直接映像组相联映像写直达法写回法按写分配法不按写分配法命中时间失效率强制性失效容量失效冲突失效2： 1经验规则相联度答：（答案略）5

15、.2简述"Cache-主存"层次与"主存-辅存"层 次的区别。答：存储层次、 比较项目“ Cache主存"层次“主存一辅存” 层次目的为了弥补主存速 度的不足为了弥补主存容 量的不足存储管理实现全部由专用硬件 实现主要由软件实现访问速度的比值（第一级比第二 级）几比一几百比一典型的块（页） 大小几十个字节几百到几千个字 节CPU对第二级的 访问方式可直接访问均通过第一级失效时CPU是否 切换不切换切换到其它进程5.3地址映像方法有哪些？它们各有什么优缺 点？答：（1）全相联映像。实现查找的机制复杂，代价 高，速度慢。Cache空间的利用率较高，

16、块冲突 概率较低，因而Cache的失效率也低。（2）直接映像。实现查找的机制简单，速度快。 Cache空间的利用率较低，块冲突概率较高，因 而Cache的失效率也高。（3）组相联映像。组相联是直接映像和全相联的一种折中5.4降低cache失效率有哪几种方法?答：(1) 增加Cache块大小(2) 提高相联度(3) 增加Cache的容量(4) Victim Cache(5) 伪相联Cache(6) 硬件预取技术(7) 由编译器控制的预取(8) 编译器优化。5.5简述减小cache失效开销的几种方法。答:(1) 让读失效优先于写。(2) 写缓冲合并。(3) 请求字处理技术。(4) 非阻塞Cache

17、或非锁定Cache技术。采用二级Cache。5.8组相联Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出结论：采用组 相联映像一定能带来性能上的提高？为什么？ 答：不一定。因为组相联命中率的提高是以增加 命中时间为代价的，组相联需要增加多路选择开 关。5.10假设对指令 Cache的访问站全部访问的 75% ;而对数据 Cache的访问占全部访问的 25%。Cache的命中时间为1个时钟周期，失效 开销为50个时钟周期，在混合Cache中一次load 或store操作访问Cache的命中时间都要增加一 个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数

18、据Cache的失效率为4.82%， 64KB的混合Cache的失效率为1.35%。又假设 采用写直达策略，且有一个写缓冲器，并且忽略 写缓冲器引起的等待。试问指令 Cache和数据Cache容量均为32KB的分离Cache和64KB的 混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？解：(1)分离Cache的总体失效率:F分离访存失效总次数访存总次数指令访存失效次数-数据访存失效次数 访存总次数指令访存次数指令访存失效率-数据访存次数数据访存失效率-访存总次数二指令访存次数指令访存失效率数据访存次数数据访存失效率 访存总次数访存总次数=指令访存比例指令访存失效率

19、-数据访存比例数据访存失效率= 75% 0.39 %25% 4.8 2 % =1.4975而容量为64 KB的混合Cache的失效率略低一些，只有1.35%。(2) 平均访存时间分析平均访存时间二访存总时间访存总次数_指令访存总时间-数据访存总时间 访存总次数_指令访存次数 平均指令访存时间-数据访存次数 平均数据访存时间-访存总次数指令访存次数 平均指令访存时间 数据访存次数 平均数据访存时间 访存总次数访存总次数二指令访存比例 平均指令访存时间数据访存比例 平均数据访存时间所以：平均访存时间分离 =75% X (1+0.39% X50)+25% X (1+4.82% X 50)=(75%

20、X1.195)+(25% X 3.41)平均访存时间混合=1.74875二 75% X (1+1.35% X50)+25% X (1+1+1.35% X 50)=(75% X1.675）+（25% X 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

21、）组相联映像Cache中的多路选择器使CPU 的时钟周期增加了 10%。（4）这两种Cache的失效开销都是80nso（5）命中时间为1个时钟周期。（6）64KB直接映像Cache的失效率为1.4%， 64KB2路组相联Cache的失效率为1.0%。解:（1）平均访问时间=命中时间+失效率X失效 开销平均访问时间 i-路 =2.0+1.4% >80=3.12ns平均访问时间2-路=2.0 X1+10%）+1.0% XJ0=3.0ns两路组相联的平均访问时间比较低（2）CPU时间=（CPU执行周期+存储等待周 期）x时钟周期时间=IC （CPI执行+总失效次数/指 令总数x失效开销）x时钟

22、周期=IC （CPI执行X时钟周期）+ （每条指令的访存次数X失效率X失效开销X时钟周期）所以：CPU 时 间1 路=IC(2.0 X+1.2 X.014 X0)= 5.344ICCPU 时间 2 路=IC(2.2 X2+1.2 >0.01 X80)=5.36IC相对性能比 :CP时间2路CPU时间1路=5.36/5.344=1.003直接映象cache的访问速度比两路组相 联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要 高1.003倍。因此这里选择两路组相联。第七章互连网络7.1解释下列术语(不要求写在作业本上，但应作为复习内容)线路交换 分组交换

23、静态网络 动态网络 互连网络互连函数网络直径结点度 网络规模等分宽度对称网络答：答案略7.3设E为交换函数，S为均匀洗牌函数，B为 蝶式函数，PM2I为移数函数，函数的自变量是 十进制数表示的处理机编号。现在有32台处理机，其编号为0，1，2，.，31。(1) 分别计算下列互连函数E2(12)S(8)B(9) PM2I +3(28) Eo(S(4)S(Eo(18)(2) 用Eo和S构成均匀洗牌交换网(每步只能 使用Eo和S 一次）,网络直径是多少？从5号处 理机发送数据到7号处理机，最短路径要经过几 步？请列出经过的处理几号。（3）采用移数网络构成互连网络，网络直径是 多少？结点度是多少？与 2号处理机距离最远 的是几号处理机？解：（1）共有32台处理机，因此用Iogz32 = 5比特 表示各处理器编号。E2（12） 十进制 =E2（01100）二进制=（01000）二进制= （8） 十进制S（8）十进制=S（ 01000）二进制=（10000）二进制= （16） 十进制B（9）十进制=B （ 01001）二进制=（11000）二进制 =（24） 十进制PM2I +3（28） = （28 +23） mod 32 = 4E0（S（4） 十进制=E°（S （00100）二进制=E0 （0