2022年清华第版《计算机系统结构》习题解答共页 .pdf

《2022年清华第版《计算机系统结构》习题解答共页 .pdf》由会员分享，可在线阅读，更多相关《2022年清华第版《计算机系统结构》习题解答共页 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 页计算机系统结构习题解答目录第一章 (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 中(3)(4)(6)(8)问（地址映象/ 替换算法 - 实存状况图）第四章 (P250) 4.5 （中断屏蔽字表 / 中断过程示意图） ，4.8 （通道流量计算/通道时间图）第五

2、章 (P343) 5.9 （流水线性能 / 时空图），5.15 （2 种调度算法）第六章 (P391) 6.6 （向量流水时间计算） ，6.10 （Amdahl 定律 /MFLOPS ）第七章 (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 题。有下划线者为推荐的主要知识

3、点。) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 第 2 页第一章 (P33) 1.7 (1) 从指定角度来看，不必要了解的知识称为透明性概念。(2) 见下表，“”为透明性概念， “P”表示相关课文页数。1.8 见下表，“”为透明性概念， “P”表示相关课文页数。1.9 见下表，“”表示都透明， “应”表示仅对应用程序员透明，“”表示都不透明。1.12 已知 Se=20 , 求作 Fe-Sn 关系曲线。将 Se 代入 A

4、mdahl 定律得1.13 上式中令 Sn=2，解出 Fe=10/19 0.526 1.14 上式中令 Sn=10，解出 Fe=18/19 0.947 1.15 已知两种方法可使性能得到相同的提高，问哪一种方法更好。(1) 用硬件组方法，已知Se=40 ，Fe=0.7 ，解出 Sn=40/12.7 3.1496 （两种方法得到的相同性能）(2) 用软件组方法，已知Se=20 ，Sn=40/12.7 ，解出 Fe=27.3/38 0.7184 （第二种方法的百分比）(3) 结论：软件组方法更好。 因为硬件组需要将Se再提高 100% （2040） ，而软件组只需将Fe 再提高 1.84% （0.

5、70.7184 ） 。1.17 57. 34. 1559.01. 01nS1.18 记 f 时钟频率， T=1/f 时钟周期， B 带宽（ Byte/s ） 。方案一：)/(4411sBytefTB方案二：)/(5.3421%252%752sBytefTB1.19 由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。(1)4155.108.0215.0232.0245.01)(iiiICICCPICPI模 m 交叉，浮点数据，P4通道与 I/O 处理机， P4总线宽度，阵列运算部件，结合型与独立型通道，单总线，访问保护，中断，指令控制方式，堆栈指令，最小编址单位，Cache存储器，指令

6、地址寄存器，指令缓冲器，时标发生器，条件码寄存器，乘法器，主存地址寄存器，磁盘，先行进位链，移位器，通用寄存器，中断字寄存器，数据通路宽度，虚拟存储器，应，Cache存储器，程序状态字，“启动 I/O”指令，应，“执行”指令，指令缓冲寄存器，Sn 20 1 0 1 Fe 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 第 3 页(2)806.2555.1401055.1104010666CPIfMIPS(3)（秒）003876

7、.040055.1106MIPSICT1.21 (1)24.21 .0812. 0418. 026 .01CPI(2)86.171024.2104010666CPIfMIPS1.24 记 Tc 新方案时钟周期，已知CPI = CPIi = 1 原时间 = CPI IC 0.95Tc = 0.95ICTc 新时间 = （0.3 2/3+0.7 ） IC Tc = 0.9ICTc 二者比较，新时间较短。第二章 (P124) 2.3 （忽略 P124倒 1 行 P125 第 8 行文字，以简化题意）已知2 种浮点数，求性能指标。此题关键是分析阶码、尾数各自的最大值、最小值。原图为数据在内存中的格式，

8、阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“最小绝对值”回答。第 1 小问中，阶码全部位数为8，作无符号数看待真值为0255，作移 -127 码看待真值为 -127 +128；尾数（不计符号位）有23 位小数，另加1 位整数隐藏位，所以尾数绝对值为1.0 2.0 2-23，有效位数 p=24；第 2 小问中，阶码全部位数为11，作无符号数看待真值为02047，作移 -1023 码看待真值为 -1023 +1024；尾数（不计符号位）有52

9、 位小数，另加1 位整数隐藏位，所以尾数绝对值为1.0 2.0 2-52，有效位数 p=53。最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。2.5 (1) rm = 2 ，re = 2 ，p = 24 （隐藏最高位）,q = 7 。(2) Nmax = 1.71038，-|N|min = -1.4710-39 5.96 10-8 10-7.22， = 100% 2.6 (1) 0.2 = 0.333333H160设阶码为移 -63 码（即 -26+1，原题未指明）0.2 = 0.110011001100110011001

10、101B2-232 位64 位最大绝对值(1-2-24) 2129(1-2-53) 21025最小绝对值2-1272-1023表数精度 2-242-53表数效率 100% 100% 1 位7 位6 位0 0111111 333333 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 第 4 页（其中最高有效位需隐藏）阶码为移 -127 码（即 -27+1）(2) 符号位不变，（阶码 63 ） 4 + 127 ；尾数左规，除去最高

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

12、，码长为2（共有 4 种组合，其中3 种组合分别代表3条指令， 留 1 种组合作为扩展前缀标志）, 第二组 7 条指令， 码长为 5 （2 位固定的前缀扩展标志，与第一组区别，加 3 位编码，只用其中7 种组合），编码性能如下表。2.15 (1) 15条/63 条/64 条(2) 14条/126 条 /128 条第三章 (P202) 3.3 直接代公式计算存储层次性能指标。(1)74ns ，38ns， 23.6ns (2)0.258，0.315 ，0.424 (3)T256K T128K c128K c64K (4)19.092 ，11.97 ，10.0064 。答案是256K方案最优。3.5

13、 已知ggKnn)1(1，其中 g=0.1 依题意有2.0)1 (12 .0)1 (111ggKggKnnnn整理得 0.9n0.2 ，解出28.159.0lg2.0lgn，向下取整，得15；按另一种题意理解是向上取整，得16，也对。3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“”表示命中。1 位8 位23 位0 01111101 10011001100110011001101 Huffman 编码2/8 扩展编码3/7 扩展编码平均码长 L 2.99 3.1 3.2 信息冗余量R 1.1

14、0% 4.61% 7.59% 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 第 5 页(1)Hmax=7/12 58.3% (2)n=4 (3) 当 1 次页面访问代表连续1024 次该页内存储单元访问时，后1023 次单元访问肯定是命中的，而第1 次单元访问的命中情况与这1 次页面访问的命中情况相同。根据上图中最高命中情况，共有 7 次页命中（折算为 71024次单元命中） ，5 次页不命中 （折算为 51023 次单元命

15、中， 也可写为51024-5 ） ，单元访问总次数为121024，故有：Hcell=(12 1024-5)/(121024)=12283/12288 99.96% 3.15 加 1 题 一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5 页，为 2 道程序分享，页地址流分别如下P1 = 1 2 3 4 1 3 2 1 P2 = 1 2 3 4 2 2 3 3 试作 2 个实存分配方案，分别使2 道程序满足(1) 命中率相同；(2) 命中次数之和最大。解：分别为2 道程序作“堆栈模拟图” ，其中“”表示命中。将两图结果综合，得到4 个分配方案的命中率情况表如下结论如下(1) 命中率相同

16、的方案是n1= 3 而 n2= 2；(2) 命中次数之和最大的方案是n1= 4 而 n2= 1。3.19 中(3)(4)(6)(8)问P= 4 5 3 2 5 1 3 2 3 5 1 3 命中次数4 5 3 2 5 1 3 2 3 5 1 3 4 5 3 2 5 1 3 2 3 5 1 4 5 3 2 5 1 1 2 3 5 4 4 3 2 5 5 1 2 2 4 4 4 4 4 4 4 n=1 0 n=2 1 n=3 3 n=4 7 n=5 7 11 3 2 1 (1)1 3 2 1 1 3 4 1 3 2 2 4 4 10 10 12 1P2 = 1 2 3 4 2 2 3 3 命中次数

17、N(2)1 2 3 4 2 2 3 3 1 2 3 4 4 2 2 1 2 3 3 4 4 1 1 1 1 1 n2= 1 2 n2= 2 2 n2= 3 4 n2= 4 4 6 5 N(1)+N(2)4 3 2 N(1) N(2)1 1+4 2+3 3+2 4+1 n11 2 3 4 N(1)0 0 2 4 n24 3 2 1 N(2)4 4 2 2 N(1)+N(2)4 4 4 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - -

18、- - 第 6 页(3) (4) 通过作“实存状况图”模拟各虚块的调度情况，可获得Cache 的块地址流序列。此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。(6)H=4/12 33% (8) 做法同 3.15 题(3) 问， Hcell=(12 16-8)/(1216) 95.8% 第四章 (P250) 4.5 已知中断服务次序为3-2-4-1 ， 。(1) 中断屏蔽字表如下图；(2) 中断过程示意图如右图。4.8 (1)f=2 105字节 / 秒， T=5us (2)Ts+Td=5us ，通道时间图如下。 作图时注意： 至少要画

19、到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。虚存实页0 1 2 3 虚组 0 0 0 1 实存1 虚组 1 2 0 实组 0 2 3 1 虚3 虚组 2 4 2 实组 1 页4 5 3 5 虚组 3 6 6 7 7 (a) 虚页集合与实页集合的对应关系(b) 对应关系表（为有关系）P= 6 2 4 1 4 6 3 0 4 5 7 3 C0 4 4* 4 4 4 4* 4 4* 4* 4* C1 1 1* 1* 1* 0 0* 5 5 5 C2 6 6* 6* 6* 6* 6 6* 6* 6* 6* 7 7* C3 2 2 2 2 2* 3 3 3 3

20、 3* 3 入入入入中中替替中替替中C= 2 3 0 1 0 2 3 1 0 1 2 3 时间中断请求主程序1 级2 级3 级4 级D1，D2 D3，D4 D1 D2 D3 D4 D1 0 1 1 1 D2 0 0 1 0 D3 0 0 0 0 D4 0 1 1 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - 第 7 页(3)5 ，160，20， 40；(4)D2 丢失第一次请求的数据；(5) 参见 P245。第五章 (P

21、343) 5.9 为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6 ）再执行加法（任务编号 7-11 ） ，其次在加法中采用“最少相关算法”（即二叉树算法） 。记 c1=A1B1， ，c6=A6B6，下图 (a) 是加法的计算顺序二叉树，注意任务10 应该用前一级最早完成的任务7 和 8 的结果，如果用任务9 的结果则要推迟1 拍启动，使总时间增加1 拍。根据时空图 (b) 得TP = 11/(22t) = 1/(2t) S = (6 4t + 5 4t)/(22t) = 2 E = (6 4t + 5 4t)/(622t) = 1/3 设优备先号级D1 1 D

22、2 4 D3 2 D4 3 时间(us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 F=c1+c2+c3+c4+c5+c66 1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 3 7 8 9 10 11 10 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 (a) (b) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

23、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - - - - 第 8 页5.15 t=10ns=10-8秒(1)F=1 ，2，5，C=(10011) (2) 状态转移图如下图(a) 所示。(3) 最小启动循环 =（3）, 最小平均启动距离=3t 。(4) 插入 2 个延迟，最小启动循环=（2）, 最小平均启动距离=2t 。(5) 新预约表如下图 (b) 所示。(6)F=1 ，3，7，C=(1000101) ，状态转移图如下图(c) 所示。(7) 插入前 TPmax = 1/3t = 1/30ns，插入后 TPm

24、ax = 1/2t = 1/20ns。(8) 插入前 TP = 10/33 t = 1/33ns，插入后 TP = 10/26 t = 1/26ns，如下图所示。1 2 3 4 5 6 7 8 初态4，6， 8S11 2 初态3，4， 6 S21 1 0 0 0 1 0 1 S34，6， 84，6， 81 0 0 1 1 S41 2 5 D11 0 1 0 1 0 1 1 0 0 0 1 1 1 D22 5 (a) (b) (c) S41 1 2 2 3 10 10 S31 2 3 10 S21 1 2 2 3 10 10 S11 2 1 3 2 10 10 3 t (a) 插入前93 6D2

25、1 2 3 11 D11 2 3 4 10 S41 1 2 2 3 3 10 10 S31 2 3 4 10 S21 2 1 3 2 4 3 5 10 10 S11 2 3 4 1 5 2 10 10 2 t (b) 插入后92 8名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - 第 9 页第六章 (P391) 6.6 （注意阅读P372倒数第 9 行倒数第6 行）已知 n=32，k加=6，k乘=7，k访存=6，k倒数=14，启

26、动、输出延迟各1。求各小题总拍数。(4) V0 存储器链接V1 1 / V0 链接V3 V1 + V2 链接V5 V3 * V4 访存倒数加乘 8 16 8 9 31 总拍数 =72（各条依次链接）(3) V0 存储器并行V3 V1 + V2 链接V4 V0 * V3 V6 V4 + V5 串行访存加乘8 9 31 8 31 总拍数 =87（第 4 条功能部件冲突）(1) V0 存储器V1 V2 + V3 并行V4 V5 * V6 访存加乘9 31 总拍数 =40（并行执行，以最长指令为准）(2) V2 V0 * V1 并行V3 存储器V4 V2 + V3 串行（ P372）乘访存加 9 31

27、 8 31 总拍数 =79（第 3 条错过时机，不能链接）(5) V0 存储器V1 V2 + V3 并行V4 V5 * V6 s0 s1 + s2 串行访存加乘9 31 8 总拍数 =48（标量看成1 个分量的向量）(6) V3 存储器并行V2 V0 + V1 串行s0 s2 + s3 并行V3 V1 * V4 访存加乘8 31 9 31 总拍数 =79（标量看成 1 个分量的向量）(7) V3 存储器并行V2 V0 + V1 链接V4 V2 * V3 存储器 V4 串行访存加乘8 9 31 8 31 总拍数 =87（第 4 条功能部件冲突）(8) V0 存储器链接V2 V0 + V1 V3

28、V2 * V1 串行V5 V3 * V4 串行访存加乘8 8 31 9 31 9 31 总拍数 =127（V1冲突，功能部件冲突）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 第 10 页6.10 已知向量速率Rv = 10MFLOPS ，标量速率 Rs = 1MFLOPS ，并记 为可向量化百分比。(1) 推导法 1：使用 Amdahl 定律，在这里可将标量速率Rs作为原速率，局部加速后的速率为向量速率Rv，于是局部加速比

29、Se=10，全局加速比为再根据加速比的定义，snRRS，所以有MIPSSRSRResns9.011)1(。（若将向量速率Rv 作为原速率，局部减速后的速率为标量速率Rs，则局部加速比Se=0.1，推出的全局加速比Sn 同上式。）推导法 2：为了推导，定义T 为总时间， N为总任务数。于是有平均速率Ra = 吞吐率 TP = N/T。记 N = Nv + Ns，且svvvNNNNN，则svssNNNNN1，于是有 Nv = N和 Ns = (1-) N 显然：总时间svssvvsvRNRNRNRNTTT)1(所以：svsvaRRRNRNNTNR1)1(11)1(或者：svaRRR1)1 (11(

30、2) 已知 Rv = 10MFLOPS ，Rs = 1MFLOPS ，Ra与的关系图如右图所示。(3) 已知 Ra = 7.5MFLOPS，解出(4) 已知 Ra = 2MFLOPS ， = 0.7，解出第七章 (P446) 7.3 已知输入端编号13 = 1101B 。(1)Cube3(1101B) = 0101B = 5 (2)PM2+3(13) = (13 + 23)mod 16 = 21 mod 16 = 5 (3)PM2+0(13) = (13 - 20)mod 16 = 12 (4)Shuffle(1101B) = 1011B = 11 (5)Shuffle(Shuffle(110

31、1B) = Shuffle(1011B) = 0111B = 7 7.4 用多级混洗交换网络，n = 4 ，拓扑结构同教材P410图 7.21(e) ，控制信号 =1010B，自左向右各级交换开关状态依次为交换直连交换直连。7.5 输入结点编号j = 9，f(j) = j控制信号 = 1001B 1100B = 0101B = 5，答为 5 号处理机。7.6 直连状态时：编号在第i 位不同的结点之间不能通信；Ra (MFLOPS) 10 1 0 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

32、 - - 第 10 页，共 15 页 - - - - - - - - - 第 11 页交换状态时：编号在第i 位相同的结点之间不能通信。7.7 用单级混洗交换网可实现，总共混洗3 步。证：设矩阵A = (aij)8 8按行展开依次存放在64 个单元中，则任意元素aij的地址为 8i + j ，而 aji的地址为 8j + i 。按混洗函数的定义，3 次混洗后， shuffle3(8i + j) = 8(8i + j) mod 63 = i + 8j，也就说将元素aij地址变换成 aji的地址。由于aij是矩阵中的任意元素，所以3 次混洗可实现矩阵转置(aij)T88=(aji)8 8。7.8

33、最多 5 级， 因为对于任给的输入结点编号j=X6X5X4X3X2X1X0， PM2I多级网络中 i=2 级的功能是 PM2 2(j)=j22mod 128， 22运算只有可能改变j 中的 X6X2，所以最多使用Cube6Cube2就能实现代换了。7.9 由于 N = 16 ，即 n = 4 ，每个结点编号用4 位二进制数表示。PM2 0函数功能是对结点编号加1 或减 1，其结果最多可将编号的4 位都取反（如1111B + 1 = 0000B） ，所以用每步只能对1 位取反的单级立方体网络来模仿，最差情况下要4 步。7.10 用混洗交换网络模拟Cube网。当模拟 Cube0功能时，只需一次交换

34、即可完成；而模拟Cubei且 i 0 时，需先作 n i 步混洗，再作1 步交换，最后作 i 步混洗才能完成，共计n + 1步。综上所述，下限为1 步，上限为 n + 1步。7.11 求单级立方体网络和单级混洗交换网络的最大广播步数，这两种网络的最大广播步数与最大距离（即直径）相同。(1) 单级立方体网络直径 = n （Cuben-1Cube0各 1 次） ；(2) 单级混洗交换网络直径 = 2n-1（n-1 次混洗， n 次交换）。7.12 已知 N = 16，用多级立方体网络或者多级混洗交换网络均能实现，两者可以互相模拟，对同一置换的寻径算法相同，控制信号也相同，下面以多级立方体网络为例分

35、析。4 组 4 元交换： f1 = Cube1Cube0；2 组 8 元交换： f2 = Cube2Cube1Cube0；1 组 16 元交换： f3 = Cube3Cube2Cube1Cube0；利用 Cube函数的结合律、交换律以及同一律（又称自反律）可以推得f = f1f2f3 = Cube3Cube1Cube0拓扑结构图略（可参考7.26 题的多级混洗交换网络拓扑结构图）。网络开关使用级控方式，控制信号为1011B（其中 biti控制级 i ， “0”表示直连，“1”表示交换）。7.13 N = 8的蝶式置换。(1) f(X2X1X0) = X0X1X2；(2) 至少需 2 次通过，每

36、次都是N个数据同时发送，同时接收，中途不储存；(3) 控制信号的设置有4 种方案，如下所示。其中“0”表示直连，“1”表示交换。 101 100 001 101 000 000 000 000 000 000 000 000 101 100 001 101 000 000 000 000 101 100 001 101 101 100 001 101 000 000 000 000 7.14 (1) 共 N!种；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页

37、- - - - - - - - - 第 12 页(2) 一次通过有2NN种不同；(3) N = 8时，百分比 = %16.10%100!88%100!42NNN7.26(1)(3) ；(1) 见下图实线。(2) 见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。(3) 一次通过实现的置换数为16 8 = 4294967296 ，全部置换数为N! = 20922789888000 ，前者约占后者的0.02%。7.27 (1) 已知 N = 64 ，n = 6 ，源结点 s = 101101B ，目的结点d = 011010B ，方向矢量 r = s d = 1

38、10111B ，以低维度优先顺序寻径，路径为s = 101101B 101100B 101110B 101010B 111010B 011010B = d （下划线为当前寻径维）(2) 求给定无向图中2 棵选播树（即生成树） 。(i) 求最小成本生成树（通道数最少），可考虑 Prim 算法、 Kruskal算法或标记法。一个参考操作方法是：先对临近结点群分别构造最短子树，然后在子树之间作最短互连。(ii) 求由结点 (3,5) 出发的单源最短路径生成树（各距离最短），可考虑贪心算法。对X-Y 网格图来说，从树根到某一树叶的任何路径只要在各维均无反向移动即为最短路径（满足此条件的最短路径有多条）

39、。要得到单一树根对于多片树叶的综合最短路径，可以先分别作出各条单播最短路径，然后在不增加各路径长度的前提下，尽可能地进行路段合并。级 3 级 2 级 1 级 0 0000 0000 0001 0001 0010 0010 0011 0011 0100 0100 0101 0101 0110 0110 0111 0111 1000 1000 1001 1001 1010 1010 1011 1011 1100 1100 1101 1101 1110 1110 1111 1111 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

40、精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 第 13 页这两小问结果如下图所示（其中b 图第一步必须选择向下，而不能向右）。(a) (b) (3) 求作超立方体贪心选播树。7.29 已知 N = 256 ，n = 8 ，起始结点编号j = 123 = 01111011B。根据混洗函数的循环移位性质，Shuffle10(j) = Shuffle2(j) = 11101101B = 237第八章 (P498) 8.12 问题为 S=A1 B1+ +A32B32，其中 T乘=4t，T加=2t ，T传=1t 。(1) 在串行计算机上，各操作不论

41、是否相关均不能重叠，总时间恒等于各操作单独时间之和，所以不必考虑运算顺序。 T=32T乘+31T加=(32 4+312) t=190 t (2) 设此双向环可以并行传送（即为“移数环”，因为 SIMD系统各种数据操作都能并行）。按平均分配原则，每个结点内有4 对数据。首先在各结点用串行算法它们的相乘与求和，需时T1=4T乘+3T加=(4 4+32) t=22 t ；然后用二叉树并行算法将8 个结点中的部分和相加（见下图），其中并行加法需3 次，每次时间相同，而并行传送 3 次的每次时间却随距离倍增，依次为1、2、4 步，所以有 T2=(1+2+4) T传+3T加=(71+32)t=13t ；总

42、时间 T=T1+T2=35t 0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7 0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 0,4 1,4 2,4 3,4 4,4 5,4 6,4 7,4 0,3 1,3 2,3 3,3 4,3 5,3 6,3 7,3 0,2 1,2 2,2 3,2 4,2 5,2 6,2 7,2 Y 0,1 1,1 2,1 3,1 4,1 5,1 6,1 7,1 0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 X 0,7 1,7 2,7 3,7 4,7 5,7 6

43、,7 7,7 0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 0,4 1,4 2,4 3,4 4,4 5,4 6,4 7,4 0,3 1,3 2,3 3,3 4,3 5,3 6,3 7,3 0,2 1,2 2,2 3,2 4,2 5,2 6,2 7,2 Y 0,1 1,1 2,1 3,1 4,1 5,1 6,1 7,1 0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 X 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

44、 - - - - - - 第 13 页，共 15 页 - - - - - - - - - 第 14 页第九章 (P562) 9.18 问题为 S=(A1+B1)(A8+B8) ，其中 T加=30ns，T乘=50ns，T传=10ns。将加法记为任务1-8 ，乘法记为任务9-15 。(1) 在串行计算机上，同8.12 题 1 问分析，共计15 步运算， T=8T加+7T乘=(830+750)ns=590ns 。(2) 多功能部件 SISD 计算机的工作方式可参考P346题 18(3) 。为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。T=2T加+7T乘

45、=(230+750)ns=410ns (3) 同 8.12 题 2 问，设单向环可以并行传送（即为“移数环”，理由同 8.12 题 2 问） 。T=T加+3T乘+(1+2+4) T传=(30+3 50+710)ns=250ns s = s1+ s2+ s3+ s4+ s5+ s6+ s7+ s8. 右传 20步加法 1 步. 右传 21步加法 1 步. 右传 22步加法 1 步15 8 14 750ns A8 B8 7 13 乘法 9 10 11 12 15 加法 1 2 3 4 5 6 7 8 A7 B7 830ns 9 2 1 A2 B2 A1 B11 2 3 4 5 6 7 8 10 2

46、0 40 2 4 6 8 传送4 8 乘法50 50 50 8 加法 30名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 第 15 页(4) 在全互连网络上，任意两个结点之间的距离均为1 步，所以任何置换都能在1 步完成，故T=T加+3T乘+(1+1+1) T传=(30+3 50+310)ns=210ns 10 10 10 传送乘法50 50 50 加法 30名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -