第6章互连网络.ppt

第6章 互连网络,6.1 互连网络的基本概念6.2 静态互连网络6.3 动态互连网络 6.4 消息传送与控制,6.1 互连网络的基本概念,6.1.1 互连网络的功能与特征6.1.2 互连函数,6.1.1 互连网络的功能与特征,1.网络功能 互连网络是一种由开关元件按一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多处理机或多功能部件之间的相互连接。它通过硬件线路，实现设备之间的连接；通过开关选择，构成一对一或者一对多的信息通路。如果再配以软件，还可实现数据格式的定义、转换、打包、帧识别、发送与接收控制以及误码检测等功能。这里主要从硬件的角度讨论互连网络的功能与特征，如图6.1所示。,图6.1 互连网络示意图,概括起来，互连网络的主要功能有以下两点：连接各个结点，构成信息通路，传送数据或者控制命令；通过路径选择，实现有目的的信息交换，其中包括一到一和一到多的选择与交换。随着互联网的发展，越来越多的并行计算机系统直接使用台式计算机作为结点机，通过互联网连接，构成并行计算机系统，这也使互连网络由专用型发展成为通用型。,2.主要性能 主要是指网络规模、连接度、结点距离、网络直径、带宽、可靠性和成本。（1）网络规模：是指网络中的结点数，它体现网络所能连接的部件数，随着设备的增加而扩大。（2）连接度：也称为结点度，是指与该结点连接的边数，也就是直接连接到该结点的其它结点数，常用d表示。如果一个结点直接连接的其它结点越多，则该网络的连接度也就越高。（3）结点距离：结点距离是从一个结点到另一结点所经过的最少边数。（4）网络直径：网络直径是指网络中任意两个结点之间的最大距离，常用D表示。从数据传送的角度来看，网络直径越小越好。（5）等分宽度：分为通道等分宽度和线等分宽度。把网络切成相等的两半，沿切口的最小边（通道）数称为通道等分宽度，可用k表示；若用w表示通道宽度（用位表示），则B=kw称为线等分宽度。,（6）结点间线长：是指两结点之间的线路长度，它影响信号传输中的延时、扭曲和需要的功率。（7）对称性：从任何一个结点来看，若网络的拓扑结构都一样，则称为对称网络。对于这种网络，容易设计和编程。（8）数据寻径功能：表示互连网络把数据从网络的一端传送到另一端的方式和能力，分为静态和动态两种。静态数据寻径网络是指其结构不能用程序改变；而动态数据寻径网络的结构可用程序改变。不同的网络结构有着不同的数据寻径功能，常见的有一到一、一到多(广播)、散射、汇合/聚集、归约(多到一)、循环移位、扫描和全交换等。3.主要参数（1）带宽 是指网络传送信息的速率，常用Mbps或MBps表示，又分为聚集带宽和等分带宽。所谓聚集带宽是在网络中，从一半结点到另一半结点，每秒钟传送信息的最大位数或字节数.。而等分带宽是指每秒钟从最小线等分宽度(线)上通过信息的最大位数或字节数。,例如HPS是一个对称式网络，包含512个结点，每个端口的带宽为40MBps，可计算出聚集带宽为512/240MBps=10GBps。若用r表示线等分宽度中每条线上传送信息的速率，则等分带宽可表示为P=kwr。（2）传输时间：是指信息通过网络所用的时间，等于信息长度除以带宽。（3）飞行时间：是指消息的第一位数据通过网络到达接收端所用的时间。（4）传输延时：传输延时等于飞行时间与传输时间之和，是消息通过互连网络的时间，但不包括网络两端硬件设备发送和接收的时间。（5）总延时：包括上述传输延时和网络两端的发送与接收时间。（6）误码率：是传输信息时出现错误的概率，等于错误码的位数除以总码长。显然，误码率越低越好。（7）成本：构建互连网络所花的费用。在保证功能要求的基础上，越低越好。,4.互连网络设计要素 在设计互连网络时，所考虑的主要因素有以下4个方面。（1）传送方式 传送方式分为同步和异步两种。所谓同步方式，是在数据传送的过程中采用统一的时钟信号。异步方式则不需要统一的时钟信号在各处理机（或单元）之间进行同步，各处理机（或单元）根据自身需要相互建立动态连接。（2）控制策略 是控制互连开关构成信息通路的方式，可分为集中控制和分散控制两种。所谓集中控制，是由统一的控制器对各个互连开关实施控制；而分散控制，是由各个开关自身实施控制。一般SIMD计算机采用的是集中控制和同步传送方式。（3）交换方式 是指数据传送管理方式，分为线路交换和分组交换。线路交换是在传送过程中，在源/目标结点间建立固定的物理通路，适合于成批数据传送。分组交换是对数据进行分组，分别送入互连网络，各分组可通过不同的路由到达目标结点，适合于短数据报文传送。SIMD计算机一般采用线路交换，MIMD多处理机多采用分组交换方式。,（4）拓扑结构 是指互连网络中各结点之间的连接关系，可分为静态拓扑和动态拓扑。静态拓扑是在网络运行中其结构不能改变；而在动态拓扑结构中设有有源开关，在网络运行中可借助于控制信号对连接通路重新组合。一维静态拓扑有线性结构，二维有圆型、星型、树状和网格型等结构，三维及以上有超立方体结构等。在动态拓扑中主要分为单级循环网络和各种多级互连网络，其连接形式与互连函数密切相关。5.互连函数 为反映互连网络的连接特征，常用函数的形式进行描述，称为互连函数，它反映的是从输入端到输出端的映象关系。设用x表示具有N个输入端的网络输入序号，则输出端的序号用函数f(x)表示。设x是一个n位的二进制数，即x=bn-1bn-2b1b0，其中n=log2N。则f(x)因函数的不同，而有不同的表达式，例如：交换互连函数f(x)=f(bn-1bn-2b1b0)=bn-1bn-2b1b0 全混洗互连函数f(x)=f(bn-1bn-2b1b0)=bn-2b1b0bn-1,6.1.2 互连函数,1.恒等互连函数也称为直通互连函数，是指输出端与相同序号的输入端对应连接。其表达式为：I(x)=I(bn-1bn-2b1b0)=bn-1bn-2b1b0其示意如图6.2所示，左边表示输入端，右边表示输出端。,图6.2 恒等互连示意图,图6.3 立方体结构图,图6.4 Cube交换互连示意图,按照Cube函数的连接示意如图6.4所示。,【例6.1】设有64个处理器，其编号依次是0，1，2，63，按照互连函数Exchange()4连接时，第21号处理器与哪一个处理器连接。解：设待求处理器的序号为i，表示为Pi，则：Pi=Exchange(010101)4=010101=000101,3.全混洗互连函数 全混洗互连函数(Shuffle)也称为均匀混洗互连函数，它实现输入端与地址中最高位循环移位到最低位的输出端连接：Shuffle(bn-1bn-2b1b0)=bn-2b1b0bn-1 其示意如图6.5所示，犹如把一沓扑克牌对分后均匀洗牌的结果，因此称为全混洗互连函数。其中，N=8。,图6.5 全混洗互连示意,此外，还有逆全混洗和扩展全混洗互连函数。其中逆全混洗互连函数是把地址中的最低位循环移位到最高位：Shuffle(bn-1bn-2b1b0)-1=b0bn-1bn-2b2b1 扩展全混洗是把地址中的任一位循环移位到最低位：Shuffle(bn-1bn-2bkb1b0)k=bn-1bn-2b1b0bk,4.PM2I互连函数 PM2I互连函数是“加减2i”单级互连函数的简称，也称为循环移数函数，它实现输入端与地址2i的输出端连接：PM2I+i(j)=(j+2 i)mod N PM2I-i(j)=(j-2 i)mod N式中0in-1，0jN-1，n=log2N，N是结点数。显然，这种互连函数共有2n种。图6.6所示是N=8时，按函数PM2I+0、PM2I-1和PM2I2构成网络的连接形式。,图6.6 PM2I互连示意图,图6.7 PM2I互连特性,互连特性如图6.7所示，比如结点0可以与结点1，2，4，6，7直接连接；而在图6.3所示的立方体互连中，每一个结点只能与相邻的3个结点连接。,但是从图6.6中不难看出，PM2I+(n-1)=PM2I-(n-1)。因此，按照函数PM2I只能构成2n-1种互连函数。网络的最大距离为n/2=log2N/2，这里 表示向上取整。,5.蝶形互连函数 蝶形互连函数实现输入端与地址中最高位与最低位交换的输出端连接：Butterfly(bn-1bn-2b1b0)=b0bn-2b1bn-1 按照蝶形互连函数的连接示意如图6.8所示，犹如一只蝴蝶，中线对称，因此称为蝶形互连函数。其中，N=8。,图6.8 蝶形互连示意图,6.混洗交换互连函数混洗交换互连函数实际上是由全混洗互连函数与交换互连函数构成的复合函数：Exchangeshuffle(bn-1bn-2b1b0)=Exchangebn-2b1b0b n-1=bn-2b1b0bn-1按照混洗交换互连函数的连接示意如图6.9所示，其中，N=8。,图6.9 混洗交换互连示意图,【例6.3】设有128个处理器，其编号依次是0，1，2，127，当复合互连函数为 Shuffle(Butterfly(PM2I+4)时，第27号处理器与哪一个处理器连接。解：设待求处理器的序号为i，表示为Pi，则：Pi=Shuffle(Butterfly(PM2I+4(00011011)=Shuffle(Butterfly(00011011+24)=Shuffle(Butterfly(00101011)=Shuffle(10101010)=01010101,6.2 静态互连网络,6.2.1 静态互连网络结构6.2.2 静态互连网络特性,静态互连网络(Static network)是在点到点之间使用直接链路，设计成功，固定不变，常用来实现集中式系统中子系统之间或分布式系统中多个计算结点之间的固定连接。这种网络较适合于通信模式可以预测或者可用静态网络连接的计算机系统中，且有多种形式，比如一维线性阵列，二维环形、星形、树形和网络形等，三维立方体以及三维以上的超立方体等。下面简要介绍常用静态互连网络，若无专门说明，N=2n。,6.2.1 静态互连网络结构,1.线性阵列结构 线性阵列是一种一维网络结构，其中N个结点用N-1条链路连接，构成一行，如图6.10（a）所示。以d表示连接度，则内部结点d=2，两端结点d=1。网络直径D=N-1，等分宽度为1，是一种非对称结构，N很大时通信效率低；N很小时，比如N=2，简单方便。2.环与带弦环结构 线性阵列首尾连接，如图6.10(b)所示，是一种对称性的结构，可单向/双向工作。连接度d=2，其中双向环的直径D=N/2，单向环的直径D=N。对于环中的结点，可以增加其连接度，比如3或者4，就构成如图6.10(c)和(d)所示的连接度为3和4的带弦环。增加结点之间的链路，即可增加其连接度。但是，随着连接度的增加，网络直径减小。其中图6.10(c)的网络直径D=5，图6.10(d)的网络直径D=3。在极端的情况下构成图6.10(f)所示的全连接结构，连接度d=15，网络直径最短，D=1。,图6.10 静态网络结构,3.循环移数网络结构如图6.10(e)所示，它是将环上每一个结点与其距离为2的整次幂的结点连接起来。若网络规模N=2n，则网络连接度d=2n-1，网络直径D=n/2。与连接度为4的带弦环相比，连接度提高，网络直径减小；而复杂性，又比全连接简单的多。当N=16时，连接度为7，网络直径D=2。,图6.11 树状网络结构,4.树状网络结构 如图6.11所示象一棵倒立的树。其中最顶上的是根结点，底层结点为叶，中间结点称为支或者干。图6.11(a)是一个完全的二叉树结构，有31个结点，分成5层。若以h表示层，则在完全二叉树中结点数N=2h-1，连接度d=3，直径D=2(h-1)。最大特点是连接度是一个常数，易于扩展。图6.11(b)是一种胖树结构。胖树结构在上层增加了通信链路，使通往上层支干结点和根结点的线路变胖，因此可解决二叉树中的瓶颈问题。,5.星型网络结构 如图6.12所示，各外层结点连接到中心结点上，可看作一种2层树形结构，连接度很高，d=N-1；但直径小，仅等于常数2。其缺点是中心结点太忙，一旦出现故障，整个网络瘫痪。,图6.12 星型网络结构,图6.13 网格型与环网型结构,6.网格型与环网型结构 网格的结构有多种形式，其中图6.13(a)是一个典型的44二维网格形式。若以k表示维数，r表示行数或列数，当网络规模为N=rk时，内部结点的连接度d=2k，网络直径D=k(r-1)。对于二维网格，内部结点的连接度是4，边界和角结点的连接度分别是3和2。,若把边界和角结点如图6.13(b)所示回绕起来，构成Illiac网格。这种结构使用在Illiac-型计算机中，因此称为Illiac网络。在一个N=rr的Illiac网络中，结点连接度为4，网络直径为(r-1)，仅是纯二维网络的一半。,图6.13 网格型与环网型结构,图6.13 网格型与环网型结构,图6.13(c)所示的环网形结构是在每一行或者每一列构成一个环，因此也称为环型网络。一般来说，对于N=rr的二维环网型结构，结点连接度d=4，网络直径D=2r/2。这种环型网络是一种对称型的拓扑结构。,7.脉动阵列结构 脉动阵列网格如图6.14所示，主要是为矩阵乘法运算而设计的。它可沿多个方向同步传送数据流，实现多维流水线操作，内部结点的连接度为6。脉动阵列结构一般与算法紧密相关，在信号/图像处理中有着特殊的用途，但是适用性有限。,图6.14 脉动阵列结构,8.超立方体网络结构 超立方体(Hypercube)是一种二元n-立方体结构，其中二元表示沿每一个方向有2个结点，n表示维数。维数n与立方体中的结点数N的关系是N=2n。图6.15(a)是由8个结点构成的3-立方体，沿着每一个方向有2个结点，总的结点数N=8=23，因此称为3-立方体。图6.15(b)是由2个3-立方体构成的4-立方体结构，沿每一方向结点数为2，总的结点数为16=24。这种二元n-立方体网络结构中，每一个结点的连接度为n，直径也是n。,图6.15 超立方体结构,9.带环立方体网络结构 是把立方体中每一个结点用一个包含多个结点的环代替。如图6.16 所示，是把3-立方体中的顶角结点换成包含3个结点的环，而构成的带环立方体结构，简称3-CCC(Cube Connected Cycles)。若要组成带环k-立方体，只需将k-立方体的每一个顶角结点用k个结点组成的环代替，这样就构成一个有N=k2k个结点的带环k-立方体。,图6.16 带环3-立方体,在构成带环立方体网络时，环中的结点数k一般与立方体的维数相等。,10.k元n-立方体网络结构 在k元n-立方体网络中，k表示基数，即每一方向上的结点数，n表示立方体的维数。这样，网络中的结点数N=kn(n=logkN)。图6.17是一种4元3-立方体的网络结构(隐藏部分的结点没有画出)，每个方向上有一条双向通信链路。实际上，环型、网格型、环网型、二元n维立方体(超立方体)以及Omega网络都是k元n-立方体（k-ary n-cube network）系列的拓扑同构体。按照习惯，低维k元n-立方体称为环网，高维二元n-立方体称为超立方体。,图6.17 4元3-立方体网络结构,6.2.2 静态互连网络特性,各种阵列机或大规模并行处理机系统中的静态互连网络已经很多，而且各有特色。概括起来如表6.1所示。其中d表示连接度，D表示网络直径，l表示链路数，B表示等分带宽。,说明：表示取整,6.3 动态互连网络,6.3.1 总线互连方式6.3.2 交叉开关互连方式6.3.3 多级网络互连方式,动态互连网络是用开关或裁决器提供动态连接特性，在运行过程中由程序来确定具体的连接方式，常见的动态互连网络有总线互连方式、交叉开关互连方式、多级互连方式及组合互连方式等。,6.3.1 总线互连方式,总线连接方式是多机互连的一种最简单的方式。多个处理机、存储器模块及I/O部件通过各自的接口部件连接在一条共用总线上；或是多个由CPU、局部存储器和I/O部件组成的计算机模块通过各自的接口部件与一条总线连接。1.总线结构多处理机系统 总线结构多处理机系统如图6.18所示，构成系统总线的各种线路分布在底板上，通过插槽与各处理模块连接。系统总线一般受某一主CPU模块或总线裁决器控制。当某一模块需要通信时首先向主CPU或总线裁决器发总线请求信号；在获取总线后发送地址，以确定从设备；然后与从设备进行一次通信，通信完后，释放总线。,图6.18 总线结构多处理机系统,在各处理模块内部设有本地或者局部总线，用来连接模块内部的部件或者器件。设在CPU模块中的局部总线称为本地总线，设在存储器模块中的称为存储器总线；设在I/O模块中的称为I/O总线。各模块之间使用统一的总线标准，比如PCI、VME、Multibus、Sbus、Microchanne、IEEE Futurebus等。,2.多层总线结构多处理机系统 多层总线结构如图6.19所示，各处理机采用底层总线实现互连，构成一个机群，底层总线也称为机群总线。在各机群内部，CC表示机群缓冲存储器，P表示处理器。在上层，各机群通过外部总线实现互连，构成大的机群系统，这种外部总线也称为机群间总线。,图6.19 多层总线结构多处理机系统,另外，各机群通过上层总线与共享存储器连接，通过共享存储器实现数据交换或者通信；亦可与大型外部设备连接，共享系统中的大型外部设备。在构成多层总线结构的多处理机系统时，因为各机群使用的总线标准不一定相同，因此需要使用网桥实现标准转换，并进行地址分配和连接。,6.3.2 交叉开关互连方式,1.单级交叉开关互连网络 是通过开关把多个处理机、存储器模块以及I/O设备连接起来，形成一种网络结构。它引入空间重复因素，可为每一个端口提供更高的带宽。一般由一组二维开关阵列组成，如图6.20所示，通过开关把处理机Pi与存储器Mi连接起来。控制开关的通与断可实现某两个结点的连接。总线的条数等于所有处理机数p与存储器模块数m之和。只要mp，必然使每一个处理,图6.20 交叉开关互连网络,机都能有一套总线与某一存储器模块连接，可提高系统的带宽。为了处理多个处理机同时使用某 一存储器而引起的冲突，在纵横交 叉开关互连网络中需要设置裁决部件。若p个处理机还要与i个I/O设备 连接，则阵列机中总线的条数等于p+m+i。只有mp+i时，才能实现无阻塞连接。,2.多级交叉开关互连网络图6.21所示是由4个44交叉开关阵列构成的二级1616交叉开关互连网络。显然，如果使用单级交叉开关实现1616的互连网络，则需要256个交叉开关。采用二级网络结构，则仅需要128个交叉开关，使硬件节省一半，且结构简单。但是，延时将随着级数的增加而增加。,图6.21 二级1616交叉开关互连网络,6.3.3 多级网络互连方式,多级互连网络MIN(Multistage interconnection network)是把多个单级互连网络通过交换开关或交叉开关串连起来而构成的网络，可通过改变开关状态实现不同的连接，以满足系统需要。常见的有多级立方体互连网络、多级混洗交换网络（Omega网络）、多级PM2I网络、多级BENES可重排网络及多级CLOS网络等。构成多级互连网络三要素，包括交换开关、拓扑结构和控制方式。（1）交换开关：是构成多级互连网络的基本单元，有两个输入端和两个输出端，又分为二功能和四功能两种。二功能有直通和交换，四功能是增加了上播和下播，如图6.22所示。,图6.22 交换开关的四种功能,（2）拓扑结构：拓扑结构是指各级之间输入端和输出端的连接规则或模式。按照一定的规则或模式可将各种单级互连网络进行组合，从而构成具有不同连接特性的多级互连网络。（3）控制方式：根据互联网络的结构可有三种控制方式。级控：同一级的所有交换开关受同一信号控制，对于一个n级网络需要n个控制信号。单元控制：每个开关有一个单独的控制信号。对于n级网络，其输入与输出端数N=2n，故每级有N/2个开关，共需nN/2个控制信号。控制复杂，但使用灵活。部分级控：对同一级开关分组，在不同级使用不同数量的控制信号。比如第0级用1个控制信号，第1级用2个控制信号，第2级用3个控制信号，即第i级用i+1个控制信号，其中0in-1，n为级数。,如图6.23是用ab开关模块和不同的级间连接模式（ISC）构成的多级互连网络示意图。不同的多级互连网络的主要区别表现在上述三个方面。其中开关可以根据需要选用22、44、46、88、1616、6464等；级间连接模式可选择Exchange、Cube、Shuffle、PM2I、Butterfly以及这些函数的逆模式等；控制方式可以是级控、部分级控和单元控制。三要素确定以后，就可得到所需要的网络结构。,图6.23 多级互连网络示意图,1.多立方体网络 是将Cube0、Cube1和Cube2三种函数构成的单级网络串接起来，如图6.24所示，是一种STARAN网络。使用二功能交换开关，即直通和交换，分级控制，可实现交换网络功能。采用不同方式控制，可实现不同连通功能。即当第i级控制信号为0时，开关直通；若控制信号为1，则开关交换，实现Cubei的功能。若采用部分级控，则实现移数网络功能。,图6.24 三级立方体互连网络,设N表示处理单元数，一个NN的STARAN网络的级数n=log2N，每级有N/2个开关，全部开关数为nN/2。若N=8，则可如图6.24所示，可分为三级，需要三级控制信号。级控信号的组合与所实现的功能如表6.2所示。,2.多级混洗交换网络 又称为OMEGA网络，由n级相同的网络组成，各级包含一个全混洗拓扑和一列四功能的交换开关，采用单元控制方式。一个用于8个处理单元的多级混洗交换网络如图6.25所示。对于一个N=2n个输入输出端的OMEGA网络，共需要n级22开关，每一级包含N/2个采用单元控制的四功能交换开关。,图6.25 三级混洗交换网络,3.多级PM2I互连网络 也称为数据交换网络，可包含n级单元连接，每一级都是把前后两列各N=2n个单元按照PM2I拓扑结构连接起来，如图6.26所示，其中n=log28=3，即三级PM2I互连网络。对于第i级(0in-1),每一个输入端j都有三条输出线与之连接，即j、(j+2i)mod N和(j-2i)mod N，也就是通过交换开关选择直通、上播和下播。三级PM2I网络中第0级完成的是PM2I0的函数功能，第1级完成的是PM2I1的函数功能，第2级完成的是PM2I2的函数功能。可以看出，从每一个输入到输出都有三条线路，为信息传送提供了冗余通路。例如，从输入端7到输出端2的路径有：733273127712有利于克服线路阻塞，提高通信的可靠性。,图6.26 三级PM2I互连网络,4.基准网络 如图6.27所示是一种N=8的互连网络，与三级多立方体网络的逆网络相似，只是在第1级的级间互连不同。基准网络的级间互连从输入到输出依次是直通、逆均匀混洗、子逆均匀混洗和直通置换。开关采用二功能交换开关，单元控制。,图6.27 N=8的基准网络,图6.28 N=16的基准网络,明显特征是可扩展性，图6.28是N=16的基准网络。这种网络常用于多级互连网络的研究，把基准网络作为中间介质，模拟一种网络的拓扑结构和功能。,5.多级CLOS网络（1）三级CLOS网络 是一种非阻塞网络，输入输出端口数相同，都是nr，其组成如图6.29所示。输入级有r个交叉开关，每个交叉开关均为nm；中间级有m个交叉开关，每个交叉开关均为 rr；输出级有r个交叉开关，每个开关均为mn。,图6.29 三级CLOS网络,图6.30 N(3,2,2)CLOS交叉开关网络,由于输入端和输出端仅有4个，因此若用单级44的交叉开关来实现，共需44=16个交叉点，似乎要简单一些。但是，对于图6.29来说，若设C表示多级CLOS网络中总的交叉点数，则：C=r(nm)+m(rr)+r(mn)=mr(2n+r)如果输入输出端数很大时，选用多级CLOS网络既可实现无阻塞连接，而且工程设计容易，成本低。,这种多级CLOS网络可用三个参数(m，n，r)来表示。当m2n-1时，多级CLOS网络N(m，n，r)是一个非阻塞网络。例如N(3，2，2)的网络结构如图6.30所示，其中每一级有12个交叉点，共计36个交叉点。,（2）可重排三级CLOS网络当m=n=r时，可构成三级可重排CLOS网络，通过重排，可以消除信息传送中所遇到的阻塞。为简单起见，以m=n=r=2为例来说明可重排网络的原理。如图6.31所示，,若要求一个网络可以重排，该网络至少要有两个以上的路径来满足一对结点的连接要求，即数据寻径算法不是唯一的。,图6.31 可重排三级CLOS网络,6.多级BENES可重排网络 BENES网络是由基准网络和其逆网络连接而成的可重排互连网络。如图6.32所示，是一种有8个处理单元的可重排非阻塞网络，满足由输入到输出的所有置换，即从07的所有排列，共8！种。网络开关的级数为2log2N-1，每一级有N/2个22的二功能开关，采用单元控制。图中虚线框中的两级开关在功能上一样，可合并成一级。,图6.32 多级BENES可重排网络,7.蝶式互连网络蝶式互连网络是用蝶式网络结构把多级交叉开关连接起来而构成的网络。如图6.33所示，是由16个88交叉开关构成的6464的二级蝶式网络，级间采用8路混洗方式连接。,显著特点是容易级连，若把图6.33所示的网络看成6464的开关，再用蝶式网络结构连接起来，可构成更大的蝶式互连网络。,图6.33 蝶式互连网络,8.网络 也是采用ab交叉开关，级间用混洗网络连接，也称为榕树形式。其结构如图6.34所示，,能实现a个输入中的任意一个可与b个输出中的任意一个连接。用n级ab交叉开关可组成anbn互连网络。图中显示的是一个4232的网络，适合于输入端数和输出端数不相等及通信不规则的场合。,图6.34 4232的网络,6.4 消息传送与控制,6.4.1 消息寻径方式6.4.2 虚拟通道与死锁6.4.3 流控制策略,6.4.1 消息寻径方式,其中R称为导径信息，S是顺序号，D表示数据片。包的大小受寻径方式、网络直径和通道带宽等多种因素的影响。数据片可选择8位，典型包长为64位512位，顺序号可占12个数据片，有的格式中还附带校验码。1.消息的格式 消息（Message）是多处理机信息传送的一种组织形式，如图6.35所示，由若干个数据包组成，而包是消息传送中的最小单位，由专门的数据位来说明其属性，包括头部标志、顺序号、目的地址和数据长度等，其余是数据片。,图6.35 消息中的数据格式,2.寻径方式 消息寻径可分为两大类型，即线路交换和包交换。其中包交换又分为存储转发、虚拟直通寻径和虫孔寻径等。（1）线路交换（Circuit switch）也称为线路开关寻径方式，是通过源/目结点之间的线路进行消息传送，如图6.36所示。这种方式需要在信息传送之前进行线路连接，因此在结点数较少、网络直径较小的情况下比较有效。传输时延可表示如下：,T=(Lt/B)D+L/B 其中Lt是为建立路径连接所需要的小信息包长度，L是信息包长度，D是经过的结点数，B是网络带宽。但有时线路接通时间长，可能是一个缺点。,图6.36 线路开关寻径方式,（3）虚拟直通（Virtual cut through）虚拟直通是不必等到整个消息（包）全部接收完成后再作下一步的路由选择，只要接收到头部导径信息之后即可进行下一结点的判断与连接。传输时延表示如下：T=(Lh/B)D+L/B=(LhD+L)/B 其中Lh是头部导径信息的长度。一般来说LLh，所以公式可近似为TL/B。也就是说，时延与结点数近似于无关。（4）虫孔寻径（Wormhole）也称为虫蚀寻径，是把包分成更小的数据片，称为Flit。而在每个结点中设有硬件寻径器及片缓冲区，Flit以流水线的方式顺序，不间断地从源结点传送到目标结点，象一条小虫在小孔中蠕动，因此称为虫孔寻径。由于只有头部Flit知道包传送到何处，因此允许不同包交叉传送，但不允许不同包中的Flit混在一起。,图6.38所示是小孔寻径示意图，其中L表示包长，Lf表示数据片Flit长。B是通道带宽，D是结点距离。这样，传输时延如下：T=Lf/BD+L/B=(LfD+L)/B 显然，当LLf时，TL/B，与D无关。第一台采用虫孔寻径方式的计算机是Ametek 2010（二维互连网络）。以后Intel的Paragon多级系统(二维网络)、MIT的J多级系统(三维网络)以及我国的曙光1000采用的都是虫孔寻径方式。,图6.38 虫孔寻径方式,6.4.2 虚拟通道与死锁,1.虚拟通道 虚拟通道是指两个结点之间的逻辑连链，由源结点的片缓冲区、结点间的物理通道及目标结点的片缓冲区组成。如图6.39所示，4条虚拟通道共享一条物理通道，且源/目结点各有4个片缓冲区。在使用时，只有物理通道分配给这一对缓冲区时，源/目缓冲区之间才能传送数据。物理通道由所有虚拟通道分时共享。,图6.39 虚拟通道的组成示意图,2.死锁（1）死锁原因如图6.40(a)所示，网络中各互连结点的缓冲区都有数据，这样若每个结点都不放弃自身缓冲区中的数据时，谁也不能接收/发送，即死锁。与之类似如图6.40(b)所示，在虫孔寻径中若4个消息占据4个片缓冲区，亦可造成死锁。其中Ci表示通道。,图6.40 死锁示意图,（2）消除死锁 死锁是由于循环等待而引起的，因此只要打破这种循环等待就可避免死锁。解决办法是通过虚拟通道进行包信息或数据片传送。如图6.41(a)所示，增添虚拟通道V3和V4，这样在从结点C向D传送时可经过虚拟通道V3，在从结点D向A传送时可经过虚拟通道V4。用Ci表示通道，则信息传送所经过的通道如图6.41(b)所示，在传送到C3后再传送到V3和V4，而不再是C4，形成螺旋线，从而打破原来的循环。,图6.41 增加虚拟通道消除死锁,6.4.3 流控制策略,当两个或更多的信息包同时传向某一结点时，将引起对缓冲区的竞争，而发生冲突。为此，必须有一个解决策略。1.包冲突的解决 当两个包同时到达某一结点时出现竞争。这就需要予以仲裁，即把通道分配给哪一个包？没有分配到通道的包怎么处理？（1）用缓冲区实现虚拟通道寻径 当包1和包2同时到达某一结点时，让包1通过，而把包2暂存到一个包缓冲区中，由于包缓冲区是由本地存储器提供，因此可构成虚拟通道。在不发生冲突时，可象虫孔寻径一样工作；最坏情况下，与存储转发方式的效果相同。（2）阻塞流控制 在纯粹的虫孔寻径方式中出现冲突时，可采用阻塞流控制策略。就是通过控制门让包1通过，而阻塞包2前进，但是不放弃包2。在通道空闲时，让包2通过。（3）扬弃并重发 在遇到阻塞时放弃包2，在通道可用时再重发包2。（4）阻塞后绕道 在遇到阻塞时把包2送往一条绕行的通道。,2.确定寻径与自适应寻径 在包传送时，常用两种寻径方式。一是确定寻径，另一种是自适应寻径。（1）确定寻径 是指路径由源/目结点的地址来确定。也就是说，所需路径事先唯一确定，与网络状态没有关系。常用的方法是维序寻径，即遵照多维网络的特定顺序来选择后续路径。在二维网格网络中称为XY寻径，首先沿X维方向确定路径，再沿Y维方向选择。如果总是先沿X维方向寻径，再沿Y维方向寻径，则可避免死锁和循环等待，且路径短。至于三维可按XYZ的顺序寻径。在超立方体网络（或n-立方体）中称为E-立方体寻径，是按照从维1到维n的顺序进行。用这种方法可在源/目结点之间找到一条距离最短的路径，且可避免死锁。但是对于环型网络，则不一定得到最短路径。,（2）自适应寻径 自适应寻径是指两个信息包在某结点发生冲突时，使被阻塞的包根据目标地址选择其它路径到达目的结点，这是一种与网络状态有关的寻径方式。为了实现自适应寻径，需要在结点之间建立虚拟通道。通过虚拟通道传送信息，方便，灵活。3.网络通信模式 在多机互连网络中，通信模式有4种：（1）单播方式 单播模式是一种一到一的通信方式，由一个结点发送信息，另一个结点接收信息。（2）选播方式 选播模式是一种一到多的通信方式，由一个结点发送信息，然后有选择地确定一些结点接收。（3）广播方式 广播方式是一种一到全体的通信方式，由一个结点发送信息，其余全部结点接收。（4）会议方式 会议方式是一种多到多的通信方式。,4.通道流量与通道时延 通道流量与通道时延是描述网络寻径效率的两个重要参数。其中通道流量可用传输有关消息时所使用的通道数来表示，通道时延用包的最长传输时间来表示。对于优化的寻径网络，应能以最小的流量和最小的时延实现通信。但是二者并不是毫无关系，达到最小的流量并不一定能获得最小的时延；相反，亦然。在存储转发网络中时延是一个重要的问题，在虫孔寻径网络中流量是一个重要的问题，对效率有着更为重要的影响。5.单播、选播与广播寻径 图6.42是几种选播与广播寻径的示意图。其中图6.42(a)是在34网络上实现单播寻径，其中源结点用S表示，欲将一个信息包传送到5个目标结点上。5个目标结点可用5次单播来实现，寻径流量需要用1+4+3+3+2=13条通道，到达D3的路径最长，时延为4。,图6.42 单播、选播与广播寻径方式,选播寻径如图6.42(b)和(c)所示，是在一个中间结点上复制信息包，然后将多个复制包传送到目标结点上，这样可减少通道流量。其中图(b)的流量为7，最大距离(时延)为4；图(c)的流量为6，最大距离(时延)为5。对于虫孔寻径方式，图(c)的效果比较好，因为它的流量小，而对于存储转发方式，图(b)的效果比较好，因为它的时延小。,图6.42(d)是一种树形结构的广播方式，它把一个包广播到所有的网络结点上。到达第i层结点的时延为i，产生的流量和时延都最小。,