计算机系统结构清华第2版习题解答

《计算机系统结构清华第2版习题解答》由会员分享，可在线阅读，更多相关《计算机系统结构清华第2版习题解答（27页珍藏版）》请在装配图网上搜索。

1、清华第2版计算机系统结构习题解答华中科技大学计算机学院林安目录第一章（P33）1.7-1. 9 （透明性概念），1. 12-1. 18 （Amdahl 定律）,1.19、1.21、1.24 （CPI/MIPS）第二章（P124）2.3、2.5、2.6 （浮点数性能）,2.13、2. 15 （指令编码） 第三章（P202）3. 3 （存储层次性能）,3. 5 （并行主存系统），3. 15-3. 15加1题（堆栈模拟）,3. 19中 问（地址映象/替换算法一实存状况图） 第四章（P250）4.5 （中断屏蔽字表/中断过程示意图）,4.8 （通道流量计算/通道时间图）第五章（P343）5.9 （流水

2、线性能/时空图）,5.15 （2种调度算法）第六章（P391）6.6 （向量流水时间计算）,6. 10 （Amdahl定律/MFL0PS）第七章（P446）7. 3、7. 29 （互连函数计算），7. 6-7. 14 （互连网性质）,7. 4、7. 5、7. 26 （多级网寻径算法）,7. 27 （寻径/选播算法）第八章（P498）8. 12 （SISD/SIMD 算法） 第九章（P562）9. 18 （SISD/多功能部件/SIMD/MIMD算法）（注：每章可选1-2个主要知识点，每个知识点可只选1题。有下划线者为推荐的主要知识点。）第一章(P33)1.7(1) 从指定角度来看，不必要了解的

3、知识称为透明性概念。(2) 见下表，7为透明性概念，“P”表示相关课文页数。模m交叉，V ,浮点数据，X, P4通道与I/O处理机，X, P4总线宽度，V,阵列运算部件，X,结合型与独立型通道，V,单总线，J,访问保护，X,中断，X,指令控制方式，V,堆栈指令，X,最小编址单位，X,Cache存储器，V ,18见下表广为透明性概念P”表示相关课文页数。指令地址寄存器，X,指令缓冲器，V,时标发生器，V,条件码寄存器，X,乘法器，V,主存地址寄存器，V,磁盘，X,先行进位链，V,移位器，J,通用寄存器，X,中断字寄存器，X,数据通路宽度，7,虚拟存储器，应，Cache存储器，V ,程序状态字，X

4、,“启动I/O”指令,应,“执行”指令，X,指令缓冲寄存器，V,19见下表，“ J 表示都透明，“应”表示仅对应用程序员透明X”表示都不透明。1. 12已知Se二20 ,求作Fe-Sn关系曲线。将Se代入Amdahl定律得S =-201. 13 上式中令 Sn二2,解出 Fe二 10/19=0. 5261. 14 上式中令 Sn=10,解出 Fe二 18/190. 9471. 15己知两种方法可使性能得到相同的提高，问哪一种方法更好。(1) 用硬件组方法,己知Se二40, Fe二0. 7,解出Sn二40/12. 73. 1496 (两种方法得到的相同性能)(2) 用软件组方法,己知Se二20,

5、 Sn二40/12. 7,解出Fe=27. 3/380. 7184 (第二种方法的百分比)(3) 结论：软件组方法更好。因为硬件组需要将Se再提高100% (20-40),而软件组只需将Fe 再提高 1.84% (0. 7-0. 7184)o311.17=ni 0.90.1 + 3=2 3.571.41. 18记f 时钟频率，T二1/f 时钟周期，B 带宽（Byte/s）。方案一：B=1x4=4 f (Byte/ s)方案二:B2 =75%x2 + 25%xl2Tx4 = 3.5 f (Byte/s)1.19由各种指令条数可以得到总条数，以及各白分比，然后代公式计算。/c = /cy = 10

6、5/=1(1) CP/ = E(C77,x) = lx 0.45+ 2x0.32+ 2x0.15+ 2x0.08 = 1.55 /=1IC(2) MIPS =-云=“Xi。6 = 25.806 CPIxlO6 1.55x10655 T =-0.003876(秒) MIPSxiO6 4001.21(1) CP/= 1x0.6 +2x0.18 + 4x0.12 +8x0.1 = 2.24 MIPS = L- = 40 “： q 17.86CPIxlO6 2.24 xlO61.24记Tc 新方案时钟周期，己知CPI = CPL = 1 原时间二 CPI X IC X 0. 95Tc = 0. 95I

7、CXTc 新时间二(0. 3X2/3+0. 7) X IC X Tc = 0. 9ICXTc 二者比较，新时间较短。#第二章（P124）2.3 （忽略P124倒1行 P125第8行文字，以简化题意）己知2种浮点数，求性能指标。此题关键是分析阶码、尾数各自的最大值、最小值。原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要 求。由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可 用“土最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“土最小绝对值”回答。第1小问中,阶码全部位数为8,作无符号数看待真值为0255,作移-127码

8、看待真值为-127 +128；尾数（不计符号位）有23位小数，另加1位整数隐藏位，所以尾数绝对值为1.02.0- 2勺，有效位数p二24；第2小问中，阶码全部位数为11,作无符号数看待真值为02047,作移-1023码看待真值为 -1023+1024；尾数（不计符号位）有52位小数，另加1位整数隐藏位，所以尾数绝对值为1. 0 2.0 - 2-52,有效位数 p=53o最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的 组合。代入相关公式后得最终结果如下表。32位64位土最大绝对值土 （1一2切） 21：9土 (1-2-53) 21025土最小绝对值2-127土

9、严表数精度S22-53表数效率n100%100%2.5(1) rc = 2, re = 2, p = 24 (隐藏最高位)，q 二 7。(2) N = 1. 7X 1033, -|N|z = -1.47X10-396 W 5.96X10-3 10_7 , H = 100%2.61位7位 6位_6_ 0111111333333(1) 0.2 = 0. 333333HX160设阶码为移-63码(即-2%1,原题未指明)0. 2 = 0. 1100U00110011001100U01BX2-2（其中最高有效位需隐藏）1位8位23位阶码为移T27码（即-2 +1）0011111011001100110

10、0110011001101（2）符号位不变，（阶码-63） X4 + 127；尾数左规，除去最高位；（3）符号位不变，（阶码-127） / 4 + 63；尾数补最高位，按除法余数右移若干位，左补0。2.13己知10条指令使用频度，求3种编码方法的平均码长与信息冗余量。（1）此问中的“最优Huffman编码法”实际是指码长下限，即信源的平均信息量一爛，代公式 得 H二2. 9566oHuffman编码性能如下表；(3) 2/8扩展编码是8/64/512法的变种，第一组2条指令，码长为2 (1位扩展标志，1位编码)， 第二组8条指令，码长为4 (1位扩展标志，与第一组区别，加3位编码)，编码性能如

11、下表；(4) 3/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2 (共有4种组合，其中3种 组合分别代表3条指令，留1种组合作为扩展前缀标志)，第二组7条指令，码长为5 (2位固定 的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合)，编码性能如下表。Huffman 编码2/8扩展编码3/7扩展编码平均码长T2. 993. 13.2信息冗余量R1. 10%4.61%7. 59%2. 15(1) 15 条/63 条/64 条(2) 14 条/126 条/128 条第三章(P202)3.3直接代公式计算存储层次性能指标。(1) 74ns, 38ns, 23. 6ns(2)

12、0.258, 0. 315, 0. 424(3) T256K T128K cl28K c64K(4) 19.092, 11.97, 10.0064。答案是 256K 方案最优。3.5己知Kn =,其中沪0.1g依题意有石 =严、心+ 0.2 =+ 0.28g整理得0.刁0.2,解出4422N+N(24446N(i：i+N(2)二N “ -Ng+42+33+24+1结论如下(1) 命中率相同的方案是m= 3而n：= 2；(2) 命中次数之和最大的方案是m=4而n：= 1。3. 19中问(3)虚存实组0实组1实页0123虚 页0VV1VV2VV3VV4VV5VV6VV7V(a)虚页集合与实页集合的

13、对应关系(b)对应关系表(J为有关系)(4) 通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。9P 二624146304573CO44*4444*44*4*4*Cl11*1*1*00*555C266*6*6*6*66*6*6*6*77*C322222*33333*3入 入 入 入 中 中 替 替 中 替 替 中C 二 230102310123 此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注 号也容易导致淘汰对象错误。(6)H 二 4/1233%(8)做法同 3. 15 题问,Hz二(12X16-8)/(12X 16)95. 8%DID2

14、D3D4DI0111D20010D30000D401104. 5己知中断服务次序为3-2-4-1,。(1) 中断屏蔽字表如下图；(2) 中断过程示意图如右图。第四章(P250)时间 中断请求主程序 1级 2级3级 4级DI, D2JD3, D4 J4.8(1) f=2X105字节/秒,T=5us(2) Ts+Td二5us,通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确 定是否丢失数据(因为响应优先级低的设备较易丢失数据)。21时间(us) 01020304050607080 90 100 110 120 130 140 150 160 170(3) 5, 160, 20

15、, 40：(4) D2丢失第一次请求的数据；(5) 参见 P245。第五章(P343)5.9为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法(任务编号1-6) 再执行加法(任务编号7-11),其次在加法中釆用“最少相关算法”(即二叉树算法)。记6二A】XBi,c6=A6XB6,下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级 最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。6543211234567891214 1518 22(b)根据时空图(b)得TP = 11/(22 At) = 1/(2 At)S 二(6X4A1 + 5X4 A

16、t)/(22A t)二 2E 二(6X4At + 5X4 At)/(6X22 t)二 1/3 5. 15 A t=10ns=108秒(1) F=1, 2, 5, C=(10011)(2) 状态转移图如下图(a)所示。(3) 最小启动循环=(3)，最小平均启动距离=3 A to(4) 插入2个延迟，最小启动循环二(2)，最小平均启动距离=2 A to(5) 新预约表如下图(b)所示。(6) F=1, 3, 7, C= (1000101),状态转移图如下图(c)所示。初态 3, 4,12345678SiXooX(；2XS3Xs4DA*DiXd2X(b)$8(7) 插入前 TPg = l/3At =

17、 l/30ns,插入后 TP = 1/2 A t = l/20nso(8) 插入前 TP 二 10/33 A t 二 l/33ns,插入后 TP 二 10/26 At 二 l/26ns,如下图所示。(a)插入前D2DiS4S3S2S1(b)插入后1231234112233123412132435123415229X2KI 0I loliol w10101048第六章（P391）6. 6 （注意阅读P372倒数第9行一倒数第6行）已知n32, k加=6, k乘二7, k访存二6, k倒故二14,启动、输出延迟各1。求各小题总拍数。(1)VO 一存储器VI - V2 + V3V4 一 V5 * V

18、6并行(2) V2 - VO*V1 V3 -存储器V4 一 V2 + V3并行/ 串行(P372)访存1/7II加M /乘 1/7k总拍数二40（并行执行，以最长指令为准）乘 访存片 加 i.总拍数二79（第3条错过时机，不能链接）访存 731倒数加/ .乘111k8|16|89 | 31 p-”访存k /总拍数二87 （第4条功能部件冲突）总拍数二72 （各条依次链接）V0 -存储器 1并行(4) V0 -存储器 1链接V3 -VI +V2 -.链接VI - 1/V0.链接V4 -V0*V3 -V3 - VI +V2 链接V6 -V4 + V5 卜串行V5 - V3*V4 (5) V0 -存

19、储器 VI -V2 + V3卜并行V4 -V5 * V6s0 - si + s2了串行(6) V3 存储器并行 V2 - V0 + V1 J 串行sO s2十s3 i并行 丿V3 - VI *V4 了访存/: / r(加/ /乘11 1 /用.9 | 31 |8 p-访存7-加/-乘1II111 1i/8|31 |931 片总拍数二48 （标量看成1个分量的向量）总拍数二79 （标量看成1个分量的向量）(7)V3 -存储器V2 - V0 + V1V4 - V2*V3 存储器一 V4I并行链接j串行(8) V0 -存储器V2 一 V0 + V1V3 一 V2*V1V5 一 V3*V4I链接串行串

20、行访存 1/ /!/!加Q丨丨I.乘才审丨丨31 |s|31 *-总拍数二87 （第4条功能部件冲突）访存/ /加 I / 71 1总拍数二127 （Vi冲突,功能部件冲突）6. 10已知向量速率Rv二10MFL0PS,标量速率Rs二1MFL0PS,并记Q为可向量化白分比。（1）推导法1:使用Amdahl定律，在这里可将标量速率Rs作为原速率，局部加速后的速率为向 量速率Rv,于是局部加速比Se二10,全局加速比为R再根据加速比的定义，宣,所以有 Ra = Rs.Sn =R$Z1 、 a()+（若将向量速率Rv作为原速率，局部减速后的速率为标量速率Rs,则局部加速比Se二0.1，推出 的全局加

21、速比Sn同上式。）推导法2：为了推导，定义T为总时间，N为总任务数。于是有平均速率Ra二吞吐率TP二N/T。记 N 二 Nv + Ns,NNv + Ns则 1 _a = LNNv + Ns于是有Nv = a N和Ns 二(1-a) -N显然：总时间丁 =儿+7；=春+善Rv Rsa N Q a)N 可+ R$N所以：Ra = - =Na-N Q a)N 可+ R,或者:= cr+ (l-a)- R、&(2) 己知 Rv 二 10MFL0PS, Rs 二 1MFLOPS,R = 0.1a + (l-a)MFLOPS = io -9a MFL0PSRa与a的关系图如右图所示。(3) 己知 Ra =

22、 7. 5MFL0PS,解出a = (l - ) = x 0.96 = 96%97.5915(4) 己知 Ra 二 2MFL0PS, a = 0.7,解出Rv = r= = 3MFLOPS)-0.3x1 R,R.2as第七章(P446)7.3已知输入端编号13 = llOlBo(1) Cubes (1101B) = 0101B = 5(2) PM2+3(13) = (13 + 23)mod 16 = 21 mod 16 = 5(3) PM2+o(13) = (13 - 2) mod 16 = 12(4) Shuffle(1101B) = 1011B = 11(5) Shuffle(Shuffl

23、e(1101B) = Shuffle (101IB) = 0111B = 7 7.4用多级混洗一交换网络，n二4,拓扑结构同教材P410图7.21(e),控制信号二1010B,自左 向右各级交换开关状态依次为交换一直连一交换一直连。7.5输入结点编号j = 9, f(j) = j控制信号二1001B1100B = 0101B = 5,答为5号处理 机。7.6直连状态时：编号在第i位不同的结点之间不能通信；交换状态时：编号在第i位相同的结点之间不能通信。7.7用单级混洗一交换网可实现，总共混洗3步。证：设矩阵A二(aJSx8按行展开依次存放在64个单元中，则任意元素弧的地址为8i + j,而 的

24、地址为8j + io按混洗函数的定义，3次混洗后，shuffle3(8i + j) = 8X+ j) mod 63 二i + 8j,也就说将元素a门地址变换成弧的地址。由于如是矩阵中的任意元素，所以3次混 洗可实现矩阵转置(a J Tsxs= (a J 8X807. 8最多5级，因为对于任给的输入结点编号j二XKXiUXiXo, PM2I多级网络中i二2级的功能是 PM22(j)=j22 mod 128, 才运算只有可能改变j中的X6X：,所以最多使用CubesCube：就 能实现代换了。7.9由于N二16,即n二4,每个结点编号用4位二进制数表示。PM2土。函数功能是对结点编号 加1或减1,

25、其结果最多可将编号的4位都取反(如1111B + 1二0000B),所以用每步只能对1 位取反的单级立方体网络来模仿，最差情况下要4步。7. 10用混洗一交换网络模拟Cube网。当模拟Cube。功能时，只需一次交换即可完成；而模拟Cube且iHO时，需先作n-i步混洗, 再作1步交换，最后作i步混洗才能完成，共计n + 1步。综上所述，下限为1步，上限为n+ 1步。7.11求单级立方体网络和单级混洗一交换网络的最大广播步数，这两种网络的最大广播步数与 最大距离(即直径)相同。单级立方体网络直径=n (Cuben-iCubeo各1次)；(2)单级混洗一交换网络直径二2n-l (n-1次混洗，n次

26、交换)。7.12已知N二16,用多级立方体网络或者多级混洗一交换网络均能实现，两者可以互相模拟， 对同一置换的寻径算法相同，控制信号也相同，下面以多级立方体网络为例分析。4 组 4 元交换:fi = CubeiCubeo；2 组 8 元交换：f： = CubezCubeiCubeo;1 组 16 兀交换：fs = CubesCubezCubeiCubeo;利用Cube函数的结合律、交换律以及同一律(乂称自反律)可以推得f 二 fifzf3 二 CubesCubeiCubeo拓扑结构图略(可参考7. 26题的多级混洗一交换网络拓扑结构图)。网络开关使用级控方式，控制信号为1011B (其中bih

27、控制级i, “0”表示直连，“1”表示交 换)。7. 13 N二8的蝶式置换。(1) f (X2X1X0)二 XoXiX：； (2)至少需2次通过，每次都是N个数据同时发送，同时接收，中途不储存;表示交换。 控制信号的设置有4种方案，如下所示。其中“0”表示直连,101000000100、000000oof000000iof000000101 100 001 101000101101000100100000 000ooo、001001000、101101000 0007. 14共N!种；N(2) 一次通过有“了种不同；N亍84(3) N = 8 时，百分比二100% =瓦x 100% u 10

28、.16%7. 26(1)；(1) 见下图实线。(2) 见下图虚线；不会阻塞，因为两条路径的控制信号都是1110,形成级控模式，所以不会阻塞。(3) 次通过实现的置换数为16 s = 4294967296,全部置换数为N! = 20922789888000,前者约 占后者的0. 02%o级3级2级1级0000000010010001101000101011001111000100110101011110011011110111100000001001000110100010101100111100010011010101111001101111011117. 27(1) 己知 N = 64, n

29、 = 6,源结点 s = 101101B,目的结点 d = 011010B,方向矢量 r = s d = 1101UB, 以低维度优先顺序寻径，路径为s = 101101B - 101100B - 101110B 一 101010B 一 111010B - 011010B = d (下划线 为当前寻径维)一(2) 求给定无向图中2棵选播树(即生成树)。(1)求最小成本生成树(通道数最少)，可考虑Prim算法、Kruskal算法或标记法。一个参 考操作方法是：先对临近结点群分别构造最短子树，然后在子树之间作最短互连。(ii)求由结点(3, 5)出发的单源最短路径生成树(各距离最短)，可考虑贪心算

30、法。对X-Y 网格图来说，从树根到某一树叶的任何路径只要在各维均无反向移动即为最短路径(满足此条件 的最短路径有多条)。要得到单一树根对于多片树叶的综合最短路径，可以先分别作出各条单播 最短路径，然后在不增加各路径长度的前提下，尽可能地进行路段合并。#sSi + S2 + S3 + S4 + S5 + S6 + S7 + S$这两小问结果如下图所示(其中b图第一步必须选择向下，而不能向右)。 0(9 (9 0 0 T Y ,1) X.1Y 427(a)(3) 求作超立方体贪心选播树。7. 29己知N二256, n = 8,起始结点编号j二123二OllllOllBo根据混洗函数的循环移位性 质

31、,Shuffle10(j) = Shuffle2(j) = 11101101B = 237第八章(P498)8. 12 问题为S=A1XB1+A32XB32,其中 T 乘=4 At, T 加二 2A t, T 传=1 Ato(1) 在串行计算机上，各操作不论是否相关均不能重叠，总时间恒等于各操作单独时间之和，所 以不必考虑运算顺序。T二32T#+31Tw= (32X4+31X2) At=190At(2) 设此双向环可以并行传送(即为“移数环”，因为SIMP系统齐种数据操作都能并行)。按平均分配原则，每个结点内有4对数据。首先在各结点用串行算法它们的相乘与求和,需时Ti=4T集+3T .JU=

32、(4 X 4+3 X 2) A t=22 A t;然后用二叉树并行算法将8个结点中的部分和相加(见下图)，其中并行加法需3次，每次 时间相同，而并行传送3次的每次时间却随距离倍增，依次为1、2、4步，所以有Tf(1+2+4)T 传+3 Tju=(7Xl+3X2) At=13At；总时间 T=Ti+T：=35 A t .右传2步加法1步 .右传21步加法1步 .右传22步加法1步第九章(P562)9. 18 问题为 S=(A1+B1)XX (A8+B8),其中 T 加二30ns, T 乘二50ns, T 传二 10ns。将加法记为任务1-8,乘法记为任务9-15o 在串行计算机上，同8. 12题

33、1问分析，共计15步运算，T二8T加+7T乘二(8X30+7X 50)ns二590ns。(2)多功能部件SISD计算机的工作方式可参考P346题18 (3)。为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运 算(见下图)。T=2 T 加+7 T 瘙二(2X30+7X50)ns二410ns910112151235678乘法加法7 X 50ns8 X 30ns(3)同& 12题2问,设单向环可以并行传送(即为“移数环S理由同8. 12题2问)T二T 加+3 T 乘+(1+2+4) T 传二(30+3X50+7 X 10) ns二250nsG-D O G-s) O O O传送乘法加法3011505050102040(4) 在全互连网络上，任意两个结点之间的距离均为1步，所以任何置换都能在1步完成，故T二T 加+3 T #+(1+1+1) T 传=(30+3X50+3X 10)ns=210ns传送乘法加法301150505010 10 10