计算机体系结构 第九章 （附带移数网络直径证明和取值情况）

9.1

1.设32个处理器编号为0、1、…、31.
(1)分别计算下列互连函数:
$$\begin{array}{rl}& {\mathrm{Cube}}_2(12)\sigma (8)\beta (9){PM2I}_{+3}(28){\mathrm{Cube}}_0(\sigma (4))\\ & \sigma ({\mathrm{Cube}}_0(18))\end{array}$$
(2)用$Cub{e}_0$和$\sigma$构成混洗交换网(每步只能使用$Cub{e}_0$或$\sigma$一次),网络直径是多少?从5号处理机发送数据到7号处理机,最短路径要经过几步?请列出经过的处理机编号。

(3)采用移数网络构成互联网，网络直径是多少？节点度是多少？与 2 号处理机距离最远的是几号处理机？

解：
(1)

• $Cub{e}_2(12)=12\oplus 4=8$
• $\sigma (8)=8<<1=16$
• $\beta (9)=swap(4,0)(9)=24$
• $PM2I_{+3}(28)=28+2^3\mathrm{mod}32=4$
• $Cub{e}_0(\sigma (4))=Cub{e}_0(8)=9$
• $\sigma (Cub{e}_0(18))=\sigma (19)=7$

(2)
考虑到操作为 $Cub{e}_0$ 和 $\sigma$，可以证明，对于任意起点和终点，交替 $Cub{e}_0$（当然可以不执行$Cub{e}_0$） 和 $\sigma$ 可以到达任何终点。
所以直径的上界是 $2n-1=9$，再考虑起点为 0，终点为 1 的情况，可以发现每次都必须执行 $Cub{e}_0$，故上界取得到。所以直径为 9。

5 = 00101， 7 = 00111，最短路径为：
$5(00101)->4(00100)->8(01000)->9(01001)->18(10010)->19(10011)->7(00111)$
故最短路径需要 6 步，经过的处理机编号为 5,4,8,9,18,19,7。

(3)
这里给出证明的简洁思路：
考虑到PM2I可正可负，故距离取值只有 $0\sim 2^{n-1}$，但距离取 $2^{n-1}$，只需一次PM2I即可，故接下来都只考虑 $0\sim 2^{n-1}-1$，但是还是可以操作第 $n$ 位的。
首先可以发现，对于连续出现的超过2个1，我们可以取补的方式来减少PM2I的次数，故可得，直径中不可能出现连续的超过2个1。
假设有 x 个 0，分类讨论：

• 操作 1：只需要 $n-1-x$ 次即可
• 操作 0：先构造全 1，需要 2 次，故最终只需要 $2+x$ 次即可

即最终需要
$$\min (2+x,n-1-x),1\le x\le n-1$$
可得中点为 $\lfloor \frac{n+1}{2}\rfloor =\lceil \frac{n}{2}\rceil$，所以可得直径的距离型为

• 当 $n$ 为偶数时：分两种情况
  • $n-1-x$ 小：$L_1=\mathrm{1010...1010}$
  • $2+x$ 小：$L_2=\mathrm{1010...10111010...1010}$ ，即中间出现唯一一个连续3个1
• 当 $n$ 为奇数时：$L=\mathrm{1010..0110...1010}$，即偶数的 $L_1$ 中任意1个1后再插入一个1（取决于奇数偶数）。

可以证得，对于任意情况，$N-L$ 需要的次数严格大于等于 $L$ 需要的次数，因为 $L$ 的类型很少，所以分类讨论即可。

所以这个边界可以取到。

所以直径为 $\lceil \frac{n}{2}\rceil$。

在此题中，$n=5$，所以直径为 3。节点度数为 $2n-1=9$。

同时可求得此题中距离为 $10110=13,11010=11$，所以距离最远的处理机为 $13,15,21,23$。

9.2

2.用N=8的三级Omega网络连接8个处理机(P0~P7)
8个处理机的输出端分别依次连接Omega的8个输入端0 ~ 7,8个处理机的输入端分别依次连接Omega的8个输出端0 ~ 7,处理机P6要把数据播送到处理机PO ~ P4,
处理机P3要把数据播送到处理机P5~P7.
能否同时为它们的播送要求实现连接,画出开关状态图。

解：

开关状态图如下：留白处开关任意状态即可。