清华第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中(3)(4)(6)(8)问（地址映象/替换算法--实存状况图）
第四章(P250)
4.5（中断屏蔽字表/中断过程示意图），4.8（通道流量计算/通道时间图）
第五章(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题。有下划线者为推荐的主要知识点。)
第一章(P33)
1.7
(1)从指定角度来看，不必要了解的知识称为透明性概念。
(2)见下表，“√”为透明性概念，“P”表示相关课文页数。
模m交叉，√，
浮点数据，×，P4
通道与I/O处理机，×，P4
总线宽度，√，
阵列运算部件，×，
结合型与独立型通道，√，
单总线，√，
访问保护，×，
中断，×，
指令控制方式，√，
堆栈指令，×，
最小编址单位，×，
Cache存储器，√，
1.8见下表，“√”为透明性概念，“P”表示相关课文页数。
指令地址寄存器，×，
指令缓冲器，√，
时标发生器，√，
条件码寄存器，×，
乘法器，√，
主存地址寄存器，√，
磁盘，×，
先行进位链，√，
移位器，√，
通用寄存器,×，
中断字寄存器，×，
1.9见下表，“√”表示都透明，“应”表示仅对应用程序员透明，“×”表示都不透明。
数据通路宽度，√，
虚拟存储器，应，
Cache存储器，√，
程序状态字，×，
“启动I/O”指令，应，
“执行”指令，×，
指令缓冲寄存器，√，
Sn
20
1
0 1 Fe
1.12 已知Se=20,求作Fe-Sn关系曲线。
将Se代入Amdahl定律得
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%（20→40），而软件组只需将Fe再提高1.84%（0.7→0.7184）。
1.17
1.18 记f ── 时钟频率，T=1/f ── 时钟周期，B ── 带宽（Byte/s）。
方案一：
方案二：
1.19 由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。
(1)
(2)
(3)
1.21
(1)
(2)
1.24 记Tc ── 新方案时钟周期，已知CPI = CPIi = 1
原时间 = CPI × IC × 0.95Tc = 0.95IC×Tc
新时间 = （0.3×2/3+0.7）× IC × Tc = 0.9IC×Tc
二者比较，新时间较短。
第二章(P124)
2.3（忽略P124倒1行 ～ P125第8行文字，以简化题意）已知2种浮点数，求性能指标。
此题关键是分析阶码、尾数各自的最大值、最小值。
原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。
由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“±最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“±最小绝对值”回答。
第1小问中，阶码全部位数为8，作无符号数看待真值为0～255，作移-127码看待真值为-127～+128；尾数（不计符号位）有23位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0 – 2-23，有效位数p=24；
第2小问中，阶码全部位数为11，作无符号数看待真值为0～2047，作移-1023码看待真值为-1023～+1024；尾数（不计符号位）有52位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0 – 2-52，有效位数p=53。
最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。
32位
64位
±最大绝对值
±(1-2-24)·2129
±(1-2-53)·21025
±最小绝对值
±2-127
±2-1023
表数精度δ
2-24
2-53
表数效率η
100%
100%
2.5
(1) rm = 2，re = 2，p = 24（隐藏最高位）,q = 7。
(2) Nmax = 1.7×1038，-|N|min = -1.47×10-39
δ ≤ 5.96×10-8 ≈ 10-7.22，η = 100%
2.6
1位
7位
6位
0
0111111
333333
(1) 0.2 = 0.333333H×160
设阶码为移-63码（即-26+1，原题未指明）
0.2 = 0.110011001100110011001101B×2-2
1位
8位
23位
0
01111101
10011001100110011001101
（其中最高有效位需隐藏）
阶码为移-127码（即-27+1）
(2) 符号位不变，（阶码 – 63）×4 + 127；尾数左规，除去最高位；
(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条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。
Huffman编码
2/8扩展编码
3/7扩展编码
平均码长L
2.99
3.1
3.2
信息冗余量R
1.10%
4.61%
7.59%
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 < T64K
c256K > c128K > c64K
(4)19.092，11.97，10.0064。答案是256K方案最优。
3.5 已知，其中g=0.1
依题意有
整理得0.9n≥0.2，解出，向下取整，得15；
按另一种题意理解是向上取整，得16，也对。
3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。
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
(1)Hmax=7/12≈58.3%
(2)n=4
(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中（折算为7×1024次单元命中），5次页不命中（折算为5×1023次单元命中，也可写为5×1024-5），单元访问总次数为12×1024，故有：
Hcell=(12×1024-5)/(12×1024)=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)命中次数之和最大。
P1 =
1
2
3
4
1
3
2
1
命中次数N(1)
1
2
3
4
1
3
2
1
1
2
3
4
1
3
2
1
2
3
4
1
3
1
2
2
4
4
n1= 1
0
n1= 2
0
n1= 3
√
√
2
n1= 4
√
√
√
√
4
解：分别为2道程序作“堆栈模拟图”，其中“√”表示命中。
P2 =
1
2
3
4
2
2
3
3
命中次数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
将两图结果综合，得到4个分配方案的命中率情况表如下
n1
1
2
3
4
N(1)
0
0
2
4
n2
4
3
2
1
N(2)
4
4
2
2
N(1)+N(2)
4
4
4
6
结论如下
(1)命中率相同的方案是n1= 3而n2= 2；
(2)命中次数之和最大的方案是n1= 4而n2= 1。
3.19中(3)(4)(6)(8)问
虚存 实页 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) 对应关系表（√为有关系）
(3)
(4)通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。
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
3*
3
入
入
入
入
中
中
替
替
中
替
替
中
C=
2
3
0
1
0
2
3
1
0
1
2
3
此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。
(6)H=4/12≈33%
(8)做法同3.15题(3)问，Hcell=(12×16-8)/(12×16)≈95.8%
第四章(P250)
时间 中断请求 主程序 1级 2级 3级 4级
D1，D2
D3，D4
4.5 已知中断服务次序为3-2-4-1，。
(1)中断屏蔽字表如下图；
D1
D2
D3
D4
D1
0
1
1
1
D2
0
0
1
0
D3
0
0
0
0
D4
0
1
1
0
(2)中断过程示意图如右图。
4.8
(1)f=2×105字节/秒，T=5us
(2)Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。
设 优备 先号 级
D1 1
D2 4
D3 2
D4 3
时间
(us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170
(3)5，160，20，40；
(4)D2丢失第一次请求的数据；
(5)参见P245。
第五章(P343)
5.9 为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。
记c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。
F=c1+c2+c3+c4+c5+c6 6 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)
根据时空图(b)得
TP = 11/(22Δt) = 1/(2Δt)
S = (6×4Δt + 5×4Δt)/(22Δt) = 2
E = (6×4Δt + 5×4Δt)/(6×22Δt) = 1/3
5.15 Δt=10ns=10-8秒
(1)F={1，2，5}，C=(10011)
(2)状态转移图如下图(a)所示。
(3)最小启动循环=（3）,最小平均启动距离=3Δt。
(4)插入2个延迟，最小启动循环=（2）,最小平均启动距离=2Δt。
(5)新预约表如下图(b)所示。
1 2 3 4 5 6 7 8 初态 4，6，≥8
S1 × 1 2 ×
初态 3，4，≥6 S2 × 1 × 1 0 0 0 1 0 1
S3 × 4，6，≥8 4，6，≥8
1 0 0 1 1 S4 1 × × 2 5
D1 × 1 0 1 0 1 0 1 1 0 0 0 1 1 1
D2 × 2 5
(a) (b) (c)
(6)F={1，3，7}，C=(1000101)，状态转移图如下图(c)所示。
(7)插入前TPmax = 1/3Δt = 1/30ns，插入后TPmax = 1/2Δt = 1/20ns。
(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下图所示。
S4 1 1 2 2 3 10 10
S3 1 2 3 ……… 10
S2 1 1 2 2 3 10 10
S1 1 2 1 3 2 10 10
3 t
(a) 插入前 9×3 6
D2 1 2 3 11
D1 1 2 3 4 10
S4 1 1 2 2 3 3 ……… 10 10
S3 1 2 3 4 10
S2 1 2 1 3 2 4 3 5 10 10
S1 1 2 3 4 1 5 2 10 10
2 t
(b) 插入后 9×2 8
第六章(P391)
6.6（注意阅读P372倒数第9行－倒数第6行）
(4) V0 ← 存储器 链接
V1 ← 1 / V0 链接
V3 ← V1 + V2 链接
V5 ← V3 * V4
访存
倒数
加
乘
8 16 8 9 31
总拍数=72（各条依次链接）
已知n=32，k加=6，k乘=7，k访存=6，k倒数=14，启动、输出延迟各1。求各小题总拍数。
(1) V0 ← 存储器
V1 ← V2 + V3 并行
V4 ← V5 * V6
访存
加
乘
9 31
总拍数=40（并行执行，以最长指令为准）
(2) V2 ← V0 * V1 并行
V3 ← 存储器
V4 ← V2 + V3 串行（P372）
乘
访存
加
9 31 8 31
总拍数=79（第3条错过时机，不能链接）
(3) V0 ← 存储器 并行
V3 ← V1 + V2 链接
V4 ← V0 * V3
V6 ← V4 + V5 串行
访存
加
乘
8 9 31 8 31
总拍数=87（第4条功能部件冲突）
(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 ← V2 * V1 串行
V5 ← V3 * V4 串行
访存
加
乘
8 8 31 9 31 9 31
总拍数=127（Vi冲突，功能部件冲突）
6.10 已知向量速率Rv = 10MFLOPS，标量速率Rs = 1MFLOPS，并记α为可向量化百分比。
(1) 推导法1：使用Amdahl定律，在这里可将标量速率Rs作为原速率，局部加速后的速率为向量速率Rv，于是局部加速比Se=10，全局加速比为
再根据加速比的定义，，所以有。
（若将向量速率Rv作为原速率，局部减速后的速率为标量速率Rs，则局部加速比Se=0.1，推出的全局加速比Sn同上式。）
推导法2：为了推导，定义T为总时间，N为总任务数。于是有平均速率Ra = 吞吐率TP = N/T。记N = Nv + Ns，且，则，于是有Nv = α·N和Ns = (1-α)·N
显然：总时间
所以：
或者：
Ra (MFLOPS)
10
1
0 1 α
(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(1101B)) = 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位不同的结点之间不能通信；
交换状态时：编号在第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)T8×8=(aji)8×8。
7.8 最多5级，因为对于任给的输入结点编号j=X6X5X4X3X2X1X0，PM2I多级网络中i=2级的功能是PM2±2(j)=j±22 mod 128，±22运算只有可能改变j中的X6～X2，所以最多使用Cube6～Cube2就能实现代换了。
7.9 由于N = 16，即n = 4，每个结点编号用4位二进制数表示。PM2±0函数功能是对结点编号加1或减1，其结果最多可将编号的4位都取反（如1111B + 1 = 0000B），所以用每步只能对1位取反的单级立方体网络来模仿，最差情况下要4步。
7.10 用混洗―交换网络模拟Cube网。
当模拟Cube0功能时，只需一次交换即可完成；而模拟Cubei且i≠0时，需先作n – i步混洗，再作1步交换，最后作i步混洗才能完成，共计n + 1步。
综上所述，下限为1步，上限为n + 1步。
7.11 求单级立方体网络和单级混洗―交换网络的最大广播步数，这两种网络的最大广播步数与最大距离（即直径）相同。
(1)单级立方体网络直径 = n（Cuben-1～Cube0各1次）；
(2)单级混洗―交换网络直径 = 2n-1（n-1次混洗，n次交换）。
7.12 已知N = 16，用多级立方体网络或者多级混洗―交换网络均能实现，两者可以互相模拟，对同一置换的寻径算法相同，控制信号也相同，下面以多级立方体网络为例分析。
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次通过，每次都是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!种；
(2) 一次通过有种不同；
(3) N = 8时，百分比 =
7.26(1)～(3)；
(1)见下图实线。
(2)见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。
(3)一次通过实现的置换数为16 8 = 4294967296，全部置换数为N! = 20922789888000，前者约占后者的0.02%。
级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
7.27
(1) 已知N = 64，n = 6，源结点s = 101101B，目的结点d = 011010B，方向矢量r = s⊕d = 110111B，以低维度优先顺序寻径，路径为
s = 101101B → 101100B → 101110B → 101010B → 111010B → 011010B = d （下划线为当前寻径维）
(2) 求给定无向图中2棵选播树（即生成树）。
(i) 求最小成本生成树（通道数最少），可考虑Prim算法、Kruskal算法或标记法。一个参考操作方法是：先对临近结点群分别构造最短子树，然后在子树之间作最短互连。
(ii) 求由结点(3,5)出发的单源最短路径生成树（各距离最短），可考虑贪心算法。对X-Y网格图来说，从树根到某一树叶的任何路径只要在各维均无反向移动即为最短路径（满足此条件的最短路径有多条）。要得到单一树根对于多片树叶的综合最短路径，可以先分别作出各条单播最短路径，然后在不增加各路径长度的前提下，尽可能地进行路段合并。
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
这两小问结果如下图所示（其中b图第一步必须选择向下，而不能向右）。
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
(a) (b)
(3) 求作超立方体贪心选播树。
7.29 已知N = 256，n = 8，起始结点编号j = 123 = 01111011B。根据混洗函数的循环移位性质，Shuffle10(j) = Shuffle2(j) = 11101101B = 237
第八章(P498)
8.12 问题为S=A1×B1+……+A32×B32，其中T乘=4Δt，T加=2Δt，T传=1Δt。
(1) 在串行计算机上，各操作不论是否相关均不能重叠，总时间恒等于各操作单独时间之和，所以不必考虑运算顺序。T=32·T乘+31·T加=(32×4+31×2)Δt=190Δt
(2) 设此双向环可以并行传送（即为“移数环”，因为SIMD系统各种数据操作都能并行）。
按平均分配原则，每个结点内有4对数据。
首先在各结点用串行算法它们的相乘与求和，需时T1=4·T乘+3·T加=(4×4+3×2)Δt=22Δt；
然后用二叉树并行算法将8个结点中的部分和相加（见下图），其中并行加法需3次，每次时间相同，而并行传送3次的每次时间却随距离倍增，依次为1、2、4步，所以有T2=(1+2+4)·T传+3·T加=(7×1+3×2)Δt=13Δt；
总时间T=T1+T2=35Δt
s = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8
①.右传20步
加法1步
②.右传21步
加法1步
③.右传22步
加法1步
第九章(P562)
9.18 问题为S=(A1+B1)×……×(A8+B8)，其中T加=30ns，T乘=50ns，T传=10ns。
将加法记为任务1-8，乘法记为任务9-15。
(1) 在串行计算机上，同8.12题1问分析，共计15步运算，T=8·T加+7·T乘=(8×30+7×50)ns=590ns。
(2) 多功能部件SISD计算机的工作方式可参考P346题18(3)。
为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。T=2·T加+7·T乘=(2×30+7×50)ns=410ns
15
8 14 7×50ns
A8 B8 7 13 乘法 9 10 11 12 15
加法 1 2 3 4 5 6 7 8
A7 B7 8×30ns
9
2 1
A2 B2 A1 B1
(3) 同8.12题2问，设单向环可以并行传送（即为“移数环”，理由同8.12题2问）。
1 2 3 4 5 6 7 8 10 20 40
2 4 6 8 传送
4 8 乘法 50 50 50
8 加法 30
T=T加+3·T乘+(1+2+4)·T传=(30+3×50+7×10)ns=250ns
(4)在全互连网络上，任意两个结点之间的距离均为1步，所以任何置换都能在1步完成，故
10 10 10
传送
乘法 50 50 50
加法 30
T=T加+3·T乘+(1+1+1)·T传=(30+3×50+3×10)ns=210ns
目录
第一章(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（通道流量计算/通道时间图）
第五章(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题。有下划线者为推荐的主要知识点。)
第一章(P33)
1.7
(1)从指定角度来看，不必要了解的知识称为透明性概念。
(2)见下表，“√”为透明性概念，“P”表示相关课文页数。
模m交叉，√，
浮点数据，×，P4
通道与I/O处理机，×，P4
总线宽度，√，
阵列运算部件，×，
结合型与独立型通道，√，
单总线，√，
访问保护，×，
中断，×，
指令控制方式，√，
堆栈指令，×，
最小编址单位，×，
Cache存储器，√，
1.8见下表，“√”为透明性概念，“P”表示相关课文页数。
指令地址寄存器，×，
指令缓冲器，√，
时标发生器，√，
条件码寄存器，×，
乘法器，√，
主存地址寄存器，√，
磁盘，×，
先行进位链，√，
移位器，√，
通用寄存器,×，
中断字寄存器，×，
1.9见下表，“√”表示都透明，“应”表示仅对应用程序员透明，“×”表示都不透明。
数据通路宽度，√，
虚拟存储器，应，
Cache存储器，√，
程序状态字，×，
“启动I/O”指令，应，
“执行”指令，×，
指令缓冲寄存器，√，
Sn
20
1
0 1 Fe
1.12 已知Se=20,求作Fe-Sn关系曲线。
将Se代入Amdahl定律得
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%（20→40），而软件组只需将Fe再提高1.84%（0.7→0.7184）。
1.17
1.18 记f ── 时钟频率，T=1/f ── 时钟周期，B ── 带宽（Byte/s）。
方案一：
方案二：
1.19 由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。
(1)
(2)
(3)
1.21
(1)
(2)
1.24 记Tc ── 新方案时钟周期，已知CPI = CPIi = 1
原时间 = CPI × IC × 0.95Tc = 0.95IC×Tc
新时间 = （0.3×2/3+0.7）× IC × Tc = 0.9IC×Tc
二者比较，新时间较短。
第二章(P124)
2.3（忽略P124倒1行 ～ P125第8行文字，以简化题意）已知2种浮点数，求性能指标。
此题关键是分析阶码、尾数各自的最大值、最小值。
原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。
由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“±最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“±最小绝对值”回答。
第1小问中，阶码全部位数为8，作无符号数看待真值为0～255，作移-127码看待真值为-127～+128；尾数（不计符号位）有23位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0 – 2-23，有效位数p=24；
第2小问中，阶码全部位数为11，作无符号数看待真值为0～2047，作移-1023码看待真值为-1023～+1024；尾数（不计符号位）有52位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0 – 2-52，有效位数p=53。
最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。
32位
64位
±最大绝对值
±(1-2-24)·2129
±(1-2-53)·21025
±最小绝对值
±2-127
±2-1023
表数精度δ
2-24
2-53
表数效率η
100%
100%
2.5
(1) rm = 2，re = 2，p = 24（隐藏最高位）,q = 7。
(2) Nmax = 1.7×1038，-|N|min = -1.47×10-39
δ ≤ 5.96×10-8 ≈ 10-7.22，η = 100%
2.6
1位
7位
6位
0
0111111
333333
(1) 0.2 = 0.333333H×160
设阶码为移-63码（即-26+1，原题未指明）
0.2 = 0.110011001100110011001101B×2-2
1位
8位
23位
0
01111101
10011001100110011001101
（其中最高有效位需隐藏）
阶码为移-127码（即-27+1）
(2) 符号位不变，（阶码 – 63）×4 + 127；尾数左规，除去最高位；
(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条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。
Huffman编码
2/8扩展编码
3/7扩展编码
平均码长L
2.99
3.1
3.2
信息冗余量R
1.10%
4.61%
7.59%
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 < T64K
c256K > c128K > c64K
(4)19.092，11.97，10.0064。答案是256K方案最优。
3.5 已知，其中g=0.1
依题意有
整理得0.9n≥0.2，解出，向下取整，得15；
按另一种题意理解是向上取整，得16，也对。
3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。
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
(1)Hmax=7/12≈58.3%
(2)n=4
(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中（折算为7×1024次单元命中），5次页不命中（折算为5×1023次单元命中，也可写为5×1024-5），单元访问总次数为12×1024，故有：
Hcell=(12×1024-5)/(12×1024)=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)命中次数之和最大。
P1 =
1
2
3
4
1
3
2
1
命中次数N(1)
1
2
3
4
1
3
2
1
1
2
3
4
1
3
2
1
2
3
4
1
3
1
2
2
4
4
n1= 1
0
n1= 2
0
n1= 3
√
√
2
n1= 4
√
√
√
√
4
解：分别为2道程序作“堆栈模拟图”，其中“√”表示命中。
P2 =
1
2
3
4
2
2
3
3
命中次数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
将两图结果综合，得到4个分配方案的命中率情况表如下
n1
1
2
3
4
N(1)
0
0
2
4
n2
4
3
2
1
N(2)
4
4
2
2
N(1)+N(2)
4
4
4
6
结论如下
(1)命中率相同的方案是n1= 3而n2= 2；
(2)命中次数之和最大的方案是n1= 4而n2= 1。
3.19中(3)(4)(6)(8)问
虚存 实页 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) 对应关系表（√为有关系）
(3)
(4)通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。
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
3*
3
入
入
入
入
中
中
替
替
中
替
替
中
C=
2
3
0
1
0
2
3
1
0
1
2
3
此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。
(6)H=4/12≈33%
(8)做法同3.15题(3)问，Hcell=(12×16-8)/(12×16)≈95.8%
第四章(P250)
时间 中断请求 主程序 1级 2级 3级 4级
D1，D2
D3，D4
4.5 已知中断服务次序为3-2-4-1，。
(1)中断屏蔽字表如下图；
D1
D2
D3
D4
D1
0
1
1
1
D2
0
0
1
0
D3
0
0
0
0
D4
0
1
1
0
(2)中断过程示意图如右图。
4.8
(1)f=2×105字节/秒，T=5us
(2)Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。
设 优备 先号 级
D1 1
D2 4
D3 2
D4 3
时间
(us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170
(3)5，160，20，40；
(4)D2丢失第一次请求的数据；
(5)参见P245。
第五章(P343)
5.9 为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。
记c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。
F=c1+c2+c3+c4+c5+c6 6 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)
根据时空图(b)得
TP = 11/(22Δt) = 1/(2Δt)
S = (6×4Δt + 5×4Δt)/(22Δt) = 2
E = (6×4Δt + 5×4Δt)/(6×22Δt) = 1/3
5.15 Δt=10ns=10-8秒
(1)F={1，2，5}，C=(10011)
(2)状态转移图如下图(a)所示。
(3)最小启动循环=（3）,最小平均启动距离=3Δt。
(4)插入2个延迟，最小启动循环=（2）,最小平均启动距离=2Δt。
(5)新预约表如下图(b)所示。
1 2 3 4 5 6 7 8 初态 4，6，≥8
S1 × 1 2 ×
初态 3，4，≥6 S2 × 1 × 1 0 0 0 1 0 1
S3 × 4，6，≥8 4，6，≥8
1 0 0 1 1 S4 1 × × 2 5
D1 × 1 0 1 0 1 0 1 1 0 0 0 1 1 1
D2 × 2 5
(a) (b) (c)
(6)F={1，3，7}，C=(1000101)，状态转移图如下图(c)所示。
(7)插入前TPmax = 1/3Δt = 1/30ns，插入后TPmax = 1/2Δt = 1/20ns。
(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下图所示。
S4 1 1 2 2 3 10 10
S3 1 2 3 ……… 10
S2 1 1 2 2 3 10 10
S1 1 2 1 3 2 10 10
3 t
(a) 插入前 9×3 6
D2 1 2 3 11
D1 1 2 3 4 10
S4 1 1 2 2 3 3 ……… 10 10
S3 1 2 3 4 10
S2 1 2 1 3 2 4 3 5 10 10
S1 1 2 3 4 1 5 2 10 10
2 t
(b) 插入后 9×2 8
第六章(P391)
6.6（注意阅读P372倒数第9行－倒数第6行）
(4) V0 ← 存储器 链接
V1 ← 1 / V0 链接
V3 ← V1 + V2 链接
V5 ← V3 * V4
访存
倒数
加
乘
8 16 8 9 31
总拍数=72（各条依次链接）
已知n=32，k加=6，k乘=7，k访存=6，k倒数=14，启动、输出延迟各1。求各小题总拍数。
(1) V0 ← 存储器
V1 ← V2 + V3 并行
V4 ← V5 * V6
访存
加
乘
9 31
总拍数=40（并行执行，以最长指令为准）
(2) V2 ← V0 * V1 并行
V3 ← 存储器
V4 ← V2 + V3 串行（P372）
乘
访存
加
9 31 8 31
总拍数=79（第3条错过时机，不能链接）
(3) V0 ← 存储器 并行
V3 ← V1 + V2 链接
V4 ← V0 * V3
V6 ← V4 + V5 串行
访存
加
乘
8 9 31 8 31
总拍数=87（第4条功能部件冲突）
(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 ← V2 * V1 串行
V5 ← V3 * V4 串行
访存
加
乘
8 8 31 9 31 9 31
总拍数=127（Vi冲突，功能部件冲突）
6.10 已知向量速率Rv = 10MFLOPS，标量速率Rs = 1MFLOPS，并记α为可向量化百分比。
(1) 推导法1：使用Amdahl定律，在这里可将标量速率Rs作为原速率，局部加速后的速率为向量速率Rv，于是局部加速比Se=10，全局加速比为
再根据加速比的定义，，所以有。
（若将向量速率Rv作为原速率，局部减速后的速率为标量速率Rs，则局部加速比Se=0.1，推出的全局加速比Sn同上式。）
推导法2：为了推导，定义T为总时间，N为总任务数。于是有平均速率Ra = 吞吐率TP = N/T。记N = Nv + Ns，且，则，于是有Nv = α·N和Ns = (1-α)·N
显然：总时间
所以：
或者：
Ra (MFLOPS)
10
1
0 1 α
(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(1101B)) = 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位不同的结点之间不能通信；
交换状态时：编号在第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)T8×8=(aji)8×8。
7.8 最多5级，因为对于任给的输入结点编号j=X6X5X4X3X2X1X0，PM2I多级网络中i=2级的功能是PM2±2(j)=j±22 mod 128，±22运算只有可能改变j中的X6～X2，所以最多使用Cube6～Cube2就能实现代换了。
7.9 由于N = 16，即n = 4，每个结点编号用4位二进制数表示。PM2±0函数功能是对结点编号加1或减1，其结果最多可将编号的4位都取反（如1111B + 1 = 0000B），所以用每步只能对1位取反的单级立方体网络来模仿，最差情况下要4步。
7.10 用混洗―交换网络模拟Cube网。
当模拟Cube0功能时，只需一次交换即可完成；而模拟Cubei且i≠0时，需先作n – i步混洗，再作1步交换，最后作i步混洗才能完成，共计n + 1步。
综上所述，下限为1步，上限为n + 1步。
7.11 求单级立方体网络和单级混洗―交换网络的最大广播步数，这两种网络的最大广播步数与最大距离（即直径）相同。
(1)单级立方体网络直径 = n（Cuben-1～Cube0各1次）；
(2)单级混洗―交换网络直径 = 2n-1（n-1次混洗，n次交换）。
7.12 已知N = 16，用多级立方体网络或者多级混洗―交换网络均能实现，两者可以互相模拟，对同一置换的寻径算法相同，控制信号也相同，下面以多级立方体网络为例分析。
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次通过，每次都是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!种；
(2) 一次通过有种不同；
(3) N = 8时，百分比 =
7.26(1)～(3)；
(1)见下图实线。
(2)见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。
(3)一次通过实现的置换数为16 8 = 4294967296，全部置换数为N! = 20922789888000，前者约占后者的0.02%。
级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
7.27
(1) 已知N = 64，n = 6，源结点s = 101101B，目的结点d = 011010B，方向矢量r = s⊕d = 110111B，以低维度优先顺序寻径，路径为
s = 101101B → 101100B → 101110B → 101010B → 111010B → 011010B = d （下划线为当前寻径维）
(2) 求给定无向图中2棵选播树（即生成树）。
(i) 求最小成本生成树（通道数最少），可考虑Prim算法、Kruskal算法或标记法。一个参考操作方法是：先对临近结点群分别构造最短子树，然后在子树之间作最短互连。
(ii) 求由结点(3,5)出发的单源最短路径生成树（各距离最短），可考虑贪心算法。对X-Y网格图来说，从树根到某一树叶的任何路径只要在各维均无反向移动即为最短路径（满足此条件的最短路径有多条）。要得到单一树根对于多片树叶的综合最短路径，可以先分别作出各条单播最短路径，然后在不增加各路径长度的前提下，尽可能地进行路段合并。
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
这两小问结果如下图所示（其中b图第一步必须选择向下，而不能向右）。
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
(a) (b)
(3) 求作超立方体贪心选播树。
7.29 已知N = 256，n = 8，起始结点编号j = 123 = 01111011B。根据混洗函数的循环移位性质，Shuffle10(j) = Shuffle2(j) = 11101101B = 237
第八章(P498)
8.12 问题为S=A1×B1+……+A32×B32，其中T乘=4Δt，T加=2Δt，T传=1Δt。
(1) 在串行计算机上，各操作不论是否相关均不能重叠，总时间恒等于各操作单独时间之和，所以不必考虑运算顺序。T=32·T乘+31·T加=(32×4+31×2)Δt=190Δt
(2) 设此双向环可以并行传送（即为“移数环”，因为SIMD系统各种数据操作都能并行）。
按平均分配原则，每个结点内有4对数据。
首先在各结点用串行算法它们的相乘与求和，需时T1=4·T乘+3·T加=(4×4+3×2)Δt=22Δt；
然后用二叉树并行算法将8个结点中的部分和相加（见下图），其中并行加法需3次，每次时间相同，而并行传送3次的每次时间却随距离倍增，依次为1、2、4步，所以有T2=(1+2+4)·T传+3·T加=(7×1+3×2)Δt=13Δt；
总时间T=T1+T2=35Δt
s = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8
①.右传20步
加法1步
②.右传21步
加法1步
③.右传22步
加法1步
第九章(P562)
9.18 问题为S=(A1+B1)×……×(A8+B8)，其中T加=30ns，T乘=50ns，T传=10ns。
将加法记为任务1-8，乘法记为任务9-15。
(1) 在串行计算机上，同8.12题1问分析，共计15步运算，T=8·T加+7·T乘=(8×30+7×50)ns=590ns。
(2) 多功能部件SISD计算机的工作方式可参考P346题18(3)。
为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。T=2·T加+7·T乘=(2×30+7×50)ns=410ns
15
8 14 7×50ns
A8 B8 7 13 乘法 9 10 11 12 15
加法 1 2 3 4 5 6 7 8
A7 B7 8×30ns
9
2 1
A2 B2 A1 B1
(3) 同8.12题2问，设单向环可以并行传送（即为“移数环”，理由同8.12题2问）。
1 2 3 4 5 6 7 8 10 20 40
2 4 6 8 传送
4 8 乘法 50 50 50
8 加法 30
T=T加+3·T乘+(1+2+4)·T传=(30+3×50+7×10)ns=250ns
(4)在全互连网络上，任意两个结点之间的距离均为1步，所以任何置换都能在1步完成，故
10 10 10
传送
乘法 50 50 50
加法 30
T=T加+3·T乘+(1+1+1)·T传=(30+3×50+3×10)ns=210ns
