第六章 互连网络 6.1 互连网络的基本概念 6.2 静态互连网络 6.3 动态互连网络

6.1 互连网络的基本概念 一. 互连网络的功能 1．什么是互连网络? 从广义上讲，凡是用以实现部件、设备或系统之间连接用的部件都可以称为互连网络。 狭义上讲，互连网络是一种由开关元件按一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多处理机或多功能部件之间的相互连接。 它通过硬件线路，实现设备之间的连接；通过开关选择，构成一对一或一对多的信息通路。

6.1 互连网络的基本概念 互连网络 富士通VPP500并行向量处理机: 224×224交叉开关 送部件 主存储 器部件 向量标 标量部件 系统存储器部件 控制 处理机 数据传 送部件 主存储器 标量部件 主存储 器部件 量部件 向量标 处理部件 1 2 222 224×224交叉开关 VP2000 二级 存储器

更为一般的系统： 存储器 处理机—存储器网络 m 1 2 共享存储器 处理机间网络 处理机 处理机—外设网络 磁带设备 磁盘设备 打印设备 网 络 共享外设 系统以多处理机为核心，各处理机有自己专用的存储器，称为本地存储器，处理机内包含有独用的Cache。此外还有各处理机公用的存储器，称为共享存储器，各处理机对共享存储器的访问通过处理机—存储器网络进行交换。

6.1 互连网络的基本概念 2．互连网络的主要功能 1）连接各个结点，构成信息通路，传送数据或控制命令。 2）通过路径选择，实现有目的的信息交换，其中包括一到一和一到多的选择与交换。

6.1 互连网络的基本概念 二. 互连网络的主要特性 1）网络规模：即一个网络中所连接的结点数。 2）结点度：每个结点与外部连接的边数称为一个结点的度，用d表示。 结点A 结点B 线路 ( b ) 双向 ( a ) 单向

6.1 互连网络的基本概念 3）距离：任意两结点之间相连的最少边数。 4）网络直径（D）：网络中任意结点之间距离中的最大值。 B A C D AB的距离:1 AC的距离:1 AD的距离:1 BC的距离:2 BD的距离:1 CD的距离:1 网络直径: D=2 5）结点间线长：两个结点之间实际连接用的线长。

6.1 互连网络的基本概念 6）等分宽度： 通道等分宽度：一个网络被切割成对等的两半时，沿切口所具有的边数（通道数），称为通道等分宽度，用k表示。 线等分宽度：若用w表示通道宽度（用位表示），则线等分宽度为：B= k×w。 7）对称性：如果从任一个结点观察网络，所看到的网络拓扑结构都是相同的，该网络是一个对称网络。 8）数据寻经功能：表示互连网络把数据从一端传送到另一端的方式和能力。寻径方式分为静态和动态两种。寻径功能有一到一、一到多、散射、汇合/聚集等。

6.1 互连网络的基本概念 三. 互连函数 1．互连网络的功能表示 无论何种互连网络，在系统中所起的作用都是一样的，即进行有关部件（或设备）间的有效连接，完成信息的传输。 如果将互连网络看作一个黑盒子，盒子的输出端口与输入端口间就存在一定的位置变换关系，这就是互连函数。

6.1 互连网络的基本概念 互连网络 f (i) 1 2 N 特别应该强调指出，这里所谓的变换关系并不是信号形式的变换，而只是端口位置的变换关系，所以用以表征黑盒子特性的不是传输函数，而是互连函数。

6.1 互连网络的基本概念 2.互连函数表示法 1）函数表示法： 在函数表示法中，通常用x表示输入端变量（即端口编号），f (x)就用以表示互连函数。其中x常用端口编号的二进制值表示，x = xn-1 xn-2 … x1 x0。而相应的互连函数就可以写成：f (xn-1 xn-2 … x1 x0 )。如果变换函数发生了变化，其表示也就可以相应的写成：σ( xn-1 xn-2 … x1 x0 )。 一个完整的函数就应在其等式的右边写出该函数的值，即变换的结果。例如： σ( xn-1 xn-2 … x1 x0 ) = xn-2 xn-3 … x1 x0 xn-1

6.1 互连网络的基本概念 2）输入输出对应表示法： 即列出对应端口间的对应关系表，输入输出对应关系列出在符号框内，其表示形式为： 在符号框内，上一个元素与下一个元素分别对应输入与输出的连接关系。

6.1 互连网络的基本概念 3）图形表示法 图形表示法是直接用连线将输入与输出的关系连接在一起，非常直观。其缺点是不容易从中看出规律性的东西，即函数关系不能一目了然。 000 001 010 011 100 101 110 111

6.1 互连网络的基本概念 3. 基本互连函数 1）恒等互连函数 如果相同输入/输出编号的端口对应互连，所实现的变换称为恒等变换。其表示式为： I(xn-1xn-2…x1x0)=xn-1xn-2…x1x0 000 001 010 011 100 101 110 111 等式左边和右边端口编号的二进制编码完全相等。图形表示的恒等变换如右图所示：

) ( 6.1 互连网络的基本概念 x E = 2）交换互连函数 将输入端口编号的二进制码中的第0位取反，得到的互连函数称为交换互连函数。其表示式为： 2 - ( ) 1 n x E = … 000 001 010 011 100 101 110 111

6.1 互连网络的基本概念 ( ) x C = 3）方体互连函数 将输入端口编号的二进制码内的某一位（第k位）作取反操作，所得的值就是与之相连的输出端口编码。其表示式为： ( ) 1 2 x C k n - + = … 如果输入端口有N个，每个端口编号的二进制编码就有n = log2 N位，k可以是其中的任意一位，所以方体变换也就可以有n种。按照被变换位的位置，分别可以表示成：C0，C1，…，Cn-1等。

( ) ( ) 6.1 互连网络的基本概念 ( ) x C = x C = x C = 比如，网络结点N = 8时，允许有三种方体互连函数，他们分别 是： ( ) 1 2 x C = ( ) 1 2 x C = ( ) 1 2 x C = ( c ) C2方体 ( a ) C0方体 000 001 010 011 100 101 110 111 ( b ) C1方体

6.1 互连网络的基本概念 4）均匀洗牌（全混洗）互连函数 均匀洗牌互连函数是将输入端分为数目相同的两个部分，分别与输出端进行均匀洗牌，即一个隔一个地与输出端相连。函数表示式为： ( ) 1 3 2 - = n x S … 均匀洗牌互连函数σ 000 001 010 011 100 101 110 111

6.1 互连网络的基本概念 逆均匀洗牌 000 001 010 011 100 101 110 111 循环移位也可以由左移改为右移，这时就成了逆均匀洗牌，这种方式可以看作是均匀洗牌的逆函数。函数表达式为： ( ) 1 2 x n - = S …

6.1 互连网络的基本概念 ( ) N X mod 2 PM2I + = - 5）PM2I互连函数 式中，0 ≤ X ≤ N - 1，0 ≤ i ≤ n – 1，n = log2N， N为网络结点数。 即：结点数为N的网络，其PM2I互连函数的个数为2n，（n = log2N）。

6.1 互连网络的基本概念 按互连函数画出的图形如下图所示。 ( b ) i = +1 ( c ) i =+2 ( a ) i = 0 1 1 2 3 4 5 6 7 ( a ) i = 0 ( b ) i = +1 ( c ) i =+2

6.1 互连网络的基本概念 ( ) = x B 6）蝶式互连函数 将输入端编号的二进制码的最高位和最低位对调，所得的二进制编码就是与之相连的输出端口编号，这种连接称为蝶式置换。其函数表示式为： ( ) 1 2 - = n x B … 000 001 010 011 100 101 110 111

6.1 互连网络的基本概念 ( ) R = x x 7）反位序互连函数 就是将输入端二进制编号的位序颠倒过来求得相应输出端的编号，其函数表示式为： ( ) 1 n-2 2 - = n x R … x 1

6.1 互连网络的基本概念 ( ) [ ] = x E S = x 8）混洗交换互连函数 就是由全混洗互连函数与交换互连函数构成的复合函数，其函数表示式为： ( ) 1 2 [ - = n x E S … ] 1 2 - = n x …

6.1 互连网络的基本概念 例：设有64个处理器，其编号依次是0，1，2，…，63。当按照互连函数Exchange()4连接时,第21号处理器应与哪个处理器连接? 解:设待求处理器的序号为i，表示为Pi，则 Pi = Exchange(010101)4 = 010101 = 000101 所以，第21号处理器应与第5号处理器连接。

6.2 静态互连网络 静态互连网络是指在点到点之间使用直接链路，一旦设计成功，固定不变。即使在工作过程中，也不能用程序改变。 系统中的每一个结点往往不止只连接一个相邻结点，即结点的度往往大于1。于是在信息传递时，就必须解决正确选择通信对象的问题。为此，每个结点中都必须设置“寻径器”，所以，这种网络又被称作基于寻径器的网络。

6.2 静态互连网络 一. 网络拓扑结构 线性阵列 网络直径：N-1 环和带弦环 单向连接时，网络直径： N-1 双向连接时，网络直径： 1 2 N-1 N-2 N-3 网络直径：N-1 环和带弦环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 （a）环形网 单向连接时，网络直径： 双向连接时，网络直径： N-1 [N/2] 网络直径越大，传输延时越大

6.2 静态互连网络 环和带弦环 网络直径为5 网络直径为3 ( c ) 4度带弦环形网络 （a）环形网 ( b ) 3度带弦环形网络 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ( b ) 3度带弦环形网络 ( c ) 4度带弦环形网络 （a）环形网 网络直径为5 网络直径为3

6.2 静态互连网络 循环移数网络 这也是通过在环形网络结构上增加“弦”的方法使直径减小的改进网络。只是，加弦的规律是：从任一结点出发与距该结点距离为2的整数幂结点相连 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 网络直径为2

6.2 静态互连网络 树形与胖树形 二叉树结构网络 二叉胖树结构网络

6.2 静态互连网络 网格形和环形网格 ( c ) 环形网格 ( a ) 网格形 ( b ) Illiac网

6.2 静态互连网络 超立方体和带环立方体 ( c ) 带环立方体 ( a ) 3维立方体 ( b ) 4维立方体

6.2 静态互连网络 二 . 静态网络特性表

6.3 动态互连网络 一. 总线互连方式 动态互连网络使用开关或者裁决器提供动态连接特性，在运行过程中由程序来确定具体的连接方式。 总线互连方式是多处理机实现互连的一种最简单的方式。 在总线互连方式中，多个处理机、存储模块及I/O部件等通过各自的接口部件连接在一条公共总线上，或多个计算机模块通过各自的接口部件与一条总线连接。

6.3 动态互连网络 每一次总线只能用于一个源部件到一个或多个目的部件之间的数据传送。 具有价格低、带宽较窄的特点。

6.3 动态互连网络 二. 交叉开关互连方式 交叉开关互连方式通过开关把多个处理机、存储器模块或其他I/O设备连接在一起，形成一种网络结构。 P1 P2 P16 M1 M2 M16 网络中行线和列线交叉点有开关控制其接通与否。 每个开关只需两种状态：通与断。

6.3 动态互连网络 三. 多级网络互连方式 是把多个单级互连网络通过交换开关或交叉开关串联起来而构成的网络。 构成多级互连网络的三要素： a×b 开关 ISC1 ISC2 ISCn 第1级 第n-1级 1 b - 1 b 2b - 1 b + 1 bm - b bm - 1 第0级 a - 1 a a + 1 2a - 1 am - a am - 1 构成多级互连网络的三要素： 1）交换开关 2）拓扑结构 3）控制方式

6.3 动态互连网络 （１）交换开关 简单开关逻辑 C 1

6.3 动态互连网络 2×2开关的四种连接方式 1 ( a ) 直送 ( b ) 交叉 ( c ) 上播 ( d ) 下播 　图中表示了直通、交叉、上播和下播四种允许的状态，称为合法状态。如果出现两个输入端连接到同一个输出端的状态，就会造成信号的冲突，此状态为非法。

6.3 动态互连网络 开关模块的合法状态 输入与输出之间只有一对一的关系,即排除了上播和下播的可能性时的连接.

6.3 动态互连网络 （2）控制方式 对开关的控制方式有三种不同的控制方式： 1） 级控制 2）单元控制 3） 部分级控制 即每一级中所有的开关模块使用同一个控制信号，所以该级中的每一个开关都处于同一种状态。 2）单元控制 系统中的每一个开关模块都有自己专用的控制信号，实施个别控制，各开关均可处于自己特定的状态。 3） 部分级控制 在一个n级的网络中，取0 ≤ i ≤ n – 1，第i级的所有开关用i + 1个信号进行控制。

1．Ω（Omega）网络（多级混洗交换网络） 四. 几种主要多级网络 1．Ω（Omega）网络（多级混洗交换网络） 一个用若干级全混洗网络将开关连接起来组成的多级网络称为Ω网络。 由于采用全混洗网络是这个多级网络组织的基本特色，所以Ω网络又称为多级混洗交换网络。 1 2 3 4 5 6 7 输入端 输出端 C3 C1 C0 C2 K2 K1 K0 Ω网络中，开关采用的是单元控制方式。

6.3 动态互连网络 终端标记法可以描述为：以待连接终端（输出端）号的二进制编码作为对开关控制的基准，其中的每一位用作对应开关级中开关单元的控制信号，从而实现从指定的源端到终端间的连接。 1 2 3 4 5 6 7 K2 K1 K0 终端（D） 输入端 输出端 ① ① （000） ② （110） ② ③ ③ （010） 源端（S） 发生阻塞

6.3 动态互连网络 阻塞网络: 网络总是可以实现一对或多对输入输出的连接，但可能出现几对互连的端口之间发生冲突。 非阻塞网络: 可以实现任意端口之间的连接，不会产生如阻塞网络中出现的那种冲突。

6.3 动态互连网络 2．STARAN网络 STARAN网络的开关可以按级控制，也可以按组控制。 fi 输入端 输出端 1 1 2 3 4 1 1 2 3 4 5 6 7 输入端 输出端 C0 C2 C3 C1 K0 K1 K2 I A B C D E G F H J K L STARAN网络的开关可以按级控制，也可以按组控制。

6.3 动态互连网络 按级控制方式以级为单位，即一个控制信号可对一级中的全部开关作同样的控制。按级控制方式可以实现输入输出端的交换置换，这时的网络又可以称作交换网络。 按组控制方式则是将第i级的开关分成i + 1组，给每组施以控制信号，使组内各开关产生同样的动作。按组控制方式可以实现移数置换，这时可以称作移数网络。

6.3 动态互连网络 f x E Å = ) ( ⑴ 按级控制和交换置换 fi 1 6.3 动态互连网络 ⑴ 按级控制和交换置换 在右上图有一个开关控制示意图，假定开关的两个输入端分别标注以“0”和“1”，同样也给输出端标上“0”和“1”的标注。在直送方式下，0→0，1→1；而在交叉方式下，则有0→1，1→0。如果将这种传输情况看作二进制运算，那末控制信号fi就是参与逻辑运算的一个变量，其逻辑关系可以表示为： i f x E Å = ) ( fi=0时，表示直送； fi=１时，表示交叉。

除了F =（000）时，实现的是恒等置换外，其余7种F值所实现的是交换式的置换。比如，F =（010）时，输入与输出都分成从0~3和4~7两组，在对应组中进行前两位与后两位之间的位置交换。

由此推出的结论是：当fi = 1时，就有Ci置换。 1 2 3 4 5 6 7 F = (010) F = (011) F = (100) F = (110) F = (111) F = (001) F = (000) 也就是说，STARAN网络所实现的正是输入与输出端之间的三种方体置换，而且他们分别实现的是C0、C1和C2置换。非常有意思的是，C0 是 f0 = 1 时得到的置换，C1 是 f1 = 1 时得到的置换，同样，C2 是 f2 = 1 时得到的置换。因此， STARAN网络又称为多立方体网络。 由此推出的结论是：当fi = 1时，就有Ci置换。 于是，如果F =（011），就有C0置换，再有C1置换，简写成： C1（C0），或者Cube0 + Cube1。

6.3 动态互连网络 ⑵ 按组控制及移数置换 五. 动态网络的比较 （见课本p265 表7.3） 在N×N的STARAN网络中，第i级的开关分成i + 1组，每组一个控制信号。对于N = 8时，共3级开关K0，K1，K2，共包含有6个控制信号：F = （f23 f22 f21 f12 f11 f0）。 一个N×N的STARAN网络，在采用按组控制后，可以实现( n² + n + 2 ) / 2种移数置换。N = 8时，可实现的移数置换为7种。 五. 动态网络的比较 （见课本p265 表7.3）

练习 1．反映网络在理想通信模式下通信带宽的特性是（ ） A.度 B.直径 C.带宽总和 D.等分带宽 1．反映网络在理想通信模式下通信带宽的特性是（ ） A.度 B.直径 C.带宽总和 D.等分带宽 2．结构不对称的静态互联网络是（ ）。 A. 线性阵列 B. 环网 C. 立方体网络 D. 全连接网络 3. 有64个结点的网络的PM2I函数的个数是（ ）。 A. 4 B. 6 C. 8 D. 12

练习 4. 有32个结点的立方体连接的互联函数的个数是（ ）。 A. 2 B. 3 C. 4 D. 5 4. 有32个结点的立方体连接的互联函数的个数是（ ）。 A. 2 B. 3 C. 4 D. 5 5. 用N=16 的互联网络互联16 个处理器，编号为0~15，若网络实现的互联函数为Shuffle (Shuffle)，则从12 号处理器连接到的处理器号是（ ）。 A. 9 B. 6 C. 3 D. 12

答案 1.D 2.A 3.D 4. D 5. C