2009-7-27 计算机系统结构 1
本章内容：介绍用于多机并行计算的各种网络,它们统称为互连网络,
缩写符号是 ICN（ Interconnection Network） 。
互连网络是一种由 开关元件 按照一定的拓朴结构和控制方式构成的网络，用来实现多处理机、多计算机之间或多个功能部件之间的连接，是多处理机、多计算机系统的核心。
互连网络的设计目标：
通过互连网络连接的多个部件能实现灵活的连接变换、能提供部件间的通信的最大并行性。
第七章 互连网络 (P394)
2009-7-27 计算机系统结构 2
2009-7-27 计算机系统结构 3
7.1 目的与作用
(1) 当前提高计算速度的主要措施，一是改进器件，二是多处理单元并行计算。 ICN是供多处理单元传输数据的高速通路，对并行计算时间影响很大。
(2) ICN与处理单元的连接模型
(3) ICN的主要操作,置换 (N－ N),广播 (1 － N),选播 (1 － N’)。
输入端 IC N 输出端 输入端 IC N 输出端
(a ) 处理单元 / 处理单元的连接 (b ) 处理单元 / 存储单元 的连接
0 0
（开关网络）
N - 1 N - 1
0 0
（开关网络）
N - 1 N - 1
处理单元 0
处理单元 N -1
存储单元 0
存储单元 N -1
处理单元 0
处理单元 N -1
2009-7-27 计算机系统结构 4
(1) 网络规模一般说来，网络用图来表示。其结点数称为网络规模。
(2)结点度与结点相连接的边 (即链路或通道 )的数目称为结点度。在单向通道的情况下，进入结点的通道数叫做 入度,而从结点出来的通道数则称为 出度 。
结点度应尽可能地小并保持恒定。
(3)距离两结点之间相连的最少边数。
(4)网络直径网络中任意两个结点间 最短路径 长度的 最大值 称为网络直径。网络直径应当尽可能地小。
(5)等分宽度当某一网络被切成相等的两半时，沿切口的最小边数 (通道 )称为通道等分宽度。
(6)路由在网络通信中对路径的选择与指定。通常见到的处理单元之间的数据路由功能有 移数,混洗、交换、广播 (一对全体 ),选播 (多对多 )等。
基本概念
2009-7-27 计算机系统结构 5
(1)通用网 /专用网通用网 （原用于计算机之间交换信息的普通网络）,专用网 （专用于并行计算系统各处理单元之间并行交换数据的特殊网络） ； 通用网包括以太网、电话拨号网等，专用网在后面介绍。
(2)串行网 /并行网串行网 （多个结点的发送操作在时间上不能重叠）,并行网 （多个结点的发送操作在时间上可以重叠） ； 计算机局域网 LAN（如以太网、令牌环网）多属串行网，计算机广域网是异步并行网。
(3)同步网 /异步网（并行网再细分）
同步网 （多个结点必须朝同一方向、以同一距离、同时开始发送）,异步网
（多个结点可以朝不同方向、以不同距离、不同时开始发送，可能冲突） ；
(4)静态网 /动态网（ P402和 P408）
静态网 （结点之间有 固定连接 ）,动态网 （结点之间的连接 关系不固定，须通过开关导向或地址识别来确定当前的目的结点 ） ；
互连网络的分类
2009-7-27 计算机系统结构 6
静态网络使用直接链路，它一旦构成后就固定不变。
静态网络（ P402）
在 N很小的情况下，线性阵列相当经济和合理的。由于直径随 N线性增大，因此当 N比较大时，就不应使用了。
下面介绍几种常用的静态网络。
1.线性阵列
2009-7-27 计算机系统结构 7
环可以单向工作，也可以双向工作。
它是对称的，结点度是常数 2。
双向环的直径为 N/2，单向环的直径是 N。
2,环与带弦环
2009-7-27 计算机系统结构 8
i=1 i=2
0
7 1
i=0
6 2
5 3
4
3,循环移数网络
2009-7-27 计算机系统结构 9
4,树形和星形
2009-7-27 计算机系统结构 10
5,胖树形
2009-7-27 计算机系统结构 11
6,网格形和环网形
2009-7-27 计算机系统结构 12
7,超立方体
2009-7-27 计算机系统结构 13
为了达到多用或通用的目的，我们需要采用动态连接网络，
它能根据程序要求实现所需的通信模式动态连接特性。
按照价格和性能增加的顺序，动态连接网络的排队次序为总线系统、多级互连网络 (MIN)和交叉开关网络。
动态互接网络总线系统价格较低，存在总线争用。
1.总线系统
2009-7-27 计算机系统结构 14
交叉开关网络是单级网络，它由交叉点上的一元开关构成。
通常，这类交叉开关网络需要使用 n× m个交叉点开关。正方形交叉开关网络 (n＝ m)可以无阻塞地实现 n!种置换。
每个周期可以实现 n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。
对小型系统来说性能价格比较高。
但是单级交叉开关网络一旦构成后将不能扩充。
2.交叉开关网络
2009-7-27 计算机系统结构 15
总线的造价最低，但其缺点是可用的带宽较窄，容易产生故障。
由于交叉开关的硬件复杂性以 n2上升，所以其造价最为昂贵。但是，交叉开关的带宽和路由性能最好。如果网络的规模较小，它是一种理想的倍选择。
多级网络则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网络的级数而上升。另外，由于增加了连线和开关复杂性，价格也是一种限制因素。
总线、多级网络、交叉开关的对比
2009-7-27 计算机系统结构 16
特点：成本低，并行性差。
(1) 拓扑结构 (硬件,P402-P407),直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。
(2) 传输协议 (使用规则，软件,P427-P435),碰撞争用，令牌协议，剑桥环。
(3) 主要参数 (P399),直径，中剖宽度，结点的度，最长边。
示例：
(4) 典型代表：以太网，令牌网（环或直线）。
7.2 通用网
2009-7-27 计算机系统结构 17
特点：并行度高，造价昂贵。
(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.循环函数一个网络通过开关切换可以形成多个映射关系，所以要用,互连函数族,来定义一个网络。
7.3 专用网
2009-7-27 计算机系统结构 18
定义,单级 ICN只使用一级开关，如下图所示。
开关的每种接通组合方式可用一个互连函数表示。
f( j入 ) = j出,0≤ j≤N -1
在互连函数中，记：
N ── 结点数
n = log2N ── 维数
j= Xn-1…… X0 ─ ─ 结点编号的二进制形式，位数为 n。
互连函数族的组成必须使网络成为 连通图 。
(2) 单级 ICN
ICN
0 0
N-1 N-1
2009-7-27 计算机系统结构 19
该网络由立方体 函数定义,立方体 函数族有 n个成员,分别是 Cube0,Cube1
,……,Cuben-1。
立方体 函数 定义,Cubei的功能 是对 入端结点编号二进制形式的第 i位取反
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
例如,Cube0(0)=1,Cube3(7)=15。
n=3的单级立方体网络拓扑形状如 右 图所示 。
单级立方体网 （ Cube网,P396第 1行 / P405第 4行）
2 3
0 1
6 7
4 5
最坏情况下的传输需对输入结点编号的全部
n位取反。所以单级立方体网络的直径是 n。
立方体函数 性质,结合律,交换律 以及 自反律 （ Cubei重复使用 2次的结果与原始自变量相同）。
2009-7-27 计算机系统结构 20
该网络由 混洗函数 （ 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)所示,其连接规律就像洗牌 。
单级混洗 -交换网 （ P396倒数第 8行 ）
0 1 2 3 4 5 6 7
n=3的 混洗 网络拓扑形状如下图 绿线 所示，可以看出它不是一个 连通图,所以还需要增加一个交换函数 交换函数 （图中 红线 所示），才能构成完整的单级混洗 — 交换网络。
性质 1,shuffle（ Xn-1Xn-2……X0 ） = Xn-2……X0Xn -1（ 循环左移）
性质 2,shufflen（ j） = j
单级混洗 —
交换网络的直径是 2n-1。
2009-7-27 计算机系统结构 21
2009-7-27 计算机系统结构 22
交换置换（ P395）
E(Xn-1Xn-2… X1X0)=Xn-1Xn-2… X1X0，
其中 0≤ i≤n -1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
n=3的交换置换形状如 右 图所示。
交换置换函数定义：对入端结点编号二进制形式的第 0位取反
0 1 2 3 4 5 6 7
2009-7-27 计算机系统结构 23
该网络由 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）,获得出端结点编号 。
单级加减 2i网 （ PM2I网，移数网,P398倒数第 2行）
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
2009-7-27 计算机系统结构 24
N = 8的 PM2+i网络拓扑形状如图所示，
性质 1：对相同的 i值,PM2+i
与 PM2-i函数的传送路径相同,
方向相反 （ 右图中所有箭头反向即为 PM2-1的拓扑形状 ） ；
性质 2,PM2+(n-1) = PM2-(n-1)。
根据性质 2,我们知道单级 PM2I网络实际上只能实现 2n-1种不同的置换 。
单级 PM2I网络的直径是 。
可以看出它包含多个强连通子图 （ 即除去若干边以后仍能保证任何一对结点互相可达 ）,所以这 2n个函数并不是实现互连网的最小集合 。 实际应用中为了降低造价,人们往往取它们的一个子集来构造互连网 。
2/n
i=1 i=2
0
7 1
i=0
6 2
5 3
4
2009-7-27 计算机系统结构 25
各种互连函数总结
E(Xn-1Xn-2… X1X0)=Xn-1Xn-2… X1X0，
其中 0≤ i≤n -1
交换置换函数定义
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
立方体函数定义,Cubei的功能是对入端结点编号二进制形式的第 i位取反均匀洗牌
shuffle（ Xn-1Xn-2…… X0） = Xn-2…… X0Xn-1（ 循环左移 ）
PM2I函数定义,PM2± i的功能是对入端结点编号加或减 2i,然后再作模 N运算
PM2+i（ X） = X + 2i mod N
PM2-i（ X） = X - 2i mod N
其中 X = 0 ～ N - 1,i = 0 ～ n - 1。
2009-7-27 计算机系统结构 26
(3) 多级 ICN（ P409）
定义：多级 ICN使用多级开关,使得数据在一次通过网络的过程中可以实现的置换种类更多 。
通常在 N个结点的网络中,多级 ICN由 n级构成 （ n = log2N） 。
经典的多级互连网有 多级立方体网,多级混洗 — 交换网 和 多级 PM2I网 。 我们只学习多级混洗 — 交换网 。
多级立方体网和多级混洗 — 交换网不使用单级互连网中的那种多路选择开关
,而是用一种 2输入 /2输出的 二元交换开关,以减少开关总数 。 二元交换开关的基本接通状态有,直连,,,交换,,,上播,和,下播,,在进行数据置换时只能使用前 2种 。
各开关的控制信号可采用 3种分配方式之一,级控方式,部分级控方式 和 单元控制方式 。
级控方式 就是同一级 （ 即同一列 ） 开关共用一个控制信号,动作保持一致；
部分级控方式 在第 i级设置 i+1个独立的控制信号,每个信号管辖若干开关； 单元控制方式 为每个开关独自设置一个控制信号,各开关动作独立,性能比前两种方式都更灵活,结构也更复杂 。
( a ) 直连 (b ) 交换 (c ) 上播 (d ) 下播
2009-7-27 计算机系统结构 27
多级混洗 — 交换网络（ P410/P436）
多级混洗 — 交换网络又称为 Omega网 。
多级混洗 — 交换网络结构：它 由 n级构成,每一级包含 一个无条件 混洗拓扑 线路 和 一列可控的二元 交换开关,前后重复,便于制造 。 如 P436图 7.43所示 。
各级编号是 n-1,……,0,即按 降序排列 。
在多级混洗 — 交换网络中,
单独一级 混洗拓扑线路可完成一次 数据混洗 （ shuffle）,
单独一列二元交换开关在处于,交换,状态时可完成一次 交换操作 （ Cube0
）
如果各级二元交换开关都处于,直连,状态,N个结点的数据通过网络仅经过 n次混洗操作,排列顺序最终 恢复输入状态 （ 混洗函数性质 2） ；
如果各级二元交换开关都处于,交换,状态,则 N个结点的数据在每次混洗之后紧接着一次交换 （ Cube0）,也就是地址码的最低位取反,最后 n位地址均被取反 。
程序员根据数据置换或复制的需要,可以灵活地设置各开关的状态 。
2009-7-27 计算机系统结构 28
多级混洗 — 交换网络寻径算法（路由算法）
目的,根据给定的输入 /输出对应关系,确定各开关的状态 。
名称,源 -目的地址异或法操作,将任一个输入地址与它要到达的输出地址作异或运算,其结果的 biti
位控制数据到达的第 i级开关,,0” 表示,直连,,,1” 表示,交换,。
例如给定传输 101B→ 011B,二者异或结果为 110B,于是从 101B号输入端开始,把它遇到的第 2级开关置为,交换,,第 1级开关置为,交换,,第 0
级开关置为,直连,。 如下图 红线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000 00 0
00 1 00 1
0 1 0 0 1 0
0 11 01 1
1 00 1 00
1 0 1 1 01
11 0 1 10
1 11 1 11
2009-7-27 计算机系统结构 29
Omega网寻径冲突给定传输 101B→ 011B,二者异或结果为 110B,路径 如下图 红线 所示 。
给定传输 011→ 010B,二者异或结果为 001B,路径 如下图 白线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111
2009-7-27 计算机系统结构 30
7.5 广播与选播算法（ P425）
广播是将一个结点的数据复制到全部 N个结点；选播是将一个结点的数据复制到多个（ N'个）结点,1≤N'≤N。
研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数（又称 "流量 "或 "
通道数 "）最少的方案。
这里所说的并行传输，是指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行（具有这种能力的互连网不属于现在的讨论范围）。
显然对不同的网络，适用的广播与选播算法也不同。下面举几个具体实例。
2009-7-27 计算机系统结构 31
7.5.1 广播算法
(1)单级立方体网络广播算法算法：
按任意顺序使用 Cube0 ～ Cuben-1各一次,每一步都从当前拥有数据的所有结点同时发往等量的无数据结点,也就是将网络中拥有数据的结点数加倍 。 如图 6.9所示 （ 图中实线箭头表示一个数据的一次实际传送,虚线指出上一步已有数据的结点 ） 。 这种算法的时间和流量是由结点数 N决定的常量 。
时间流量
Nn 2lo g
1
0
1122
n
i
ni N
2009-7-27 计算机系统结构 32
2 3
0 1
6 7
4 5
单级立方体网络广播算法实例从节点 0开始，顺序是 cube0－ >cube2
0 4 2 6 1 5 3 7
000
000
000
000
001
011
111
001
011001 101
010
010 110100
2009-7-27 计算机系统结构 33
单级立方体网络广播算法 实例
0 0 0 0
C u b e
3
0 0 0 0 1 0 0 0
C u b e
2
0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0
C u b e
1
0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
C u b e
0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5
单级立方体网络广播算法 （顺序是 C ub e
3
～ C ube
0
）
2009-7-27 计算机系统结构 34
7.5.2 选播算法
1,选播时间最少算法是通过单播时间最少算法裁剪而成（ P426 7.36(a)→ (b)）
选播算法设计目标有 3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案。
2009-7-27 计算机系统结构 35
3,实现第 3种目标的一种重要算法是贪婪算法（教材 P426图 7.36(b)）。
不论对何种网络，贪婪算法总是重复使用一个固定的操作规则,从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步，如此循环，直至传遍所有需要数据的结点。 如果最后发现某个通道（即一次数据发送操作）不在通往给定目标结点的路径上，则应将其删去。
2.选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树” （ 教材 P426图 7.36(c)）。
2009-7-27 计算机系统结构 36
(1)单级网格网（ Mash网）贪婪算法算法,以图 7.36为例，小图 (a)指出总共有 1个源结点 S和 5个目的结点。图 (b)指出从 S出发，首先应向右邻结点发送数据，因为 S的左方只有 1个目的结点、上方有 3个目的结点、右方有４个目的结点；第二步从这２个拥有数据的结点出发，可以再向右发送（有 3个目的结点），也可以改向上发送（也有 3个目的结点）,…… 。只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的。
2009-7-27 计算机系统结构 37
(2)单级立方体网络贪婪算法源结点编号的二进制形式 00在 bit0位与两个目的结点的二进制形式 01,11
都不相同,而在 bit1位仅与一个目的结点的二进制形式不同,所以应该先传
bit0方向,再传
bit1方向,如右图 (a)所示,这时流量 =2；如果先传 bit1方向,
再传 bit0方向,
如右图 (b)所示,
则流量 =3。
0 0 0 0
Cu b e
0
Cu b e
1
0 0 01 0 0 1 0
Cu b e
1
Cu b e
0
0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1
(a) 先传 Cu b e
0
方向，流量 = 2 (b ) 先传 C u b e
1
方向，流量 =3
单级立方体网络贪婪算法的简单例子算法：
以教材 P426图 7.37为例。小图 (a)指出广播算法的时间是 4，流量是 15。
Cube0 ～ Cuben-1的使用顺序对广播算法的时间和流量没有影响，
但对小图 (b)的选播算法的时间和流量有影响。
先看下图例子：已知 N=4,维数 n=2,源结点是 0，目的结点是 1和 3。
2009-7-27 计算机系统结构 38
0 1 0 1
Cu b e
3
0 1 0 1 1 1 0 1
Cu b e
1
0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1
Cu b e
0
0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0
Cu b e
2
0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0
5 1 4 0 7 3 6 2 1 3 9 1 2 8 1 5 1 1 1 4 1 0
单级立方体网络贪婪算法的复杂例子再看教材 P426图 7.37(b)的例子。源结点编号的二进制形式 0101在 Cube0 ～
Cube3位分别与 5,5,4,5个目的结点的二进制形式不同，所以 Cube2方向应该最后发送，其它 3个方向的发送先后顺序则没有限制。教材 P427采用了
Cube3,Cube1,Cube0,Cube2的发送顺序，如下图所示，时间 =4，总流量 =10。
计算机系统结构 392003.3.1
单级立方体网络贪婪算法过程
1。比较各维 bit不同个数，定维的顺序
2。画树
3。修剪树
2009-7-27 计算机系统结构 40
本章小结
(1) 通用网的拓扑结构，传输协议，主要参数，典型代表；
(2) 互连函数（置换，循环）的 4种表示方式；
(3) 单级立方体网（ Cube网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(4) 单级混洗 -交换网的定义，拓扑形状，直径，性质，互连函数族的组成；
(5) 单级加减 2i网（ PM2I网，移数网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(6) 二元交换开关，控制信号的 3种分配方式；
(7) 多级混洗 — 交换网络的结构，寻径算法（路由算法）。
习题,P446，题 3，题 10，题 26(1)～ (2)，题 27(3)。
计算机系统结构 412003.3.1
在 Cube0 ～ Cube3位分别与 7,6,5,6个目的结点的二进制形式不同，所以总时间 =4（如某一位没有与源结点不同的目的结点，则该维不发送，总时间减少 1），并且 Cube0方向应该最先发送,Cube2方向最后发送，其它 2个方向的发送先后顺序没有限制。我们可以采用 Cube0,Cube1,Cube3,Cube2的发送顺序，生成的选播树如下图所示，总流量 =11。
P449,27题 源结点 1010，
目的结点,0000,0001,0011,0100,0101,0111,1111,1101,1001
本章内容：介绍用于多机并行计算的各种网络,它们统称为互连网络,
缩写符号是 ICN（ Interconnection Network） 。
互连网络是一种由 开关元件 按照一定的拓朴结构和控制方式构成的网络，用来实现多处理机、多计算机之间或多个功能部件之间的连接，是多处理机、多计算机系统的核心。
互连网络的设计目标：
通过互连网络连接的多个部件能实现灵活的连接变换、能提供部件间的通信的最大并行性。
第七章 互连网络 (P394)
2009-7-27 计算机系统结构 2
2009-7-27 计算机系统结构 3
7.1 目的与作用
(1) 当前提高计算速度的主要措施，一是改进器件，二是多处理单元并行计算。 ICN是供多处理单元传输数据的高速通路，对并行计算时间影响很大。
(2) ICN与处理单元的连接模型
(3) ICN的主要操作,置换 (N－ N),广播 (1 － N),选播 (1 － N’)。
输入端 IC N 输出端 输入端 IC N 输出端
(a ) 处理单元 / 处理单元的连接 (b ) 处理单元 / 存储单元 的连接
0 0
（开关网络）
N - 1 N - 1
0 0
（开关网络）
N - 1 N - 1
处理单元 0
处理单元 N -1
存储单元 0
存储单元 N -1
处理单元 0
处理单元 N -1
2009-7-27 计算机系统结构 4
(1) 网络规模一般说来，网络用图来表示。其结点数称为网络规模。
(2)结点度与结点相连接的边 (即链路或通道 )的数目称为结点度。在单向通道的情况下，进入结点的通道数叫做 入度,而从结点出来的通道数则称为 出度 。
结点度应尽可能地小并保持恒定。
(3)距离两结点之间相连的最少边数。
(4)网络直径网络中任意两个结点间 最短路径 长度的 最大值 称为网络直径。网络直径应当尽可能地小。
(5)等分宽度当某一网络被切成相等的两半时，沿切口的最小边数 (通道 )称为通道等分宽度。
(6)路由在网络通信中对路径的选择与指定。通常见到的处理单元之间的数据路由功能有 移数,混洗、交换、广播 (一对全体 ),选播 (多对多 )等。
基本概念
2009-7-27 计算机系统结构 5
(1)通用网 /专用网通用网 （原用于计算机之间交换信息的普通网络）,专用网 （专用于并行计算系统各处理单元之间并行交换数据的特殊网络） ； 通用网包括以太网、电话拨号网等，专用网在后面介绍。
(2)串行网 /并行网串行网 （多个结点的发送操作在时间上不能重叠）,并行网 （多个结点的发送操作在时间上可以重叠） ； 计算机局域网 LAN（如以太网、令牌环网）多属串行网，计算机广域网是异步并行网。
(3)同步网 /异步网（并行网再细分）
同步网 （多个结点必须朝同一方向、以同一距离、同时开始发送）,异步网
（多个结点可以朝不同方向、以不同距离、不同时开始发送，可能冲突） ；
(4)静态网 /动态网（ P402和 P408）
静态网 （结点之间有 固定连接 ）,动态网 （结点之间的连接 关系不固定，须通过开关导向或地址识别来确定当前的目的结点 ） ；
互连网络的分类
2009-7-27 计算机系统结构 6
静态网络使用直接链路，它一旦构成后就固定不变。
静态网络（ P402）
在 N很小的情况下，线性阵列相当经济和合理的。由于直径随 N线性增大，因此当 N比较大时，就不应使用了。
下面介绍几种常用的静态网络。
1.线性阵列
2009-7-27 计算机系统结构 7
环可以单向工作，也可以双向工作。
它是对称的，结点度是常数 2。
双向环的直径为 N/2，单向环的直径是 N。
2,环与带弦环
2009-7-27 计算机系统结构 8
i=1 i=2
0
7 1
i=0
6 2
5 3
4
3,循环移数网络
2009-7-27 计算机系统结构 9
4,树形和星形
2009-7-27 计算机系统结构 10
5,胖树形
2009-7-27 计算机系统结构 11
6,网格形和环网形
2009-7-27 计算机系统结构 12
7,超立方体
2009-7-27 计算机系统结构 13
为了达到多用或通用的目的，我们需要采用动态连接网络，
它能根据程序要求实现所需的通信模式动态连接特性。
按照价格和性能增加的顺序，动态连接网络的排队次序为总线系统、多级互连网络 (MIN)和交叉开关网络。
动态互接网络总线系统价格较低，存在总线争用。
1.总线系统
2009-7-27 计算机系统结构 14
交叉开关网络是单级网络，它由交叉点上的一元开关构成。
通常，这类交叉开关网络需要使用 n× m个交叉点开关。正方形交叉开关网络 (n＝ m)可以无阻塞地实现 n!种置换。
每个周期可以实现 n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。
对小型系统来说性能价格比较高。
但是单级交叉开关网络一旦构成后将不能扩充。
2.交叉开关网络
2009-7-27 计算机系统结构 15
总线的造价最低，但其缺点是可用的带宽较窄，容易产生故障。
由于交叉开关的硬件复杂性以 n2上升，所以其造价最为昂贵。但是，交叉开关的带宽和路由性能最好。如果网络的规模较小，它是一种理想的倍选择。
多级网络则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网络的级数而上升。另外，由于增加了连线和开关复杂性，价格也是一种限制因素。
总线、多级网络、交叉开关的对比
2009-7-27 计算机系统结构 16
特点：成本低，并行性差。
(1) 拓扑结构 (硬件,P402-P407),直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。
(2) 传输协议 (使用规则，软件,P427-P435),碰撞争用，令牌协议，剑桥环。
(3) 主要参数 (P399),直径，中剖宽度，结点的度，最长边。
示例：
(4) 典型代表：以太网，令牌网（环或直线）。
7.2 通用网
2009-7-27 计算机系统结构 17
特点：并行度高，造价昂贵。
(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.循环函数一个网络通过开关切换可以形成多个映射关系，所以要用,互连函数族,来定义一个网络。
7.3 专用网
2009-7-27 计算机系统结构 18
定义,单级 ICN只使用一级开关，如下图所示。
开关的每种接通组合方式可用一个互连函数表示。
f( j入 ) = j出,0≤ j≤N -1
在互连函数中，记：
N ── 结点数
n = log2N ── 维数
j= Xn-1…… X0 ─ ─ 结点编号的二进制形式，位数为 n。
互连函数族的组成必须使网络成为 连通图 。
(2) 单级 ICN
ICN
0 0
N-1 N-1
2009-7-27 计算机系统结构 19
该网络由立方体 函数定义,立方体 函数族有 n个成员,分别是 Cube0,Cube1
,……,Cuben-1。
立方体 函数 定义,Cubei的功能 是对 入端结点编号二进制形式的第 i位取反
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
例如,Cube0(0)=1,Cube3(7)=15。
n=3的单级立方体网络拓扑形状如 右 图所示 。
单级立方体网 （ Cube网,P396第 1行 / P405第 4行）
2 3
0 1
6 7
4 5
最坏情况下的传输需对输入结点编号的全部
n位取反。所以单级立方体网络的直径是 n。
立方体函数 性质,结合律,交换律 以及 自反律 （ Cubei重复使用 2次的结果与原始自变量相同）。
2009-7-27 计算机系统结构 20
该网络由 混洗函数 （ 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)所示,其连接规律就像洗牌 。
单级混洗 -交换网 （ P396倒数第 8行 ）
0 1 2 3 4 5 6 7
n=3的 混洗 网络拓扑形状如下图 绿线 所示，可以看出它不是一个 连通图,所以还需要增加一个交换函数 交换函数 （图中 红线 所示），才能构成完整的单级混洗 — 交换网络。
性质 1,shuffle（ Xn-1Xn-2……X0 ） = Xn-2……X0Xn -1（ 循环左移）
性质 2,shufflen（ j） = j
单级混洗 —
交换网络的直径是 2n-1。
2009-7-27 计算机系统结构 21
2009-7-27 计算机系统结构 22
交换置换（ P395）
E(Xn-1Xn-2… X1X0)=Xn-1Xn-2… X1X0，
其中 0≤ i≤n -1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
n=3的交换置换形状如 右 图所示。
交换置换函数定义：对入端结点编号二进制形式的第 0位取反
0 1 2 3 4 5 6 7
2009-7-27 计算机系统结构 23
该网络由 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）,获得出端结点编号 。
单级加减 2i网 （ PM2I网，移数网,P398倒数第 2行）
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
2009-7-27 计算机系统结构 24
N = 8的 PM2+i网络拓扑形状如图所示，
性质 1：对相同的 i值,PM2+i
与 PM2-i函数的传送路径相同,
方向相反 （ 右图中所有箭头反向即为 PM2-1的拓扑形状 ） ；
性质 2,PM2+(n-1) = PM2-(n-1)。
根据性质 2,我们知道单级 PM2I网络实际上只能实现 2n-1种不同的置换 。
单级 PM2I网络的直径是 。
可以看出它包含多个强连通子图 （ 即除去若干边以后仍能保证任何一对结点互相可达 ）,所以这 2n个函数并不是实现互连网的最小集合 。 实际应用中为了降低造价,人们往往取它们的一个子集来构造互连网 。
2/n
i=1 i=2
0
7 1
i=0
6 2
5 3
4
2009-7-27 计算机系统结构 25
各种互连函数总结
E(Xn-1Xn-2… X1X0)=Xn-1Xn-2… X1X0，
其中 0≤ i≤n -1
交换置换函数定义
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
立方体函数定义,Cubei的功能是对入端结点编号二进制形式的第 i位取反均匀洗牌
shuffle（ Xn-1Xn-2…… X0） = Xn-2…… X0Xn-1（ 循环左移 ）
PM2I函数定义,PM2± i的功能是对入端结点编号加或减 2i,然后再作模 N运算
PM2+i（ X） = X + 2i mod N
PM2-i（ X） = X - 2i mod N
其中 X = 0 ～ N - 1,i = 0 ～ n - 1。
2009-7-27 计算机系统结构 26
(3) 多级 ICN（ P409）
定义：多级 ICN使用多级开关,使得数据在一次通过网络的过程中可以实现的置换种类更多 。
通常在 N个结点的网络中,多级 ICN由 n级构成 （ n = log2N） 。
经典的多级互连网有 多级立方体网,多级混洗 — 交换网 和 多级 PM2I网 。 我们只学习多级混洗 — 交换网 。
多级立方体网和多级混洗 — 交换网不使用单级互连网中的那种多路选择开关
,而是用一种 2输入 /2输出的 二元交换开关,以减少开关总数 。 二元交换开关的基本接通状态有,直连,,,交换,,,上播,和,下播,,在进行数据置换时只能使用前 2种 。
各开关的控制信号可采用 3种分配方式之一,级控方式,部分级控方式 和 单元控制方式 。
级控方式 就是同一级 （ 即同一列 ） 开关共用一个控制信号,动作保持一致；
部分级控方式 在第 i级设置 i+1个独立的控制信号,每个信号管辖若干开关； 单元控制方式 为每个开关独自设置一个控制信号,各开关动作独立,性能比前两种方式都更灵活,结构也更复杂 。
( a ) 直连 (b ) 交换 (c ) 上播 (d ) 下播
2009-7-27 计算机系统结构 27
多级混洗 — 交换网络（ P410/P436）
多级混洗 — 交换网络又称为 Omega网 。
多级混洗 — 交换网络结构：它 由 n级构成,每一级包含 一个无条件 混洗拓扑 线路 和 一列可控的二元 交换开关,前后重复,便于制造 。 如 P436图 7.43所示 。
各级编号是 n-1,……,0,即按 降序排列 。
在多级混洗 — 交换网络中,
单独一级 混洗拓扑线路可完成一次 数据混洗 （ shuffle）,
单独一列二元交换开关在处于,交换,状态时可完成一次 交换操作 （ Cube0
）
如果各级二元交换开关都处于,直连,状态,N个结点的数据通过网络仅经过 n次混洗操作,排列顺序最终 恢复输入状态 （ 混洗函数性质 2） ；
如果各级二元交换开关都处于,交换,状态,则 N个结点的数据在每次混洗之后紧接着一次交换 （ Cube0）,也就是地址码的最低位取反,最后 n位地址均被取反 。
程序员根据数据置换或复制的需要,可以灵活地设置各开关的状态 。
2009-7-27 计算机系统结构 28
多级混洗 — 交换网络寻径算法（路由算法）
目的,根据给定的输入 /输出对应关系,确定各开关的状态 。
名称,源 -目的地址异或法操作,将任一个输入地址与它要到达的输出地址作异或运算,其结果的 biti
位控制数据到达的第 i级开关,,0” 表示,直连,,,1” 表示,交换,。
例如给定传输 101B→ 011B,二者异或结果为 110B,于是从 101B号输入端开始,把它遇到的第 2级开关置为,交换,,第 1级开关置为,交换,,第 0
级开关置为,直连,。 如下图 红线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000 00 0
00 1 00 1
0 1 0 0 1 0
0 11 01 1
1 00 1 00
1 0 1 1 01
11 0 1 10
1 11 1 11
2009-7-27 计算机系统结构 29
Omega网寻径冲突给定传输 101B→ 011B,二者异或结果为 110B,路径 如下图 红线 所示 。
给定传输 011→ 010B,二者异或结果为 001B,路径 如下图 白线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111
2009-7-27 计算机系统结构 30
7.5 广播与选播算法（ P425）
广播是将一个结点的数据复制到全部 N个结点；选播是将一个结点的数据复制到多个（ N'个）结点,1≤N'≤N。
研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数（又称 "流量 "或 "
通道数 "）最少的方案。
这里所说的并行传输，是指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行（具有这种能力的互连网不属于现在的讨论范围）。
显然对不同的网络，适用的广播与选播算法也不同。下面举几个具体实例。
2009-7-27 计算机系统结构 31
7.5.1 广播算法
(1)单级立方体网络广播算法算法：
按任意顺序使用 Cube0 ～ Cuben-1各一次,每一步都从当前拥有数据的所有结点同时发往等量的无数据结点,也就是将网络中拥有数据的结点数加倍 。 如图 6.9所示 （ 图中实线箭头表示一个数据的一次实际传送,虚线指出上一步已有数据的结点 ） 。 这种算法的时间和流量是由结点数 N决定的常量 。
时间流量
Nn 2lo g
1
0
1122
n
i
ni N
2009-7-27 计算机系统结构 32
2 3
0 1
6 7
4 5
单级立方体网络广播算法实例从节点 0开始，顺序是 cube0－ >cube2
0 4 2 6 1 5 3 7
000
000
000
000
001
011
111
001
011001 101
010
010 110100
2009-7-27 计算机系统结构 33
单级立方体网络广播算法 实例
0 0 0 0
C u b e
3
0 0 0 0 1 0 0 0
C u b e
2
0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0
C u b e
1
0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
C u b e
0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5
单级立方体网络广播算法 （顺序是 C ub e
3
～ C ube
0
）
2009-7-27 计算机系统结构 34
7.5.2 选播算法
1,选播时间最少算法是通过单播时间最少算法裁剪而成（ P426 7.36(a)→ (b)）
选播算法设计目标有 3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案。
2009-7-27 计算机系统结构 35
3,实现第 3种目标的一种重要算法是贪婪算法（教材 P426图 7.36(b)）。
不论对何种网络，贪婪算法总是重复使用一个固定的操作规则,从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步，如此循环，直至传遍所有需要数据的结点。 如果最后发现某个通道（即一次数据发送操作）不在通往给定目标结点的路径上，则应将其删去。
2.选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树” （ 教材 P426图 7.36(c)）。
2009-7-27 计算机系统结构 36
(1)单级网格网（ Mash网）贪婪算法算法,以图 7.36为例，小图 (a)指出总共有 1个源结点 S和 5个目的结点。图 (b)指出从 S出发，首先应向右邻结点发送数据，因为 S的左方只有 1个目的结点、上方有 3个目的结点、右方有４个目的结点；第二步从这２个拥有数据的结点出发，可以再向右发送（有 3个目的结点），也可以改向上发送（也有 3个目的结点）,…… 。只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的。
2009-7-27 计算机系统结构 37
(2)单级立方体网络贪婪算法源结点编号的二进制形式 00在 bit0位与两个目的结点的二进制形式 01,11
都不相同,而在 bit1位仅与一个目的结点的二进制形式不同,所以应该先传
bit0方向,再传
bit1方向,如右图 (a)所示,这时流量 =2；如果先传 bit1方向,
再传 bit0方向,
如右图 (b)所示,
则流量 =3。
0 0 0 0
Cu b e
0
Cu b e
1
0 0 01 0 0 1 0
Cu b e
1
Cu b e
0
0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1
(a) 先传 Cu b e
0
方向，流量 = 2 (b ) 先传 C u b e
1
方向，流量 =3
单级立方体网络贪婪算法的简单例子算法：
以教材 P426图 7.37为例。小图 (a)指出广播算法的时间是 4，流量是 15。
Cube0 ～ Cuben-1的使用顺序对广播算法的时间和流量没有影响，
但对小图 (b)的选播算法的时间和流量有影响。
先看下图例子：已知 N=4,维数 n=2,源结点是 0，目的结点是 1和 3。
2009-7-27 计算机系统结构 38
0 1 0 1
Cu b e
3
0 1 0 1 1 1 0 1
Cu b e
1
0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1
Cu b e
0
0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0
Cu b e
2
0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0
5 1 4 0 7 3 6 2 1 3 9 1 2 8 1 5 1 1 1 4 1 0
单级立方体网络贪婪算法的复杂例子再看教材 P426图 7.37(b)的例子。源结点编号的二进制形式 0101在 Cube0 ～
Cube3位分别与 5,5,4,5个目的结点的二进制形式不同，所以 Cube2方向应该最后发送，其它 3个方向的发送先后顺序则没有限制。教材 P427采用了
Cube3,Cube1,Cube0,Cube2的发送顺序，如下图所示，时间 =4，总流量 =10。
计算机系统结构 392003.3.1
单级立方体网络贪婪算法过程
1。比较各维 bit不同个数，定维的顺序
2。画树
3。修剪树
2009-7-27 计算机系统结构 40
本章小结
(1) 通用网的拓扑结构，传输协议，主要参数，典型代表；
(2) 互连函数（置换，循环）的 4种表示方式；
(3) 单级立方体网（ Cube网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(4) 单级混洗 -交换网的定义，拓扑形状，直径，性质，互连函数族的组成；
(5) 单级加减 2i网（ PM2I网，移数网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(6) 二元交换开关，控制信号的 3种分配方式；
(7) 多级混洗 — 交换网络的结构，寻径算法（路由算法）。
习题,P446，题 3，题 10，题 26(1)～ (2)，题 27(3)。
计算机系统结构 412003.3.1
在 Cube0 ～ Cube3位分别与 7,6,5,6个目的结点的二进制形式不同，所以总时间 =4（如某一位没有与源结点不同的目的结点，则该维不发送，总时间减少 1），并且 Cube0方向应该最先发送,Cube2方向最后发送，其它 2个方向的发送先后顺序没有限制。我们可以采用 Cube0,Cube1,Cube3,Cube2的发送顺序，生成的选播树如下图所示，总流量 =11。
P449,27题 源结点 1010，
目的结点,0000,0001,0011,0100,0101,0111,1111,1101,1001
