计算机互连网络课件

本章内容：介绍用于多机并行计算的各种网络，它们统称为互连网络，缩写符号是ICN（InterconnectionNetwork）。•互连网络是一种由开关元件按照一定的拓朴结构和控制方式构成的网络，用来实现多处理机、多计算机之间或多个功能部件之间的连接，是多处理机、多计算机系统的核心。

•互连网络的设计目标：通过互连网络连接的多个部件能实现灵活的连接变换、能提供部件间的通信的最大并行性。第七章互连网络(P394)2003.3.11计算机系统结构7.1目的与作用(1)当前提高计算速度的主要措施，一是改进器件，二是多处理单元并行计算。ICN是供多处理单元传输数据的高速通路，对并行计算时间影响很大。(2)ICN与处理单元的连接模型(3)ICN的主要操作：置换(N－N)，广播(1－

N)，选播(1－

N’)。2003.3.12计算机系统结构网络规模 一般说来，网络用图来表示。其结点数称为网络规模。(2) 结点度 与结点相连接的边(即链路或通道)的数目称为结点度。在单向通道的情况下，进入结点的通道数叫做入度，而从结点出来的通道数则称为出度。结点度应尽可能地小并保持恒定。(3) 距离

两结点之间相连的最少边数。(4) 网络直径 网络中任意两个结点间最短路径长度的最大值称为网络直径。网络直径应当尽可能地小。(5) 等分宽度 当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度。(6) 路由 在网络通信中对路径的选择与指定。通常见到的处理单元之间的数据路由功能有移数、混洗、交换、广播(一对全体)、选播(多对多)等。基本概念2003.3.13计算机系统结构静态网络使用直接链路，它一旦构成后就固定不变。静态网络（P402）在N很小的情况下，线性阵列相当经济和合理的。由于直径随N线性增大，因此当N比较大时，就不应使用了。下面介绍几种常用的静态网络。1.线性阵列2003.3.15计算机系统结构环可以单向工作，也可以双向工作。它是对称的，结点度是常数2。双向环的直径为N/2，单向环的直径是N。2.环与带弦环2003.3.16计算机系统结构3.循环移数网络2003.3.17计算机系统结构5.胖树形2003.3.19计算机系统结构6.网格形和环网形2003.3.110计算机系统结构7.超立方体2003.3.111计算机系统结构交叉开关网络是单级网络，它由交叉点上的一元开关构成。通常，这类交叉开关网络需要使用n×m个交叉点开关。正方形交叉开关网络(n＝m)可以无阻塞地实现n!种置换。每个周期可以实现n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。对小型系统来说性能价格比较高。但是单级交叉开关网络一旦构成后将不能扩充。2.交叉开关网络2003.3.113计算机系统结构总线的造价最低，但其缺点是可用的带宽较窄，容易产生故障。由于交叉开关的硬件复杂性以n2上升，所以其造价最为昂贵。但是，交叉开关的带宽和路由性能最好。如果网络的规模较小，它是一种理想的倍选择。多级网络则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网络的级数而上升。另外，由于增加了连线和开关复杂性，价格也是一种限制因素。总线、多级网络、交叉开关的对比2003.3.114计算机系统结构特点：成本低，并行性差。(1)拓扑结构(硬件，P402-P407)：直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。(2)传输协议(使用规则，软件，P427-P435)：碰撞争用，令牌协议，剑桥环。(3)主要参数(P399)：直径，中剖宽度，结点的度，最长边。示例：(4)典型代表：以太网，令牌网（环或直线）。7.2通用网2003.3.115计算机系统结构定义：单级ICN只使用一级开关，如下图所示。开关的每种接通组合方式可用一个互连函数表示。

f(j入)=j出，0≤j≤N-1在互连函数中，记：

N──结点数

n=log2N──维数

j=Xn-1……X0──

结点 编号的二进制形式，位数为n。互连函数族的组成必须使网络成为连通图。(2)单级ICN2003.3.117计算机系统结构该网络由立方体函数定义，立方体函数族有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的单级立方体网络拓扑形状如右图所示。最坏情况下的传输需对输入结点编号的全部n位取反。所以单级立方体网络的直径是n。

立方体函数性质：结合律、交换律以及自反律（Cubei重复使用2次的结果与原始自变量相同）。单级立方体网（Cube网，P396第1行/P405第4行）2003.3.118计算机系统结构该网络由混洗函数（shuffle）与交换函数（exchange即Cube0）定义，或者说它的互连函数族只有这两个成员。

混洗函数定义： 2jmod（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：shuffle（Xn-1Xn-2……X0）=Xn-2……X0Xn-1（循环左移）

性质2：shufflen（j）=j

n=3的混洗网络拓扑形状如下图绿线所示，可以看出它不是一个连通图，所以还需要增加一个交换函数（图中红线所示），才能构成完整的单级混洗—交换网络。单级混洗—交换网络的直径是2n-1。单级混洗-交换网（P396倒数第8行）2003.3.119计算机系统结构该网络由PM2I函数定义，PM2I函数共有n对成员，分别是PM2±0，PM2±1，……，PM2±(n-1)。PM2I函数定义：PM2±i的功能是对入端结点编号加或减2i，然后再作模N运算

PM2+i（j）=j+2imodN PM2-i（j）=j-2imodN其中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（modN），获得出端结点编号。单级加减2i网（PM2I网，移数网，P398倒数第2行）2003.3.121计算机系统结构

N=8的PM2+i网络拓扑形状如下图所示，可以看出它包含多个强连通子图（即除去若干边以后仍能保证任何一对结点互相可达），所以这2n个函数并不是实现互连网的最小集合。实际应用中为了降低造价，人们往往取它们的一个子集来构造互连网。

性质1：对相同的i值，PM2+i与PM2-i函数的传送路径相同，方向相反（右图中所有箭头反向即为PM2-1的拓扑形状）；

性质2：PM2+(n-1)=PM2-(n-1)。

根据性质2，我们知道单级PM2I网络实际上只能实现2n-1种不同的置换。单级PM2I网络的直径是。2003.3.122计算机系统结构各种互连函数总结

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+2imodN PM2-i（X）=X-2imodN其中X=0～N-1，i=0～n-1。2003.3.123计算机系统结构多级混洗—交换网络（P410/P436）多级混洗—交换网络又称为Omega网。多级混洗—交换网络结构：它由n级构成，每一级包含一个无条件混洗拓扑线路和一列可控的二元交换开关，前后重复，便于制造。如P436图7.43所示。各级编号是n-1，……，0，即按降序排列。在多级混洗—交换网络中，单独一级混洗拓扑线路可完成一次数据混洗（shuffle），而单独一列二元交换开关在处于“交换”状态时可完成一次交换操作（Cube0）。如果各级二元交换开关都处于“直连”状态，N个结点的数据通过网络仅经过n次混洗操作，排列顺序最终恢复输入状态（混洗函数性质2）；如果各级二元交换开关都处于“交换”状态，则N个结点的数据在每次混洗之后紧接着一次交换（Cube0），也就是地址码的最低位取反，最后n位地址均被取反。程序员根据数据置换或复制的需要，可以灵活地设置各开关的状态。2003.3.125计算机系统结构多级混洗—交换网络寻径算法（路由算法）目的：根据给定的输入/输出对应关系，确定各开关的状态。名称：源-目的地址异或法操作：将任一个输入地址与它要到达的输出地址作异或运算，其结果的biti位控制数据到达的第i级开关，“0”表示“直连”，“1”表示“交换”。例如给定传输101B→011B，二者异或结果为110B，于是从101B号输入端开始，把它遇到的第2级开关置为“交换”，第1级开关置为“交换”，第0级开关置为“直连”。如下图红线所示。2003.3.126计算机系统结构7.4.2四种寻径方式对应的总时间（P415）(1)线路交换T=(Lt/B)×D+L/B其中：Lt是为建立路径所需的小信息包的长度，(2)存储转发T=(L/B)×D+L/B=(D+1)×L/B(3)虚拟直通T=(Lh/B)×D+L/B=(Lh×D+L)/B其中：Lh是消息的寻径头部的长度，(4)虫蚀寻径T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B其中：Lf是片的长度，2003.3.129计算机系统结构7.5广播与选播算法（P425）广播是将一个结点的数据复制到全部N个结点；选播是将一个结点的数据复制到多个（N'个）结点，1≤N'≤N。

研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数（又称"流量"或"通道数"）最少的方案。这里所说的并行传输，是指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行（具有这种能力的互连网不属于现在的讨论范围）。显然对不同的网络，适用的广播与选播算法也不同。下面举几个具体实例。2003.3.130计算机系统结构7.5.1广播算法(1)单级立方体网络广播算法算法：按任意顺序使用Cube0～Cuben-1各一次，每一步都从当前拥有数据的所有结点同时发往等量的无数据结点，也就是将网络中拥有数据的结点数加倍。如图6.9所示（图中实线箭头表示一个数据的一次实际传送，虚线指出上一步已有数据的结点）。这种算法的时间和流量是由结点数N决定的常量。时间流量

2003.3.131计算机系统结构

2301

6745单级立方体网络广播算法实例从节点0开始，顺序是cube0－>cube2

042615370000000000000010111110010110011010100101101002003.3.132计算机系统结构单级立方体网络广播算法实例2003.3.133计算机系统结构7.5.2选播算法选播算法的设计目标有3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案。选播时间最少算法是通过单播时间最少算法裁剪而成（教材P426图7.36(a)→(b)）。选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树”（教材P426图7.36(c)）。

实现第3种目标的一种重要算法是贪婪算法（教材P426图7.36(b)）。不论对何种网络，贪婪算法总是重复使用一个固定的操作规则：从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步，如此循环，直至传遍所有需要数据的结点。如果最后发现某个通道（即一次数据发送操作）不在通往给定目标结点的路径上，则应将其删去。2003.3.134计算机系统结构(1)单级网格网（Mash网）贪婪算法算法：以教材P426图7.36为例，小图(a)指出总共有1个源结点S和5个目的结点。小图(b)指出从S出发，首先应向右邻结点发送数据，因为S的左方只有1个目的结点、上方有3个目的结点、右方有４个目的结点；第二步从这２个拥有数据的结点出发，可以再向右发送（有3个目的结点），也可以改向上发送（也有3个目的结点），……。只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的。2003.3.135计算机系统结构(2)单级立方体网络贪婪算法算法：以教材P426图7.37为例。小图(a)指出广播算法的时间是4，流量是15。Cube0～Cuben-1的使用顺序对广播算法的时间和流量没有影响，但对小图(b)的选播算法的时间