《2022年计算机系统结构第1-8章部分作业答案》由会员分享,可在线阅读,更多相关《2022年计算机系统结构第1-8章部分作业答案(11页珍藏版)》请在金锄头文库上搜索。
1、第一章1.6 某台主频为400MHz 的计算机执行标准测试程序,程序中指令类型、执行数量和平均时钟周期数如下:指令类型指令执行数量平均时钟周期数整数45000 1 数据传送75000 2 浮点8000 4 分支1500 2 求该计算机的有效CPI、MIPS 和程序执行时间。解: (1)CPI (450001750002 8000415002) / 129500 1.776 (或259460) (2)MIPS 速率 f/ CPI 400/1.776 225.225MIPS (或2595180MIPS)(3)程序执行时间= (4500017500028000415002)400=575 s1.9
2、假设某应用程序中有4 类操作,通过改进,各操作获得不同的性能提高。具体数据如下表所示:操作类型程序中的数量(百万条指令)改进前的执行时间(周期)改进后的执行时间(周期)操作 1 10 2 1 操作 2 30 20 15 操作 3 35 10 3 操作 4 15 4 1 (1)改进后,各类操作的加速比分别是多少?(2)各类操作单独改进后,程序获得的加速比分别是多少?(3)4 类操作均改进后,整个程序的加速比是多少?解:根据 Amdahl 定律SeFeFeSn)1(1可得操作类型各类操作的指令条数在程序中所占的比例Fi各类操作的加速比Si各类操作单独改进后,程序获得的加速比操作 1 11.1% 2
3、 1.06 操作 2 33.3% 1.33 1.09 操作 3 38.9% 3.33 1.37 操作 4 16.7% 4 1.14 4 类操作均改进后,整个程序的加速比:2.16)1(1iiinSFFS1.10 第二章变长编码,哈夫曼编码精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 11 页第三章3.12 有一条指令流水线如下所示:(1)求连续输入10 条指令的情况下,该流水线的实际吞吐率和效率。(2)该流水线的瓶颈在哪一段?请采用两种不同的措施消除此瓶颈。对于你所给出的两种新的流水线,连续输入10 条指令时,其实际吞吐率和效率各是多
4、少?解:(1)本题主要考察对各功能段用时不等的线性流水线的性能计算公式的掌握情况。2200(ns)2009200)10050(50tntTmaxkii)1(1流水)(ns2201TnTP1流水45.45%1154400TPktTPEk1ii注意:对于公式不能死记硬背,需要充分理解,注意公式的适用条件。(2)瓶颈在3、 4 段。变成八级流水线(细分瓶颈段方法)123_13_24_14_4?3 ?50ns50ns50ns50ns50ns50ns850(ns)509850t1)(ntTmaxk1ii流水)(ns851TnT P1流水58.82%17108400TPktiTPEk1i重复设置瓶颈段方法
5、50ns 50ns 100ns 200ns 1 2 3 4 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 11 页123_13_24_14_24_34_411112222333344445555666677778899101089108910850nsTimeStage)(ns851TnTP1流水58.82%1710885010400E3.13 有一个流水线由4 段组成,其中每当流过第三段时,总要在该段循环一次,然后才能流到第 4 段。如果每段经过一次所需的时间都是 t,问:(1)当在流水线的输入端连续地每t 时间输入一个任务时,该流
6、水线会发生什么情况?(2)此流水线的最大吞吐率为多少?如果每2 t 输入一个任务,连续处理10 个任务时,其实际吞吐率和效率是多少?(3)当每段时间不变时,如何提高流水线的吞吐率?人连续处理10 个任务时, 其吞吐率提高多少?解:(1)会发生流水线阻塞情况。(2)当任务流过第三段时要在该段循环一次,相当于要占用第三段2 t 时间, 则该流水线可看成是具有瓶颈段的线性流水线,瓶颈段即第三段,所需时间为2 t。每 2 t 输入一个任务,连续处理10 个任务的时空图如下:StageTime12341111122222333334444455555666667777788888999991010101
7、010t23则:1 2 3-1 3-2 4-1 4-2 4-3 4-4 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 11 页54.35%9250TPETnTpTTPmax4523102321tttt流水流水(3)重复设置部件。 重复的部件可并联在流水线上,也可串联于流水线中。如下图所示:123_13_24ttttt123_13_24ttttt采用并联方式时的时空图如下:StageTime1123_13_24111122222333334444455555666667777788888999991010101010t14tt75141
8、0流水TnTP吞吐率提高倍数tt2310751.64 3.14 有一条静态多功能流水线由5 段组成,加法用1、3、4、5 段,乘法用1、2、5 段,第3 段的时间为2 t,其余各段的时间均为 t,而且流水线的输出可以直接返回输入端或暂存于相应的流水线寄存器中。现在该流水线上计算41)(iiiBA,画出时空图,并计算其吞吐率、加速比和效率。 t t 2 t t 1 2 3 4 5 t 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 11 页解:此题容易出的问题是忽略静态流水线的特点,当加法任务流入流水线后紧跟着启动乘法任务。正确的做法是当
9、所有加法任务完成从流水线流出后再启动乘法任务,同时还应注意到流水线中的第三段所用时间为2 t。(1)任务分析(2)画时空图1 2 3 4 5 6 7 1 2 3 4 1 2 3 4 5 6 7 1 2 3 4 5 6 7 18 t(3)计算流水线性能吞吐率:tTnTp187加速比:18291854t3t3t流水串行TTSp效率:902954t1853t3t时空区总面积实际占用面积E3.18 在 CRAY-l 机器上,按照链接方式执行下述4 条向量指令 ( 括号中给出了相应功能部件时间 ) ,如果向量寄存器和功能部件之间的数据传送需要1 拍,试求此链接流水线的通过时间是多少拍?如果向量长度为 6
10、4 ,则需多少拍才能得到全部结果。V0存储器(从存储器中取数:拍)V2V0V1 (向量加:拍)V3V2A3 (按 (A3) 左移:拍)V5V3V4 (向量逻辑乘:拍)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 11 页解: 通过时间就是每条向量指令的第一个操作数执行完毕需要的时间,也就是各功能流水线由空到满的时间,具体过程如下图所示。要得到全部结果,在流水线充满之后,向量中后继操作数继续以流水方式执行,直到整组向量执行完毕。存储器访存向量加左移向量逻辑乘V0V1V2V3V4V5A3(拍)(拍)()()(通过总共通过866323164
11、TT2312114113117T说明:若考虑数据从存储器送访存部件也有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,完成这些计算并把结果存进相应寄存器,此
12、处理部件的时间吞吐率为多少MFLOPS? 解:(1)我们在这里假设AB 的中间结果放在V6 中, (AB) C 地最后结果放在V7 中,DE 地中间结果放在V8 中, (DE) F 的最后结果放在V9 中。具体实现参考下图:V0AV1BV3DV4EV5FV6V7V2CV9V8向量加向量乘通过时间应该为前者( (AB) C)通过的时间:T通过= (1+2+1)+(1+3+1) =9 (拍)(2)在做完( AB) C 之后,作( CD) E 就不需要通过时间了。; FV8V9E;DV8C;V6V7B;AV6精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第
13、 6 页,共 11 页1200(ns)TT(拍)(通过24818=1200 10-9 (s)题目中所问为吞吐率是多少MFLOPS , 显然是让求以MFLOPS为单位的吞吐率。 MFLOPS是指每秒完成多少百万次浮点运算,因此要明确所有任务中共多少浮点运算。显然共有4条浮点向量指令,而每条指令完成8 个浮点运算,因此浮点运算总数为32 个。所以:吞吐率:MFLOPS26.67T32TPE696101012003210第四章4.4 假设有一条长流水线,仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为 4 个时钟周期,缓冲不命中的开销为3 个时钟周期。假设:命中率为90%,预测精度为 9
14、0%,分支频率为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。假设分支目标缓冲中
15、包含分之目标指令,允许无条件转移指令进入分支目标缓冲, 则程序的 CPI 值为多少?假设无条件分支指令不进入分支目标缓冲时程序执行的CPI 为 1.1 解:无条件分支指令的特点是只要执行肯定分支成功。因此,对于进入分支目标缓冲器的无条件分支指令,分支预测的精度为100% ,也就不会带来分支延迟。而没有进入分支目标缓冲器的无条件分支指令会带来一定分支延迟。首先要求出一条无条件分支指令的分支延迟是多少,不妨设为x 个时钟周期。由题知无条件分支指令不进入分支目标缓冲时程序执行的CPI 为 1.1,而程序中没有无条件转移指令的CPI 为 1,因此有CPI = CPI无分支指令+无条件分支延迟= 1 +
16、 5%x = 1.1 所以 x= 2 因此,允许无条件分支指令进入分支目标缓冲器时,CPI = CPI无分支指令+ 5%( 1-90%) 2 =1.01 第五章 存储层次5.1 解释下列术语(不要求写在作业本上,但应作为复习内容)存储系统全相联映像直接映像组相联映像写直达法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 11 页写回法按写分配法不按写分配法命中时间失效率强制性失效容量失效冲突失效2:1 经验规则相联度答: (答案略)5.2 简述“ Cache-主存”层次与“主存-辅存”层次的区别。答:存储层次比较项目“Cache主存”层
17、次“主存辅存”层次目的为了弥补主存速度的不足为了弥补主存容量的不足存储管理实现全部由专用硬件实现主要由软件实现访问速度的比值(第一级比第二级)几比一几百比一典型的块(页)大小几十个字节几百到几千个字节CPU 对第二级的访问方式可直接访问均通过第一级失效时 CPU 是否切换不切换切换到其它进程5.3 地址映像方法有哪些?它们各有什么优缺点?答:(1)全相联映像。实现查找的机制复杂,代价高,速度慢。Cache 空间的利用率较高,块冲突概率较低,因而Cache的失效率也低。(2)直接映像。实现查找的机制简单,速度快。Cache 空间的利用率较低,块冲突概率较高,因而Cache 的失效率也高。(3)组
18、相联映像。组相联是直接映像和全相联的一种折中。5.4 降低 cache失效率有哪几种方法?答:(1)增加 Cache 块大小(2)提高相联度(3)增加 Cache 的容量(4)Victim Cache (5)伪相联Cache (6)硬件预取技术(7)由编译器控制的预取(8)编译器优化。5.5 简述减小cache失效开销的几种方法。答:(1) 让读失效优先于写。(2) 写缓冲合并。(3) 请求字处理技术。(4) 非阻塞 Cache或非锁定Cache技术。(5) 采用二级Cache。5.8 组相联 Cache 的失效率比相同容量直接映像Cache 的失效率低。由此能否得出结论:采用组相联映像一定能
19、带来性能上的提高?为什么?精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 11 页答:不一定。因为组相联命中率的提高是以增加命中时间为代价的,组相联需要增加多路选择开关。5.10 假设对指令Cache 的访问站全部访问的75%;而对数据Cache 的访问占全部访问的25%。Cache 的命中时间为1 个时钟周期, 失效开销为50 个时钟周期, 在混合 Cache 中一次load 或 store 操作访问 Cache 的命中时间都要增加一个时钟周期,32KB 的指令 Cache 的失效率为 0.39%, 32KB 的数据 Cache 的失
20、效率为4.82%, 64KB 的混合 Cache 的失效率为1.35%。又假设采用写直达策略,且有一个写缓冲器, 并且忽略写缓冲器引起的等待。试问指令 Cache和数据 Cache容量均为32KB 的分离 Cache和 64KB 的混合 Cache 相比, 哪种 Cache 的失效率更低?两种情况下平均访存时间各是多少?解:(1)分离 Cache 的总体失效率:4975.1242539.075.%.8%F数据访存失效率数据访存比例指令访存失效率指令访存比例数据访存失效率访存总次数数据访存次数指令访存失效率访存总次数指令访存次数访存总次数数据访存失效率数据访存次数指令访存失效率指令访存次数访存总
21、次数数据访存失效次数指令访存失效次数访存总次数访存失效总次数分离而容量为64 KB 的混合 Cache的失效率略低一些,只有1.35%。( 2)平均访存时间分析平均数据访存时间数据访存比例平均指令访存时间指令访存比例访存总次数平均数据访存时间数据访存次数访存总次数平均指令访存时间指令访存次数访存总次数平均数据访存时间数据访存次数平均指令访存时间指令访存次数访存总次数数据访存总时间指令访存总时间访存总次数访存总时间平均访存时间所以:平均访存时间分离75% (1+0.39%50)+25% (1+4.82%50) (75%1.195)+(25%3.41) 1.74875 平均访存时间混合75% (1
22、+1.35%50)+25% (1+1+1.35% 50) (75%1.675)+(25%2.675) 1.925 因此,尽管分离Cache 的实际失效率比混合Cache 的高,但其平均访存时间反而较低。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 11 页5.11 给定以下的假设, 试计算直接映像Cache和 2 路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论?(1)理想 Cache 情况下的CPI 为 2.0,时钟周期为2ns,平均每条指令访存1.2 次。(2)两者 Cache 容量均为64KB,块大小都
23、是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执行+总失效次数 /指令总数失效开销)
24、时钟周期= IC ( (CPI执行时钟周期) +(每条指令的访存次数失效率失效开销时钟周期) )所以:CPU 时间1路=IC(2.02+1.2 0.014 80) 5.344ICCPU 时间2路=IC(2.2 2+1.2 0.01 80)5.36IC 相对性能比:路路时间时间1CPUCP25.36/5.344=1.003 直接映象cache的访问速度比两路组相联cache要快 1.04 倍,而两路组相联Cache的平均性能比直接映象cache要高 1.003 倍。因此这里选择两路组相联。第七章 互连网络7.1 解释下列术语(不要求写在作业本上,但应作为复习内容)线路交换分组交换静态网络动态网络
25、互连网络互连函数网络直径结点度网络规模等分宽度对称网络答:答案略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 号处理
26、机距离最精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 11 页远的是几号处理机?解:(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) mod 32 = 4 E0(S(4)十进制= E0(S(00100) )二进制=
27、E0(01000)= (01001)二进制= (9)十进制S(E0(18)十进制= S (E0(10010) )二进制=S(10011)= ( 00111)二进制= (7)十进制(2)2n个结点的均匀洗牌交换网的网络直径是2n-1,32 个结点的均匀洗牌交换网的网络直径为 9。从 5号处理机发送数据到7 号处理机,最短路径要经过6 步:0 0 1 1 11 0 0 1 11 0 0 1 00 1 0 0 10 1 0 0 00 0 1 0 00 0 1 0 1SESESE000(3)网络直径是3,节点度是9,与 2 号处理机距离最远的是13、15、21、23 号处理机。 . 第八章 多处理机8
28、.1 解释下列术语(不要求写在作业本上,但应作为复习内容)集中式共享多处理机分布式共享多处理机通信延迟计算 /通信比监听协议目录协议写作废协议写更新协议答:答案略8.2 一个具有32 个处理器的多处理机,对远程存储器访问时间为2000 ns。除了通信以外,假设所有其他访问均命中局部存储器。当发出一个远程请求时,本处理器挂起。 处理器的时钟周期时间是10ns,假设指令基本的CPI 为 1.0(设所有访存均命中局部存储器)。对于下述两种情况:( 1)没有远程访问。( 2)有 0.5%的指令需要远程访问。试问前者比后者快多少? 解:已知远程访问率p=0.5%,远程访问时间t=2000ns,时钟周期时间T=10ns,则远程访问开销C=t/T = 2000ns/10ns = 200 个时钟周期则有 0.5%远程访问的机器的实际CPI2为:CPI2= CPI1 + pC = 1.0 + 0.5% 200 = 2.0 只有局部访问的机器的基本CPI1 =1.0 ,故CPI2/CPI1 = 2.0/1.0 = 2(倍) 因此,没有远程访问状态下的机器速度是有0.5%远程访问的机器速度的2 倍。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 11 页