第6章互连网络.ppt

《第6章互连网络.ppt》由会员分享，可在线阅读，更多相关《第6章互连网络.ppt（75页珍藏版）》请在优知文库上搜索。

1、第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、连网络示意图 概括起来，互连网络的主要功能有以下两点：连接各个结点，构成信息通路，传送数据或者控制命令；通过路径选择，实现有目的的信息交换，其中包括一到一和一到多的选择与交换。随着互联网的发展，越来越多的并行计算机系统直接使用台式计算机作为结点机，通过互联网连接，构成并行计算机系统，这也使互连网络由专用型发展成为通用型。2.主要性能 主要是指网络规模、连接度、结点距离、网络直径、带宽、可靠性和成本。（1）网络规模：是指网络中的结点数，它体现网络所能连接的部件数，随着设备的增加而扩大。（2）连接度：也称为结点度，是指与该结点连接的边数，也就是直接连接到该结点的其它结点数，常用d表示。如果一个结点

3、直接连接的其它结点越多，则该网络的连接度也就越高。（3）结点距离：结点距离是从一个结点到另一结点所经过的最少边数。（4）网络直径：网络直径是指网络中任意两个结点之间的最大距离，常用D表示。从数据传送的角度来看，网络直径越小越好。（5）等分宽度：分为通道等分宽度和线等分宽度。把网络切成相等的两半，沿切口的最小边（通道）数称为通道等分宽度，可用k表示；若用w表示通道宽度（用位表示），则B=kw称为线等分宽度。（6）结点间线长：是指两结点之间的线路长度，它影响信号传输中的延时、扭曲和需要的功率。（7）对称性：从任何一个结点来看，若网络的拓扑结构都一样，则称为对称网络。对于这种网络，容易设计和编程。（

4、8）数据寻径功能：表示互连网络把数据从网络的一端传送到另一端的方式和能力，分为静态和动态两种。静态数据寻径网络是指其结构不能用程序改变；而动态数据寻径网络的结构可用程序改变。不同的网络结构有着不同的数据寻径功能，常见的有一到一、一到多(广播)、散射、汇合/聚集、归约(多到一)、循环移位、扫描和全交换等。3.主要参数 （1）带宽 是指网络传送信息的速率，常用Mbps或MBps表示，又分为聚集带宽和等分带宽。所谓聚集带宽是在网络中，从一半结点到另一半结点，每秒钟传送信息的最大位数或字节数.。而等分带宽是指每秒钟从最小线等分宽度(线)上通过信息的最大位数或字节数。例如HPS是一个对称式网络，包含51

5、2个结点，每个端口的带宽为40MBps，可计算出聚集带宽为512/240MBps=10GBps。若用r表示线等分宽度中每条线上传送信息的速率，则等分带宽可表示为P=kwr。（2）传输时间：是指信息通过网络所用的时间，等于信息长度除以带宽。（3）飞行时间：是指消息的第一位数据通过网络到达接收端所用的时间。（4）传输延时：传输延时等于飞行时间与传输时间之和，是消息通过互连网络的时间，但不包括网络两端硬件设备发送和接收的时间。（5）总延时：包括上述传输延时和网络两端的发送与接收时间。（6）误码率：是传输信息时出现错误的概率，等于错误码的位数除以总码长。显然，误码率越低越好。（7）成本：构建互连网络所

6、花的费用。在保证功能要求的基础上，越低越好。4.互连网络设计要素 在设计互连网络时，所考虑的主要因素有以下4个方面。（1）传送方式 传送方式分为同步和异步两种。所谓同步方式，是在数据传送的过程中采用统一的时钟信号。异步方式则不需要统一的时钟信号在各处理机（或单元）之间进行同步，各处理机（或单元）根据自身需要相互建立动态连接。（2）控制策略 是控制互连开关构成信息通路的方式，可分为集中控制和分散控制两种。所谓集中控制，是由统一的控制器对各个互连开关实施控制；而分散控制，是由各个开关自身实施控制。一般SIMD计算机采用的是集中控制和同步传送方式。（3）交换方式 是指数据传送管理方式，分为线路交换和

7、分组交换。线路交换是在传送过程中，在源/目标结点间建立固定的物理通路，适合于成批数据传送。分组交换是对数据进行分组，分别送入互连网络，各分组可通过不同的路由到达目标结点，适合于短数据报文传送。SIMD计算机一般采用线路交换，MIMD多处理机多采用分组交换方式。（4）拓扑结构 是指互连网络中各结点之间的连接关系，可分为静态拓扑和动态拓扑。静态拓扑是在网络运行中其结构不能改变；而在动态拓扑结构中设有有源开关，在网络运行中可借助于控制信号对连接通路重新组合。一维静态拓扑有线性结构，二维有圆型、星型、树状和网格型等结构，三维及以上有超立方体结构等。在动态拓扑中主要分为单级循环网络和各种多级互连网络，其

8、连接形式与互连函数密切相关。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.恒等互连函数也称为直通互连函数，是指输出端与相同序号的输入端对应连接。

9、其表达式为：I(x)=I(bn-1bn-2b1b0)=bn-1bn-2b1b0其示意如图6.2所示，左边表示输入端，右边表示输出端。图6.2 恒等互连示意图 2.交换互连函数交换互连函数（Exchange）实现输入端与地址中某一位取反的输出端连接：Exchange(bn-1bn-2b1b0)=bn-1bn-2b1b0 扩展交换互连函数是把地址中的任一位变反，其表达式为：Exchange(bn-1bn-2bkb1b0)k=bn-1bn-2bk b1b0图6.3 立方体结构图 如果设N=8，则n=log2N=3，其互连关系在空间表示一个立方体，如图6.3所示，因此也称为立方体（Cube）互连函数：

10、Cube0(b2b1b0)=b2b1b0 Cube1(b2b1b0)=b2b1b0 Cube2(b2b1b0)=b2b1b0 按照Cube函数的连接示 意如图6.4所示。图6.4 Cube交换互连示意图按照Cube函数的连接示意如图6.4所示。【例6.1】设有64个处理器，其编号依次是0，1，2，63，按照互连函数Exchange()4连接时，第21号处理器与哪一个处理器连接。解：设待求处理器的序号为i，表示为Pi，则：Pi=Exchange(010101)4 =010101 =0001013.全混洗互连函数 全混洗互连函数(Shuffle)也称为均匀混洗互连函数，它实现输入端与地址中最高位循

11、环移位到最低位的输出端连接：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”单级互连函数的简称，也称为

12、循环移数函数，它实现输入端与地址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)。因此，按照函数PM

13、2I只能构成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按照混

14、洗交换互连函数的连接示意如图6.9所示，其中，N=8。图6.9 混洗交换互连示意图【例6.2】设有128个处理器，其编号依次是0，1，2，127，当复合互连函数为 Shuffle(Exchange(PM2I-2)时，第7号处理器与哪一个处理器连接。解：设待求处理器的序号为i，表示为Pi，则：Pi=Shuffle(Exchange(PM2I-2(00000111)=Shuffle(Exchange(00000111-22)=Shuffle(Exchange(00000011)=Shuffle(00000011)=Shuffle(00000010)=00000100【例6.3】设有128个处理器，

15、其编号依次是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)=010101016.2 静态互连网络6.2.1 静态互连网络结构6.2.2 静态互连网络特性 静态互连网络(Static network)是在点到点之间使用直接链路，设计成功，固定不变，常

16、用来实现集中式系统中子系统之间或分布式系统中多个计算结点之间的固定连接。这种网络较适合于通信模式可以预测或者可用静态网络连接的计算机系统中，且有多种形式，比如一维线性阵列，二维环形、星形、树形和网络形等，三维立方体以及三维以上的超立方体等。下面简要介绍常用静态互连网络，若无专门说明，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)的网络直径