第7章 互连网络
7.1 解释以下术语
静态互连网络：各结点之间有固定的连接通路、且在运行中不能改变的网络。
动态互连网络：由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。
互连函数：用变量x表示输入，用函数f(x)表示输出。则f(x)表示：在互连函数f的作用下，输入端x连接到输出端f(x)。它反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系，所以互连函数有时也称为置换函数或排列函数。
网络直径：指互连网络中任意两个结点之间距离的最大值。
7.3 设E为交换函数，S为均匀洗牌函数，B为蝶式函数，PM2I为移数函数，函数的自变量是十进制数表示的处理机编号。现有32台处理机，其编号为0，1，2， ，31。
（1）分别计算下列互连函数
E2（12） S（8） B（9） PM2I+3（28） E0（S（4）） S（E0（18））
（2）用E0和S构成均匀洗牌交换网（每步只能使用E0和S一次），网络直径是多少？从5号处理机发送数据到7号处理机，最短路径要经过几步？请列出经过的处理机编号。
（3）采用移数网络构成互连网，网络直径是多少？结点度是多少？与2号处理机距离最远的是几号处理机？
解：（1）共有32个处理机，表示处理机号的二进制地址应为5位。
E2（12）＝E2（01100）＝01000（8） S（8）＝S（01000）＝10000（16） B（9）＝B（01001）＝11000（24） PM2I+3（28）＝28＋23 mod32 ＝4 E0（S（4））＝E0（S（00100））＝01001（9） S（E0（18））＝S（E0（10010））＝S（10011）＝00111（7）
（2）2n个结点的均匀洗牌交换网的网络直径为2n-1，32个结点的均匀洗牌交换网的网络直径为9。
从5号处理机发送数据到7号处理机，最短路径要经过6步：
00101→00100→01000→01001→10010→10011→00111
（3）网络直径是3，结点度是9，与2号处理机距离最远的是13、15、21、23号处理机。
7.7用一个N=8的三级Omega网络连接8个处理机（P0~P7），8个处理机的输出端分别依序连接Omega网络的8个输入端0~7，8个处理机的输入端分别依序连接Omega网络的8个输出端0~7。如果处理机P6要把数据播送给处理机P0~P4，处理机P3要把数据播送给处理机P5~P7，那么，Omega网络能否同时为它们的播送要求实现连接？画出实现播送的Omega网络的开关状态图。
解：Omega网络使用的2×2开关有4种状态：直送、交叉、上播、下播。置换连接只使用直送和交叉状态，播送连接还需要使用上播和下播状态。分别画出实现处理机P6和P3的播送连接要求使用的开关状态，如果没有开关状态和开关输出端争用冲突，就可以使用播送连接。实际上，它们的播送要求没有冲突，因此，可以同时实现，同时实现的Omega网