《计算机互连网络PPT课件》由会员分享，可在线阅读，更多相关《计算机互连网络PPT课件（38页珍藏版）》请在金锄头文库上搜索。
1、 本章内容：介绍用于多机并行计算的各种网络，它们统称为互连网络，缩写符号是ICN（Interconnection Network）。 互连网络是一种由开关元件按照一定的拓朴结构和控制方式 构成的网络，用来实现多处理机、多计算机之间或多个功能 部件之间的连接，是多处理机、多计算机系统的核心。 互连网络的设计目标： 通过互连网络连接的多个部件能实现灵活的连接变换、能提 供部件间的通信的最大并行性。第七章第七章 互连网络互连网络(P394)2003.3.117.1 目的与作用(1) 当前提高计算速度的主要措施，一是改进器件，二是多处理单元并行计算。ICN是供多处理单元传输数据的高速通路，对并行计算时
2、间影响很大。(2) ICN与处理单元的连接模型(3) ICN的主要操作：置换(NN)，广播(1 N)，选播(1 N)。2003.3.12(1)网络规模 (2)一般说来，网络用图来表示。其结点数称为网络规模。(3)(2) 结点度(4)与结点相连接的边(即链路或通道)的数目称为结点度。在单向通道的情况下，进入结点的通道数叫做入度，而从结点出来的通道数则称为出度。结点度应尽可能地小并保持恒定。(5)(3) 距离(6)两结点之间相连的最少边数。(7)(4) 网络直径(8)网络中任意两个结点间最短路径长度的最大值称为网络直径。网络直径应当尽可能地小。(9)(5) 等分宽度(10)当某一网络被切成相等的两
3、半时，沿切口的最小边数(通道)称为通道等分宽度。(11)(6)路由(12)在网络通信中对路径的选择与指定。通常见到的处理单元之间的数据路由功能有移数、混洗、交换、广播(一对全体)、选播(多对多)等。基本概念基本概念2003.3.13(1)通用网/专用网通用网（原用于计算机之间交换信息的普通网络），专用网（专用于并行计算系统各处理单元之间并行交换数据的特殊网络）；通用网包括以太网、电话拨号网等，专用网在后面介绍。(2)串行网/并行网串行网（多个结点的发送操作在时间上不能重叠），并行网（多个结点的发送操作在时间上可以重叠）；计算机局域网LAN（如以太网、令牌环网）多属串行网，计算机广域网是异步并行
4、网。(3)同步网/异步网（并行网再细分）同步网（多个结点必须朝同一方向、以同一距离、同时开始发送），异步网（多个结点可以朝不同方向、以不同距离、不同时开始发送，可能冲突）；(4)静态网/动态网（P402和P408）静态网（结点之间有固定连接），动态网（结点之间的连接关系不固定，须通过开关导向或地址识别来确定当前的目的结点）；互连网络的分类2003.3.14静态网络使用直接链路，它一旦构成后就固定不变。静态网络（P402）在N很小的情况下，线性阵列相当经济和合理的。由于直径随N线性增大，因此当N比较大时，就不应使用了。下面介绍几种常用的静态网络。 1.线性阵列2003.3.15环可以单向工作，也
5、可以双向工作。它是对称的，结点度是常数2。双向环的直径为N/2，单向环的直径是N。 2. 环与带弦环2003.3.163. 循环移数网络2003.3.174. 树形和星形2003.3.185. 胖树形 2003.3.196. 网格形和环网形2003.3.1107. 超立方体2003.3.111为了达到多用或通用的目的，我们需要采用动态连接网络，它能根据程序要求实现所需的通信模式动态连接特性。 按照价格和性能增加的顺序，动态连接网络的排队次序为总线系统、多级互连网络(MIN)和交叉开关网络。动态互接网络总线系统价格较低，存在总线争用。1.总线系统2003.3.112交叉开关网络是单级网络，它由交
6、叉点上的一元开关构成。通常，这类交叉开关网络需要使用nm个交叉点开关。正方形交叉开关网络(nm)可以无阻塞地实现n!种置换。每个周期可以实现n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。 对小型系统来说性能价格比较高。 但是单级交叉开关网络一旦构成后将不能扩充。2.交叉开关网络2003.3.113总线的造价最低，但其缺点是可用的带宽较窄，容易产生故障。由于交叉开关的硬件复杂性以n2上升，所以其造价最为昂贵。但是，交叉开关的带宽和路由性能最好。如果网络的规模较小，它是一种理想的倍选择。 多级网络则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网
7、络的级数而上升。另外，由于增加了连线和开关复杂性，价格也是一种限制因素。总线、多级网络、交叉开关的对比2003.3.114特点：成本低，并行性差。(1) 拓扑结构(硬件，P402-P407)：直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。(2) 传输协议(使用规则，软件，P427-P435)：碰撞争用，令牌协议，剑桥环。(3) 主要参数(P399)：直径，中剖宽度，结点的度，最长边。 示例：(4) 典型代表：以太网，令牌网（环或直线）。7.2 通用网2003.3.115 特点：并行度高，造价昂贵。(1) 互连函数 N个输入到N个输出的一种对应状态可以用一个映射函数表示，称为
8、互连函数。它是处理单元集合对于自身的双射映射，所以又称为“置换”，或者“循环”。 互连函数有多种表示方式，如下例所示：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 专用网2003.3.116定义：单级ICN只使用一级开关，如下图所示。 开关的每种接通组合方式可用一个互连函数表示。f( j入 ) = j出，0jN-1在互连函数中，记：N 结点数n = log2N 维数j= Xn-
9、1X0 结点编号的二进制形式，位数为n。互连函数族的组成必须使网络成为连通图连通图。(2) 单级ICN2003.3.117 该网络由立方体函数定义，立方体函数族有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的单级立方体网络拓扑形状如右图所示。 最坏情况下的传输需对输入结点编号的全部n位取反。所以单级立方体网络的直径是n。 立方体函数性质：结合律、交换律以
10、及自反律（Cubei重复使用2次的结果与原始自变量相同）。单级立方体网（Cube网，P396第1行 / P405第4行）2003.3.118 该网络由混洗函数（shuffle）与交换函数（exchange即Cube0）定义，或者说它的互连函数族只有这两个成员。 混洗函数混洗函数定义： 2j mod（N-1），当j cube2 0 4 2 6 1 5 3 70000000000000010111110010110011010100101101002003.3.132单级立方体网络广播算法实例2003.3.1337.5.2 选播算法 选播算法的设计目标有3种：时间最少、流量最少、在时间最少的多个方
11、案中选取流量最少方案。 选播时间最少算法是通过单播时间最少算法裁剪而成（教材P426图7.36(a)(b)）。 选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树”（教材P426图7.36(c)）。 实现第3种目标的一种重要算法是贪婪算法（教材P426图7.36(b)）。 不论对何种网络，贪婪算法总是重复使用一个固定的操作规则：从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步，如此循环，直至传遍所有需要数据的结点。如果最后发现某个通道（即一次数据发送操作）不在通往给定目标结点的路径上，则应将其删去。2003.3.134(
12、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的使用顺序对广播算法的时
13、间和流量没有影响，但对小图(b)的选播算法的时间和流量有影响。 先看一个简单的例子（下图）：已知N=4，维数n=2，源结点是0，目的结点是1和3。 源结点编号的二进制形式00在bit0位与两个目的结点的二进制形式01、11都不相同，而在bit1位仅与一个目的结点的二进制形式不同，所以应该先传bit0方向、再传bit1方向，如右图(a)所示，这时流量=2；如果先传bit1方向、再传bit0方向，如右图(b)所示，则流量=3。2003.3.136 再看教材P426图7.37(b)的例子。源结点编号的二进制形式0101在Cube0 Cube3位分别与5、5、4、5个目的结点的二进制形式不同，所以Cu
14、be2方向应该最后发送，其它3个方向的发送先后顺序则没有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=10。2003.3.137本章小结本章小结(1) 通用网的拓扑结构，传输协议，主要参数，典型代表；(2) 互连函数（置换，循环）的4种表示方式；(3) 单级立方体网（Cube网）的定义，拓扑形状，直径，性质，互连函数族的组成；(4) 单级混洗-交换网的定义，拓扑形状，直径，性质，互连函数族的组成；(5) 单级加减2i网（PM2I网，移数网）的定义，拓扑形状，直径，性质，互连函数族的组成；(6) 二元交换开关，控制信号的3种分配方式；(7) 多级混洗交换网络的结构，寻径算法（路由算法）。习题：P446，题3，题10，题26(1)(2)，题27(3)。2003.3.138
