计算机系统结构课后习题答案

级3 级2 级1 级0 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 7.27

(1) 已知N = 64，n = 6，源结点s = 101101B，目的结点d = 011010B，方向矢量r = s⊕d = 110111B，以低维度优先顺序寻径，路径为

s = 101101B → 101100B → 101110B → 101010B → 111010B → 011010B = d （下划线为当前寻径维）

(i) 求最小成本生成树（通道数最少），可考虑Prim算法、Kruskal算法或标记法。一个参考操作方法是：先对临近结点群分(ii) 求由结点(3,5)出发的单源最短路径生成树（各距离最短），可考虑贪心算法。对X-Y网格图来说，从树根到某一树叶的(2) 求给定无向图中2棵选播树（即生成树）。 别构造最短子树，然后在子树之间作最短互连。

任何路径只要在各维均无反向移动即为最短路径（满足此条件的最短路径有多条）。要得到单一树根对于多片树叶的综合最短路径，可以先分别作出各条单播最短路径，然后在不增加各路径长度的前提下，尽可能地进行路段合并。

这两小问结果如下图所示（其中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 102 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)

(a)

(3) 求作超立方体贪心选播树。

7.29 已知N = 256，n = 8，起始结点编号

j = 123 = 01111011B。根据混

洗函数的循环移位性质，Shuffle(j) = Shuffle(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系统各种数据操作都能并行）。

s = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8

①.右传20步 加法1步 ②.右传21步 加法1步 ③.右传22步 加法1步

按平均分配原则，每个结点内有4对数据。

首先在各结点用串行算法它们的相乘与求和，需时T1=4·T乘+3·T加=(4×4+3×2)Δt=22Δt；

然后用二叉树并行算法将8个结点中的部分和相加（见下图），其中并行加法需3次，每次时间相同，而并行传送3次的每次总时间T=T1+T2=35Δt

乘

时间却随距离倍增，依次为1、2、4步，所以有T2=(1+2+4)·T传+3·T加=(7×1+3×2)Δt=13Δt；

第九章(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)。

(3) 同8.12题2问，设单向环可以并行传送（即为“移数环”，理由同8.12题2问）。

A2 B2 A1 B1

2 1

9 A8 B8 7

A7 B7 13

乘法

9 10 11 12 8×30ns 15 加法 1 2 3 4 5 6 7 8

8 14

7×50ns

15 为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。T=2·T加+7·T乘=(2×30+7×50)ns=410ns

T=T加+3·T乘+(1+2+4)·T传=(30+3×50+7×10)ns=250ns

(4)在全互连网络上，任意两个结点之间的距离均为1步，所以任何置换都能在1步完成，故 T=T加+3·T乘+(1+1+1)·T传=(30+3×50+3×10)ns=210ns

10 10

10

50 传送 乘法 加法 30 50 50 1

2 2 3 4 4 4 5 6 6 7 8 8 8 8

10 20

40

50 传送 乘法 加法 30 50 50