第七章 互联网络 本章内容：介绍用于多机并行计算的各种网络，它们统称为互连网络，缩写符号是ICN（Interconnection Network）。

互连网络分类 当前提高计算速度的主要措施，一是改进器件，二是多机并行计算。 ICN是多机之间传输数据的高速通路，对整体性能起关键作用。 通用网（原用于计算机之间交换信息的普通网络） 专用网（专用于并行计算系统各处理单元之间并行交换数据的特殊网络）。

结点 结点 结点 结点 接口 接口 接口 接口 入 链路 出 链路 链路 链路 互连网络 0 1 2 N-1 0 1 2 N-1 互连网络在系统中的位置和作用 ICN 开关 网络 到处理单元或存储单元 从处理单元来 1 N-1

互连函数 N个输入到N个输出的一种对应状态可以用一个映射函数表示，称为互连函数。它是处理单元集合对于自身的双射映射，所以又称为“置换”，或者“循环”。 互连函数有多种表示方式，如下例所示： f(0)=1 0 0 f(1)=2 1 1 f= 0 1 2 3 f=(0,1,2)(3) f(2)=0 2 2 1 2 0 3 f(3)=3 3 3 a.枚举法 b.开关状态图 c.列表法 d.循环函数 还有函数表示法：f(Xn-1Xn-2…X1X0)，其中Xn-1Xn-2…X1X0为输入变量，为n位二进制。 一个网络通过开关切换可以形成多个映射关系，所以要用“互连函数族”来定义一个网络。

单级ICN 定义：单级ICN只使用一级开关，如下图所示。 开关的每种接通组合方式可用一个互连函数表示。 f( j入 ) = j出，0≤j≤N-1 在互连函数中，记： N ── 结点数 n = log2N ── 维数 j= Xn-1……X0 ── 结点 编号的二进制形式，位数为n。 互连函数族的组成必须使网络成为连通图。

单级立方体网（Cube网） 该网络由立方体函数定义，立方体函数族有n个成员，分别是Cube0，Cube1，……，Cuben-1。 立方体函数定义：Cubei的功能是对入端结点编号二进制形式的第i位取反 Cubei(Xn-1…Xi+1XiXi-1…X0)=Xn-1…Xi+1XiXi-1…X0，其中0≤i≤n-1 当N=16（结点）时，n=log216=4 Cube0(0)=Cube0(0000)2=(0000)2=(0001)2=1 Cube0(2)=Cube0(0010)2=(0010)2=(0011)2=3 Cube0(4)=Cube0(0100)2=(0100)2=(0101)2=5 …… Cube3(7)=Cube3(0111)2=(0111)2=(1111)2 =15。

当N=8时 1 2 3 4 5 6 7 Cube0开关状态图 Cube1开关状态图 Cube2开关状态图 Cube0循环函数： f=(0,1)(2,3)(4,5)(6,7) Cube0枚举： f(0)=1,f(1)=0,f(2)=3,f(3)=2,f(4)=5,f(5)=4,f(6)=7,f(7)=6 Cube0列表： 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6

红色链路：Cube0 绿色链路： Cube1 黄色链路： Cube2 8个处理单元的二元三维立方体结构图

单级混洗-交换网 该网络由混洗函数（shuffle）与交换函数（exchange即Cube0）定义，或者说它的互连函数族只有这两个成员。 混洗函数定义： 2j mod（N-1），当j < N-1 shuffle（j）= N-1 ，当j = N-1 例如：当N=8时，shuffle（0）= 0，shuffle（1）= 2，shuffle（7）= 7。 n=3的混洗函数开关状态如P397图7.6(a)所示，其连接规律就像洗牌。 1 2 3 4 5 6 7

性质1：shuffle（Xn-1Xn-2……X0）= Xn-2……X0Xn-1（循环左移）为什么？ 子混洗互连函数如下： Shuffle(k)（Xn-1Xn-2…Xk+1XkXk-1… X1X0）= Xn-1Xn-2…Xk+1Xk-1…X0X1Xk 超混洗互连函数如下： Shuffle(k)（Xn-1Xn-2…Xn-kXn-k-1Xn-k-2… X1X0）=Xn-2…Xn-kXn-k-1Xn-1Xn-k-2… X1X0 当N=8时 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 shuffle开关状态图 Shuffle(2)开关状态图 Shuffle(2)开关状态图

单级混洗—交换网络 n=3的混洗网络拓扑形状如下图绿线所示，可以看出它不是一个连通图，所以还需要增加一个交换函数（Cube0，图中红线所示），才能构成完整的单级混洗—交换网络。 8个处理单元的混洗交换互连网络连接图

碟型互连网络 碟型互连网络的互连函数为： Butterfly(Xn-1Xn-2……X1X0)=X0Xn-2……X1Xn-1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8个处理单元碟型互连网络连接图 同样，还有子碟型互连网络B(k)和超碟型互连网络B(k)，定义见P397所示。

单级加减2i网（PM2I网，移数网) 该网络由PM2I函数定义，PM2I函数共有n对成员，分别是PM2 ±0，PM2 ±1，……，PM2 ±(n-1)。 PM2I函数定义：PM2±i的功能是对入端结点编号加或减2i，然后再作模N运算 PM2+i（j）= j + 2i mod N PM2-i（j）= j - 2i mod N 其中j = 0 ～ N - 1，i = 0 ～ n - 1。 例如：当N = 8时， PM2+0（0）= 0 + 20 = 1， PM2+0（1）= 1 + 20 = 2， PM2+0（7）= 7 + 20 = 0， PM2+1（0）= 0 + 21 = 2。 N = 8的PM2+1（j）函数开关状态如右图 所示，其连接规律是把各入端结点编号加上 相同的增量21（mod N），获得出端结点编号。

N = 8的PM2+i网络拓扑形状如下图所示，可以看出它包含多个强连通子图（即除去若干边以后仍能保证任何一对结点互相可达），所以这2n个函数并不是实现互连网的最小集合。实际应用中为了降低造价，人们往往取它们的一个子集来构造互连网。 性质1：对相同的i值，PM2+i 与PM2-i函数的传送路径相同， 方向相反（右图中所有箭头 反向即为PM2-1的拓扑形状）； 性质2：PM2+(n-1) = PM2-(n-1)。 根据性质2，我们知道 单级PM2I网络实际上只能 实现2n-1种不同的置换。

1 2 3 4 5 6 7 PM2+0互连循环函数(0 1 2 3 4 5 6 7)及连接图 1 2 3 4 5 6 7 PM2+1互连循环函数(0 2 4 6)(1 3 5 7)及连接图 1 2 3 4 5 6 7 PM2+2互连循环函数(0 4)(1 5)(2 6)(3 7)及连接图

题：编号为0、1、…、15的16个处理器用单级互连网络互连。当互连函数分别为： Cube3 PM2+3 PM2-0 Shuffle Shuffle(Shuffle) 时，第13号处理器各连至哪一个处理器？ [分析] 编号为0、1、…、15的16个处理器，其号可用4位二进制码P3P2P1P0表示。第13号处理器二进制编号为1101 Cube3实现将处理器号为P3P2P1P0与处理器号为P3P2P1P0的数据进行交换。 PM2+3实现将j号处理器数据送至第（j+23 mod 16）处理器上。 PM2-0实现将j号处理器数据送至第（j-20 mod 16）处理器上。 Shuffle实现将处理器号为P3P2P1P0的信息送至处理器号为P2P1P0P3的处理器上。 Shuffle（Shuffle）实现将处理器号为P3P2P1P0的信息送至处理器号为P1P0P3P2的处理器上。

[解答] 1）第1101处理器连至0101处理器号上，即第5号处理器上。 2）第13号处理器数据送至第（13+23 mod 16）处理器上，即第5号处理器上。 3）第13号处理器数据送至第（13-20 mod 16）处理器上，即第12号处理器上。 4）第1101处理器连至1011处理器号上，即第11号处理器上。 5）第1101处理器连至0111处理器号上，即第7号处理器上。

互连网络的特性和传输的性能参数 互连网络特性 网络用有向边或无向边连接有限个结点的图表示。 网络规模：网络中结点数，表示该网络所能连接的部件多少。 结点度：与结点相连接的边数称为结点度，包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度。结点度d=入度+出度。 距离：两个结点之间相连的最少边数。 网络直径：网络中任意两个结点间距离的最大值，用结点间的连接边数表示。 结点间的线长：两个结点间连线的长度，用米、公里等表示。 对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。

互连网络的性能参数 一台机器发送消息给另一台机器时，发送方的步骤如下： (1) 用户程序把要发送的数据拷贝到操作系统的缓冲区。 (2) 操作系统把缓冲区中的数据打包，并发送的网络接口部件。 (3) 网络接口硬件开始发送消息。 数据包的接收步骤如下： (1) 把数据包从网络接口部件拷贝到操作系统缓冲区。 (2) 检查收到的数据包，如果正确，给接收方发回答信号。 (3) 把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区 机器A 机器B 连接两台机器的简单网络

互连网络在传输方面的主要性能参数 (1) 频带宽度(Bandwidth)：互连网络传输信息的最大速率。 (2) 传输时间(Transmission time)：等于消息长度除以频宽。 (3) 飞行时间(Time of flight)：第一位信息到达接收方所花费的时间。 (4) 传输时延(Transport latency)：等于飞行时间与传输时间之和。 (5) 发送方开销(Sender overhead)：处理器把消息放到互连网络的时间。 (6) 接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间。 一个消息的总时延可以用下面公式表示： 总时延＝发送方开销＋“飞行”时间＋消息长度/频宽＋接收方开销 发送方 开销 发送方 传输时间 接收方 开销 接收方 “飞行”时间 传输时间 传输时延 总时延

例：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？ [分析]：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％。 [解]：相距100米时总时延为： 相距1000公里时的总时延为：

静态互连网络 什么是静态互连网络？在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。 一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。 1、线性阵列 1维网络，其中N个结点用N-1条链路连成1行，内部结点度为2，端结点度为1，直径为N-1，等分宽度为1，结构不对称。 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12

2、环形网 采用移数函数。使用不同的移数函数，可以构成多种环形网。 单向环行网： 右环网，采用PM2+0函数。 左环网，采用PM2-0函数。 双向环行网：又称为一维邻居网，采用{PM2+0，PM2-0}函数。 环行网是对称的，结点度是常数2。双向环网的直径为N/2，单向环形网的直径是N-1。 1 2 3 4 5 7 6 环形网

如果将结点度由2提高至3，可得到弦环网。增加的弦愈多，则结点度愈高，网络直径愈小。 循环移数网络也是一种环形网，它将环上每个结点与其距离为2的整数幂的结点之间连接构成。循环移数网的结点度为2n-1，直径为 [n/2] 。 1 2 3 4 5 7 6 循环移数网 1 2 3 4 5 7 6 度为3的弦环网

2、树形和星形网 一棵k层二叉树有N＝2k－1个结点，结点度是3，直径是2(k-1)。 星形是一种特殊的2层树，结点度很高，为d=N-1，直径是2。 二叉胖树的结点度从叶子结点往根结点逐渐增加。胖树缓解了一般二叉树根结点通信速度高的矛盾。 星形网 二叉胖树网 二叉树网

网格形网 是一种比较流行的网络结构，有各种变体形式。在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现。 一般网格网，N＝nk 结点的k维网格的结点度为2k，直径为k(n-1)。 环网形网格网沿阵列每行每列都有环形连接。一个n×n二元环网的结点度为4，直径为2[n/2]。环网是一种对称的拓扑结构。 Illiac IV的8×8 Illiac网格，其结点度为4，直径为7。一个n×n Illiac 网格的直径为d=n-1，为纯网格直径的一半。 纯网格型 Illiac网 环形网

超立方体网 n维立方体由N＝2n个结点, 分布在n维上, 每维有两个结点。 超立方体网采用交换函数，结点度为n，直径也为n Y X Z 011 000 010 110 111 101 100

题：画出16台处理器仿ILLIAC Ⅳ的连接模式进行互连的互连结构图，列出PE0分别只经过一步、二步和三步传送能将信息传送到的各处理器号。 [分析]：ILLIAC Ⅳ处理器数N为64个，构成8×8方阵，各PE之间的连接规律可以有PM2+0(mod N)和PM2+n/2(mod N)。其中PM2+n/2 因为n=log2N=log264=6，所以实际是PM2+3。 按照ILLIAC Ⅳ的连接模式，不难看出，当N为16个处理单元时，构成的是8×8方阵，各PE之间的连接规律就是PM2+0(mod 16)和PM2+2(mod 16)，根据所画出的互连结构图，PE0只经一步、二步和三步传送将信息传送到的各处理器号就可很容易求得了。 [解]：16台处理器仿ILLIAC Ⅳ的连接模式互连的结构图如下所示。 1 2 3 4 12 8 15 13 14 5 7 6 9 10 11

PE0经一步可将信息传送到的处理器号有PE1、PE4、PE12、PE15。 PE0经二步可将信息传送到的处理器号除了一步可送到的有PE1、PE4、PE12、PE15外，还有PE2、PE3、PE5、PE8、PE11、PE13、PE14。 PE0经三步可将信息传送到的处理器号除了上述处理器号外，还有PE6、PE7、PE9、PE10。 由此可见，最多经3步可以将PE0的信息传送到任何其它的处理器上，所以其最大的距离为3步。

动态互连网络 动态互连网络可以通过设置有源开关，从而根据需要借助控制信号对连接通路加以重新组合，实现所要求的通讯方式。 动态互连网络的互连形式 总线互连 交叉开关 多级互连网络 1.总线互连 指用一组导线和插座将处理机、存储模块和各种外围设备互连起来，总线上各模块需要通讯时，发出申请，由总线仲裁逻辑对多个请求进行仲裁，进行总线服务分配。 P1 P2 Pn C1 C2 Cn M1 M2 Mn I/O子系统 辅助存储器 处理机 高速缓存 总线 主存储器

2 交叉开关 交叉开关包含一组纵横开关阵列，把横向的m个处理机及i个I/O设备与纵向的n个存储器模块连接起来，如下图所示。 P1 P2 Pn 处理机 M1 M2 Mn 主存储器 I/O1 I/O2 I/Oi

(3) 多级ICN（P409） 交换开关 能够实现结点到结点之间的任意互连是互连网络的一种基本功能。 多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。 多级互连网络采用的关键技术： (1) 交换开关 (2) 交换开关之间的拓扑连接 (3) 对交换开关的不同控制方式 交换开关 一个a×b交换开关有a个输入和b个输出。 最常用的二元开关：a=b=2。 每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。 具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。 具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。

2、拓扑结构 前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。 通常采用前面介绍的互连函数实现拓扑结构 实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。 3、控制方式 在多级互连网络中有多级交换开关，每一级又有多个交换开关。通常有三种控制方式 (1) 级控制：同一级交换开关使用同一个控制信号控制，动作保持一致。 (2) 单元级控制：每个交换开关分别控制，各开关动作独立，性能灵活，结构复杂。 (3) 部分级控制：例如，第i级使用i+1个控制信号控制，每个信号管辖若干开关

多级混洗—交换Ω网络（P410/P436） C3 C2 C1 C0 K2 K1 K0 多级混洗—交换网络又称为Omega网，它由n=log2N级单级洗牌置换网构成，N为Ω网络输入数或输出数，每一级包含一个无条件混洗拓扑线路和一列N/2个可控的二元交换开关，前后重复，故Ω网络开关数为(N/2)log2N。 C3 C2 C1 C0 K2 K1 K0

Ω网络结构特点： 采用2×2的4功能开关，4功能为直送、交叉、上播、下播。 Ω网络各级开关的级号从网络输入端到输出端，依次为Kn-1，……，K1，K0，即按降序排列。 级间连接从网络输入端到输出端依次为Cn-1，……，C1，C0，其中Cn-1~C1都是均匀洗牌置换函数，C0为恒等置换。因此Ω网络输入端对输出端互连函数表达式为： Ω=σEσE…σE=(σE)n 其中E是开关级在开关控制方式下实现的交换置换函数，σ是级间连接模式实现的混洗函数。 说明： 在多级混洗—交换网络中，单独一级混洗拓扑线路可完成一次数据混洗（shuffle），而单独一列二元交换开关在处于“交换”状态时可完成一次交换操作（Cube0）。如果各级二元交换开关都处于“直连”状态，N个结点的数据通过网络仅经过n次混洗操作，排列顺序最终恢复输入状态（混洗函数性质2）；如果各级二元交换开关都处于“交换”状态，则N个结点的数据在每次混洗之后紧接着一次交换（Cube0），也就是地址码的最低位取反，最后n位地址均被取反。程序员根据数据置换或复制的需要，可以灵活地设置各开关的状态。

多级混洗—交换网络寻径算法（路由算法） 目的：根据给定的输入/输出对应关系，确定各开关的状态。 名称：源-目的地址异或法 操作：将任一个输入地址与它要到达的输出地址作异或运算，其结果的biti位控制数据到达的第i级开关，“0”表示“直连”，“1”表示“交换”。 例如给定传输101B→011B，二者异或结果为110B，于是从101B号输入端开始，把它遇到的第2级开关置为“交换”，第1级开关置为“交换”，第0级开关置为“直连”。如下图红线所示。

题：画出0~7号共8个处理器的三级混洗交换网络，在该图上标出实现将6号处理器数据播送给0~4号，同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。 [解]：可以运用多级混洗—交换网络寻径算法（路由算法）对每一对输入-输出分别求出其路径。

STARAN网络 A B C D E F G H I J K L 1 2 3 4 5 6 7 C0 输入端 输出端 C1 C2 C3 K0 1 2 3 4 5 6 7 C0 输入端 输出端 C1 C2 C3 K0 K1 K2 N=8的STARAN网络

E(Xn-1Xn-2…X1X0)=(Xn-1⊕fn-1, Xn-2⊕fn-2,…, X1⊕f1, X0⊕f0) STARAN网络： 有n=log2N级，每级N/2个开关，整个网络开关数(N/2)log2N 采用2×2的2功能开关，2功能为直送和交叉。 开关级的级号从网络输入端到输出端，依次为K0,,K1, ……,Kn-1。 级间连接从网络输入端到输出端依次为C0,C1, ……,Cn-1，其中C0为恒等置换, C1~Cn都是逆洗牌置换。 开关控制方式有2种：级控方式和组控方式。其中级控方式可实现交换置换，故级控方式的STARAN网络又被称为交换网络，组控方式可实现移数置换，故组控方式的STARAN网络又被称为移数网络。 级控方式及交换置换 对于一个2功能开关，开关输出E(x)与输入x及控制位f关系如下： E(x)=x⊕f 若f=0，则E(x)=x，开关为直送连接；若f=1，则E(x)=x，开关为交叉连接。 对于级控方式，可以用二进制向量F=(fn-1fn-2…f1f0)表示网络的控制信号，F的位分量fi就是开关级Ki所有开关的控制位信号，这样，STARAN网络实现的置换为： E(Xn-1Xn-2…X1X0)=(Xn-1⊕fn-1, Xn-2⊕fn-2,…, X1⊕f1, X0⊕f0) n位二进制向量F可取N=2n个不同的值，从而使STARAN网络实现N种置换。

3级STARAN交换网络实现的入出端连接及执行的交换函数功能 级控制信号（f2f1f0） 000 001 010 011 100 101 110 111 入端号 1 2 3 4 5 6 7 执行的交换函数功能 恒等 4组 2元 4组2元 + 2组4元 2组 4元 1组8元 i Cube0 Cube1 Cube2 +Cube1 +Cube0

入端排列： 分成4组： 每组二元交换： 分成二组： 每组四元交换： 分成一组： 每组八元交换： 0 1 2 3 4 5 6 7 除F=(000)实现恒等置换外，其他7种实现分组交换置换，如F=(101)实现的置换可表示为： 入端排列： 分成4组： 每组二元交换： 分成二组： 每组四元交换： 分成一组： 每组八元交换： 0 1 2 3 4 5 6 7 │0 1 │2 3 │ 4 5 │ 6 7 │ │1 0 │3 2 │ 5 4 │ 7 6 │ │1 0 3 2 │ 5 4 7 6 │ │2 3 0 1 │ 6 7 4 5 │ │2 3 0 1 6 7 4 5 │ 5 4 7 6 1 0 3 2

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 F=(000) F=(001) F=(010) F=(011) 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 F=(100) F=(101) F=(110) F=(111)

E(X2X1X0)=Cube1(Cube0(X2X1X0))=X2X1X0 可以发现：F=(f2f1f0)=001的交换置换就是Cube0置换，F=(f2f1f0)=010的交换置换就是Cube1置换，F=(f2f1f0)=100的交换置换就是Cube2置换，也就是说，fi实现Cubei置换。例如，当F=(f2f1f0)=011，3级STARAN网络实现的交换置换为： E(X2X1X0)=Cube1(Cube0(X2X1X0))=X2X1X0 记为Cube0+Cube1。实际上，同样有： E(X2X1X0)=(X2⊕f2,X1⊕f1,X0⊕f0) = (X2⊕0,X1⊕1,X0⊕1) =X2X1X0

组控方式及移数置换 组控方式是指：将第i级的N/2个2×2的2功能开关分成i+1组，每组用一个位信号控制该组开关的状态。对于级数是n=log2N的N×N网络，从第0级至第n-1级各开关级所需的位信号数分别为1,2,…,n个，因此，共需n(n+1)/2个位信号组成二进制控制向量F。对于N=8的网络，需要6个位信号组成的控制向量F，表示F=(f23f22f21f12f11 f0)。 移数置换的互连函数为 a(x)=(x+2m) mod 2p 其中，p和m都是整数，且0<=m<p<=n。 一个N×N=2n×2n的移数网络能实现(n2+n+2)/2种移数置换。N=8的STARAN移数网络能实现7种移数置换。 N=8的STARAN移数网络分别在7种组控制信号下，实现的网络输入到输出连接如下页表格所示。其中K0级只有1位控制信号f0控制K0级开关A、B、C、D； K1级2位控制信号f11f12，f11控制开关E、G，f12控制开关F、H；K2级有3位控制信号f21f22f23，f21控制开关I， f22控制开关J，f23控制开关J、K。

3级STARAN移数网络实现的入出端连接及执行的移数函数功能 组控制信号 2级 F23 F22 F21 K,L J I 1 1级 F12 F11 F,H E,G 0级 F0 A,B,C,D 入 端 号 2 3 4 5 6 7 执行的移数 功能 移1 mod 8 移2 移4 mod 4 mod 2 不移 恒等

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 恒等 移1模2 移1模4 移2模4 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 移1模8 移2模8 移4模8

题：编号分别为0,1,2,…,F的16个处理器之间要求按下列配对通讯： (B,1), (8,2), (7,D), (6,C), (E,4), (A,0), (9,3), (5,F)。试选择互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级交换开关状态图。 [分析]：要求配对通讯的处理器号用二进制表示如下： (B,1)是(1011,0001) (8,2)是(1000,0010) (7,D)是(0111,1101) (6,C)是(0110,1100) (E,4)是(1110,0100) (A,0)是(1010,0000) (9,3)是(1001,0011) (5,F)是(0101,1111) 可以发现，处理器P3P2P1P0与处理器P3P2P1P0配对交换数据，由于都是交换函数功能，因此，采用低成本的级控多级立方体互连网络即可。 对于16个端的多级立方体互连网络来说，N=16，有n=log2N =log216 =4级，每级使用N/2=16/2=8个二功能交换开关，其中第1级和第3级处于交换状态，第0级和第2级处于直通状态。

入端 出端 1 1 2 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 A B A B C D C D E F E F Cube0 Cube1 Cube2 Cube3 直连 交换 直连 交换

(0,B), (1,A), (2,9), (3,8), (4,F), (5,E), (6,D), (7,C) 题：并行处理机有16个处理器，要实现相当于先4组4元交换，然后是两组8元交换，再次是一组16元交换的交换函数功能，请写出此时各处理器之间所实现之互连憾事的一般式；画出相应多级网络拓扑结构图，标出各级交换开关的状态。 解：输入端号为 |0 1 2 3|4 5 6 7|8 9 A B|C D E F| 经4组4元交换后为 |3 2 1 0|7 6 5 4|B A 9 8|F E D C| 分成2组后为 |3 2 1 0 7 6 5 4|B A 9 8 F E D C| 然后经2组8元交换后为 |4 5 6 7 0 1 2 3|C D E F 8 9 A B| 再经1组16元变换后为 |B A 9 8 F E D C 3 2 1 0 7 6 5 4| 最后，可得出配对互连的是 (0,B), (1,A), (2,9), (3,8), (4,F), (5,E), (6,D), (7,C) 用二进制表示就是 Cube(P3P2P1P0)= P3P2P1P0

间接二进制n方体网络 01 23 45 67 入端 出端 K0 K1 K2 C0 C1 C2 C3 间接二进制n方体网络(n=3) 级数是n=log2N，每级有N/2个开关，网络开关数(N/2)log2N。 采用2×2的2功能开关，2个功能为直送和交叉。 开关级级号从输入到输出端，一次为K0,K1, …, Kn-1。级间连接依次为C0,C1, …, Cn。其中，C0是恒等置换，C1~Cn-1都是子碟式置换，Cn是逆洗牌置换。

寻径算法：源-目的地址异或法 阻塞网络 采用单元控制方式。网络有m= (N/2)log2N个开关，每个开关有两种状态，因此网络有2m个不同状态，即网络能实现2m种置换连接。 可以实现多种函数变换：移数变换、子移数变换、P序置换、逆P序置换等 01 23 45 67 入端 出端 K0 K1 K2 C0 C1 C2 C3 间接二进制n方体网络(n=3) 阻塞

基准网络 01 23 45 67 入端 出端 0级 1级 2级 C0 C1 C2 C3 N=8的基准网络 特点：1）采用直送和交叉的2×2的功能开关，开关级数n=log2N，每级有N/2个开关，网络开关数(N/2)log2N。 2）开关级编号从输入到输出依次为K0,K1, …, Kn-1 。 3）级间连接模式编号从输入到输出依次为C0,C1, …, Cn 。其中，C0,Cn恒等置换， C1逆均匀洗牌置换，C2~Cn-1都是子逆均匀洗牌置换。 4）单元控制，寻径算法：终端标记法

多级PM2I网络 1 2 3 4 5 6 7 入端 出端 PM2+2 PM2-2 PM2+1 PM2-1 PM2+0 PM2-0 2级 1级 1 2 3 4 5 6 7 入端 出端 PM2+2 PM2-2 PM2+1 PM2-1 PM2+0 PM2-0 2级 1级 0级 N=8的多级PM2I网络

就i级而言（0<=i<=n-1,0<=i<=2），每个输入端j（ 0<=j<=2 ）都是三根线分别输出端（j-2i）mod N，j和（j+2i）mod N，图中分别用蓝线、黑线和红线表示。 第0级完成的是PM2+0,第1级完成的是PM2+1,第2级完成的是PM2+2。 从一个单元到另一个单元的路由有多条路径可供选择，如从6号处理单元到4号处理单元，可以经过6-6-4-4，也可6-2-4-4，显然，在多级网络中提供了冗余通路，有利于提高系统的可靠性。 当各级处理单元均采用单元控制时，这种多级PM+I网络成为了强化数据交换网络(augmented data manipulator，简称ADM网络) U H D 上播 直连 下播 多级PM2I网络中各级各单元的单元控制原理图

五种多级互连网络比较 交换开关 控制方式 拓扑结构 二进制立方体网络 STARAN交换网络 二功能交换单元 级控制 单级立方体网络 STARAN移数网络 部分级控制 间接二进制n方体网络 单元控制 Omega网络 四功能交换单元 单级混洗交换网络 强化数据变换网络 （ADM网络） 多功能交换单元 单级PM2I网络

题：对于采用级控制的三级立方体网络，当第i级(0<=i<=2)为直连状态时，不能实现哪些结点之间的通信？为什么？反之，当第i级为交换状态呢？ [分析]：三级立方体网络的入出结点的二进制编号为P2P1P0 。 当第i级(0<=i<=2)为直连状态时，反映出能够实现互连的入、出端号的二进制中的Pi位不能变反，其他的Pj(Ii>j)可以不变，也可以变反。 当第i级(0<=i<=2)为交换状态时，反映出能够实现互连的入、出端号的二进制中的Pi位必须变反，其他的Pj(Ii>j)可以变反，也可以不变。 [解]： 当第i级(0<=i<=2)为直连状态时，不能实现入、出端号处理器的二进制码的编号中第Pi位取反的处理器之间的连接，因为Pi位控制第i级开关只能直连。反之，当第i级(0<=i<=2)为交换状态时，不能实现入、出端处理器号的二进制中的Pi位相同的处理器之间连接。 例如，当第0级为直连时，只能实现000、010、100、110号处理器之间进行数据传送，不能与001、011、101、111号处理器中任一处理器之间数据传送。

C=r(m×n)+m(r×r)+r(m×n)=mr(2n+r) 多级CLOS网络（非阻塞网络） n×m r×r m×n 1 1 1 n n 2 2 2 n n r r r n n 输入级 中间级 输出级 三级CLOS交叉开关网络 特点： 输入级r个开关，中间级m个开关， 输出级r个开关。 三级网络可用三个参数表示N(m,n,r)，可以证明，当m>=2n-1时，多级CLOS网络N(m,n,r)是一个非阻塞网络。 多级CLOS网络N(m,n,r)所需总的交叉点个数 C=r(m×n)+m(r×r)+r(m×n)=mr(2n+r)

N(3,2,2)CLOS交叉开关网络连接图如下： 2×3 2×2 3×2 输入级 中间级 输出级 N（3，2，2）CLOS交叉开关网络

多级BENES可重排网络（非阻塞网络） 入端 出端 01 01 23 23 45 45 67 67 N=8的BENES多级可重排网络 特点： 开关级数2log2N-1，每一级有N/2个2×2的功能开关。 BENES网络置换表达式：Eσ-1(n-1)Eσ-1(n-2) … Eσ-1(-1)Eσ(1) …Eσ(n) E 当N=8时，有2×log2N-1=5级，每级8/2=4个开关，单元控制，可实现置换数25×4=220=1M，开关组合8!=40320，所以多级BENES网络无阻塞网络

碟式网络 由16个8×8交叉开关构成的两级64×64碟式网络，级间采用8路洗牌连接。 8×8 第0级 第1级 1 7 8 9 15 56 1 7 8 9 15 56 57 63 第0级 第1级

题：具有N=2n个输入端的Ω网络，采用单元控制， 该Ω网络通过一次可以实现的置换有多少种是不同的？ 若N=8，计算出一次通过能实现的置换数占全部排列数的百分比。 [分析]：根据题意， N=2n个输入端的Ω网络，采用单元控制，实现N个输入端的全部排列数显然应当是入、出端间1到1的全部映射数。尽管在Ω网络中每个交换开关可以有直连、交换、上播和下播等4种功能，但作为1到1映射来说，实际上只需直连、交换两种功能。在每级N/2个交换开关的n级Ω网络中，共有交换单元数(N/2)log2N，每种交换单元有两种状态，所以全部开关的状态组合数只有NN/2(2的(N/2)log2N次方)，每个状态组合可实现其中一种排列的互连，所以组合数就是互连网络一次通过可以实现的入出端连接的全部置换数。 解： （1）N个输入共有N！种不同的排列。 （2）Ω网络通过一次可以实现的置换数只能是NN/2种不同。 （3）N=8时，一次通过能实现的置换数84=4096种，而全部排列数8!=40320种，所占百分比为： 4096/40320=10.16%

题：假设8×8矩阵A=[aij]的64个元素按矩阵行序存放在存储器的64个单元中，用什么样的单级互连网络可实现对该矩阵的转置变换，即在64个存储单元中按矩阵列序存放这64个元素？通过单级互连网络总共需要传送多少次？ [分析]：A=[aij], AT=[aji] a0,0 a0,1 a0,2 … a0,7 a1,0 a1,1 a1,2 … a1,7 …… a7,0 a7,1 a7,2 … a7,7 a0,0 a1,0 a2,0 … a7,0 a0,1 a1,1 a2,1 … a7,1 …… a0,7 a1,7 a2,7 … a7,7 a0,0 a0,1 … a0,7 a1,0 a7,7 a0,0 a1,0 … a7,0 a0,1 a7,7

shuffle(shuffle(shuffle(j2j1j0i2i1i0)))=i2i1i0j2j1j0 a0,0 a000,000 a0,1 a000,001 a0,2 a000,010 … ai,j aj2j1j0,i2i1i0 a7,7 a111,111 a0,0 a000,000 a1,0 a001,000 a2,0 a010,000 … aj,i ai2i1i0,j2j1j0 a7,7 a111,111 即：按行序方式下的元素aj2j1j0i2i1i0与列序方式下元素ai2i1i0j2j1j0置换。如何实现这种置换，答案是单级均匀洗牌置换网络，即： shuffle(shuffle(shuffle(j2j1j0i2i1i0)))=i2i1i0j2j1j0

[分析]:已知PM2I和Cubei的互连函数分别为: 题:假定有128个处理器,采用PM2I多级网络互连,若网络中的i=2的1级损坏,拟用Cubei多级网络代替损坏的这一级,试说明最多需要几级Cubei网络? [分析]:已知PM2I和Cubei的互连函数分别为: PM2+i(X)=X+2i mod N 其中,0<=X<=N-1,n=log2N,0<=i<=n-1 Cubei(xn-1 … xi … x1x0)=xn-1 … xi … x1x0 由题意,有N=128,n=log2N=7, PM2I多级网络i=2级实现的互连为: PM2+2(X)=X+22=X+4 mod 128 0<=X<=127 用二进制表示该级网络的输入端和输出端的编号,实现的互连为: PM2+2(x6x5x4x3x2x1x0)= x6x5x4x3x2x1x0+100 mod 128 若PM2I多级网络中,PM2+2级损坏,用Cubei多级网络代替,即要求Cubei多级网络能实现PM2+2指定的互连. 对于Cubei多级网络的128个输入端中所有x2=0的输入端,有: = x6x5x4x3x2x1x0 =Cube2(x6x5x4x3x2x1x0) 则只需1级Cubei网络并实现Cube2就可以代替PM2+2指定的连接.

PM2+2(x6x5x4x3x2x1x0)= x6x5x4x3x2x1x0+100 mod 128 对于Cubei多级网络的128个输入端中所有x2=1、 x3=0的输入端,有: PM2+2(x6x5x4x3x2x1x0)= x6x5x4x3x2x1x0+100 mod 128 = x6x5x4x3x2x1x0 = Cube3(Cube2(x6x5x4x3x2x1x0)) 则只需2级Cubei网络并实现Cube3(Cube2)就可以代替PM2+2指定的连接. 对于Cubei多级网络的128个输入端中所有x2=1、 x3=1 、 x4=0的输入端,有: = Cube4(Cube3(Cube2(x6x5x4x3x2x1x0))) 则只需3级Cubei网络并实现Cube4(Cube3(Cube2))就可以代替PM2+2指定的连接. 对于Cubei多级网络的128个输入端中所有x2=x3=x4=1、x5=0的输入端,有: =Cube5(Cube4(Cube3(Cube2(x6x5x4x3x2x1x0)))) 则只需4级Cubei网络并实现Cube5(Cube4(Cube3(Cube2)))就可以代替PM2+2指定的连接.

PM2+2(x6x5x4x3x2x1x0)= x6x5x4x3x2x1x0+100 mod 128 对于Cubei多级网络的128个输入端中所有x2=x3=x4=x5=1、x6=0的输入端,有: PM2+2(x6x5x4x3x2x1x0)= x6x5x4x3x2x1x0+100 mod 128 = x6x5x4x3x2x1x0 =Cube6(Cube5(Cube4(Cube3(Cube2(x6x5x4x3x2x1x0))))) 则需5级Cubei网络并实现Cube6(Cube5(Cube4(Cube3(Cube2))))就可以代替PM2+2指定的连接. 因此，最多需要5级Cubei网络代替PM2+2指定的连接.

题：给出N=8的碟式变换如右图所示。 写出互连函数关系式 如采用Omega网络，需几次通过才能完成此变换？ 画出Omega网络实现输入端到输出端连接要求的各次连接的开关状态图。 1 2 3 4 5 6 7 [分析]:N=8的Omega网络就是三级混洗交换网络，有关用Omega网络实现此交换需通过几次 的问题，可以分两种情形讨论。一种情形就是处理单元设置有屏蔽位控制硬件，此时，可将0、2、5、7号处理单元处于屏蔽状态，只将1、3、4、6按(1,4),(3,6)进行交换传送即可。另一种情况是，处理单元不设置屏蔽位控制硬件，此时，0~7号处理单元同时传送，因此，应使1、3、4、6按要求交换传送的同时，应使0、2、5、7号处理单元的数据经中转传送后，仍送回其自身。

解： (1)设互连网络入端的二进制编号为P2P1P0 ，则互连函数为： f(P2P1P0)=P0P1P2 (2)如果处理单元设置有屏蔽位控制硬件，可让0、2、5、7处理器输出处于屏蔽状态，而让1、3、4、6处理器输出处于活跃状态，这样，只需在Omega网络上通过一次即可实现(1,4),(3,6)的同时交换，此时，传送的路径没有冗余。 如果处理单元未设置屏蔽位控制硬件，就需要在Omega网络上通过两次，此时，传送路径会有很多冗余。 (3)通过一次的控制状态图如下：

通过二次Omega网络可选的方案很多， 例如，可以： 0——5 1——1 2——0 3——4 4——2 5——6 6——7 7——3 第一次 原则是：不能发生阻塞或冲突 5——0 1——4 0——2 4——6 2——1 6——5 7——3 3——7 第二次

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

消息格式与消息寻径方式 消息格式： Message Packet Packet 数据片 … 数据片 数据片 序号片 寻径片 包：能独立寻径 片：不能独立寻径 消息寻径方式： 线路交换 包交换 存储转发 虚拟直通寻径 虫蚀寻径