计算机体系结构第三章练习题参考解答

3.26 设16个处理器编号分别为0，1，…，15，要用单级互连网络，当互连函数分别为：（1）Cube3（Cube1） （5）Butterfly（Butterfly） （8）1 （9） （13）(2)

(1)时，第13号处理器分别与哪一个处理器相连?

解：（1）因为Cube3（Cube1(X3X2X1X0)）= Cube3(X3X2X1X0)= X3X2X1X0 所以13 → Cube3（Cube1(1101)）= 0100 → 4

（5）因为Butterfly（Butterfly(X3X2X1X0)）=Butterfly（X0X2X1X3）=X3X2X1X0

所以13 →Butterfly（Butterfly (1101)）= 1101 → 13 （8）因为1(X3X2X1X0)= X0X3X2X1 所以13 →1 (1101)= 1110 → 14 （9）因为(X3X2X1X0)= X3X2X0X1 所以13 → (1101)= 1110 → 14

(1)(1) （13）因为(X3X2X1X0)= X1X2X3X0 所以13 →(2) (1101)= 0111 → 7

(1)

3.30 在有16个处理器的均匀洗牌网络中，若要使第0号处理器与第15号处理器相连，需要经过多少次均匀洗牌和交换置换。

解：0（0000B）号处理器与15（1111B）号处理器相连要对四位取反。交换置换一次只能对一位取反，所以要四次交换置换。交换置换每次取反只对最低位，要有三次移位，所以要四次均匀洗牌置换。

即变换为0000(E)→ 0001(σ)→ 0010(E)→ 0011(σ)→ 0110(E)→ 0111(σ)→1110(E)→ 1111。

3.34 在编号分别为0，1，2，……，9的16个处理器之间，要求按下列配对通信：(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。试选择所用互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级的交换开关状态图。

解：16个处理机通过N = 16的互连网络互联，通信配对连接的二进制编号为： (0、A)：0000---1010 (8、2)：1000---0010 (1、B)：0001---1011 (9、3)：1001---0011 (2、8)：0010---1000 (A、0)：1010---0000 (3、9)：0011---1001 (B、1)：1011---0001 (4、E)：0100---1110 (C、6)：1100---0110 (5、F)：0101---1111 (D、7)：1101---0111 (6、C)：0110---1100 (E、4)：1110---0100 (7、D)：0111---1101 (F、5)：1111---0101

显然要求互连网络实现的互联函数为f（X3X2X1X0）= X3X2X1X0，为多重方体置换。

N = 16的STARAN网络在级控方式下实现的是方体置换，且当级控信号为F = f3f2f1f0 = 1010时，实现的互联函数是Cube3（Cube1（X3X2X1X0））= X3X2X1X0。所以采用N = 16的STARAN网络在级控方式且级控信号F = 1010时，可实现要求配对通信。

0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F

3.41 写出N=8的蝶式置换的互连函数，如采用Omega网络，则需几次通过才能完成此变换？画出Omega网络实现此变换的控制状态图。

解：（1）N=8的蝶式置换的互连函数为：β（X2X1X0）= X0X1X2

（2）根据Omega网络采用单元控制终端标记法寻径方法，蝶式交换的连接关系及用N=8的Omega网络实现该连接的开关要求如下表所示。

S D d2 d1 d0 K2级开关 K1级开关 K0级开关

0 0 0 0 0 与K21上输出端连接 与K11上输出端连接 与K01上输出端连接 1 4 1 0 0 与K22下输出端连接 与K14上输出端连接 与K03上输出端连接 2 2 0 1 0 与K23上输出端连接 与K11下输出端连接 与K02上输出端连接 3 6 1 1 0 与K24下输出端连接 与K14下输出端连接 与K04上输出端连接 4 1 0 0 1 与K21上输出端连接 与K11上输出端连接 与K01下输出端连接 5 5 1 0 1 与K22下输出端连接 与K14上输出端连接 与K03下输出端连接 6 3 0 1 1 与K23上输出端连接 与K11下输出端连接 与K02下输出端连接 7 7 1 1 1 与K24下输出端连接 与K14下输出端连接 与K04下输出端连接

由表可见，当实现八个结点对连接时，对K2级开关的要求将发生下列争用开关输出端的

冲突：

0 → 0 和 4 → 1 争用开关K21上输出端 1 → 4 和 5 → 5 争用开关K22下输出端 2 → 2 和 6 → 3 争用开关K23上输出端 3 → 6 和 7 → 7 争用开关K24下输出端

因此，为避免K2级开关输出端的冲突，八个结点对连接分两次实现。第一次实现：0 → 0、1 → 4、2 → 2、3 → 6；第二次实现：4 → 1、5 → 5、6 → 3、7 → 7。分两次实现连接也避免K1级开关K11和K14输出端的冲突，K0级四个开关没有输出端的冲突。

第一次

第二次

（3）Omega网络分2次连接的开关状态如下图。 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3

4 5 6 7 0 1 2 3 4 5 6 7

3.55 对于4方体网络见图3-65，从结点0000到结点1111，有多少条最短路径？为什么？用E—立方维序寻径算法找出其中一条最短路径。

解：（1）当源节点与目的节点的海明距离为h，则有h!条最短路径。结点0000到结点1111的海明距离为4，所以有1×2×3×4=24条最短路径。

（2）方向位向量R = S⊕D = 0000⊕1111 = 1111，V = S = 0000（源节点）

r1=1，V = V⊕2i-1 = 0000⊕0001 = 0001； r2=1，V = V⊕2i-1 = 0001⊕0010 = 0011； r3=1，V = V⊕2i-1 = 0011⊕0100 = 0111；

i-1

r4=1，V = V⊕2 = 0111⊕1000 = 1111（目的结点）。

所以，0000与1111有一条最短路径为：S=0000→0001→0011→0111→1111=D。