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