单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 互联网络,互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接互连网络已成为并行处理系统的核心组成部分互连网络对整个计算机系统的性能价格比有着决定性的影响一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构,磁盘,SM,1,SM,2,SM,m,PMN,C,n,P,n,LM,C,1,P,1,LM,PCN,PION,磁带,打印机,终端,网络,(共享存储器),(共享I/O与外设),互连网络通常是用有向边或无向边连接有限个结点的组成互连网络的主要特性有：,(1),网络规模：网络中结点的个数,(2),结点度：与结点相连接的边数称为结点度,进入结点的边数叫入度,从结点出来的边数则叫出度,(3),距离：两个结点之间相连的最少边数,(4),网络直径：网络中任意两个结点间距离的最大值用结点间的连接边数表示,互连网络的特性,互连网络的性能参数,发送方的步骤如下：,(1),用户程序把要发送的数据拷贝到系统缓冲区2),缓冲区中的数据打包并发送到网络接口部件。
3),网络接口硬件开始发送消息数据包的接收步骤如下：,(1),把数据包从网络接口部件拷贝到系统缓冲区2),检查收到的数据包，如果正确，发回答信号3),把接收到的数据拷贝到用户地址空间发送方接收到回答信号后释放系统缓冲区,互连网络的主要性能参数：,(1),频带宽度,(Bandwidth),：传输信息的最大速率,(2),传输时间,(Transmission time),：等于消息长度除以频宽3),飞行时间,(Time of flight),：第一位信息到达接收方所花费的时间4),传输时延,(Transport latency),：等于飞行时间与传输时间之和5),发送方开销,(Sender overhead),：处理器把消息放到互连网络的时间6),接收方开销,(Receiver overhead),：处理器把消息从网络取出来的时间一个消息的总时延可以用下面公式表示：,总时延发送方开销飞行时间 消息长度,/,频宽接收方开销,例,7.1,：假设一个网络的频宽为,10Mb/S,，发送方开销为,230us,，接收方开销分别为,270us,如果两台机器相距,100,米，现在要发送一个,1000,字节的消息给另一台机器，试计算总时延。
如果两台机器相距,1000,公里，那么总时延为多大？,解：光的速度为,299792.5KM/S,，信号在导体中传递速度大约是光速的,50,相距,100,米时总时延为：,相距,1000,公里时的总时延为：,为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：,(1),互连函数表示法：如：,f(x,n-1,x,1,x,0,)=x,0,x,n-2,x,1,x,n-1,(2),图形表示法,(3),输入输出对应表示法,互连网络,0,0,1,1,n-1,n-1,输入,:0 1 2 3 4 5 6 7,输出,:1 0 3 2 5 4 7 6,互连网络的表示方法,互连函数,互连函数也称为互连置换或互连排列等1.,交换函数（,Exchange,）,当,n,3,时，有,3,种函数，每种能表示,8,个结点之间的连接关系由于交换函数主要用于,超立方体互连网,中，因此也称为超立方体函数，用,Cube,表示，如：,Cube0,、,Cube1,、,Cube2,等2.,全混洗函数（,Perfect shuffle,）,函数关系：把二进制结点号循环左移一位,子混洗,(subshuffle)S,(k),最低,k,位循环左移一位,超混洗,(supershuffle)S,(k),最高,k,位循环左移一位,3.,蝶式函数（,Butterfly,）,蝶式函数的名称来自于,FFT,变换时的图形，如蝴蝶式样。
函数关系：将输入端二进制结点号的最高位和最低位互换位置子蝶式,(subbutterfly)B,(k),最低,k,位的,高低位互换,超蝶式,(superbutterfly)B,(k),最高,k,位的,高低互换,显然成立：,4.,反位序函数（,Bit Reversal,）,函数关系：将二进制自变量的位序反过来子反位序函数，,最低,k,位的,位序反过来,超反位序函数，,最高,k,位的,位序反过来,5.,移数函数,函数关系：将输入端向量循环移动一定的位置,经常取,r,2,i,，因此移数函数又称为加减,2,i,函数、,PM2I,函数等子移数函数：,其中：,0,x,N-1,，,0,i,k,n-1,，,n=log,2,N,Illiac,函数包含,PM2,0,和,PM2,n/2,等,4,个互连函数,每个接点与它的上下左右,4,个相邻接点连接,例,6.2,：假设,16,个处理机的编号分别为,0,、,1,、,、,15,，采用单级互连网络互连函数分别为：,(1)Cube3,(2)PM2+3,(3)PM2-0,(4)Shuffle,(5)Butterfly,(6)Reversal,第,12,号处理机分别与哪一个处理机相连？,解：,(12),10,=(1100),2,(1)Cube3,，,(2)PM2+3,，,(3)PM2-0,，,(4)Shuffle,，,(5)Butterfly,，,(6)Reversal,1100,最高位取反得,0100,，,4,号处理机,(12+8)MOD 16=4,，,4,号处理机,12 1=11,，,11,号处理机,1100,循环左移,1,位得到,1001,9,号处理机,1100,的最高最低位交换,0101,5,号处理机,1100,的位序反过来为,0011,3,号处理机,补充,:,基本的单级互连网络,1.,立方体单级网络,立方体的每个顶点代表一个结点，结点的编号用二进制码（,C,2,C,1,C,0,）表示。
N,8,的三维立方体结构,立方体单级网络的互连函数实现二进制编号中第,k,位值不同的结点之间的连接故三维的立方体单级网络有三种互连函数：,Cube,0,、,Cube,1,和,Cube,2,，分别建立结点编号中,C,0,不同或,C,1,不同或,C,2,不同的结点之间的连结N,8,的三维立方体三种互连方式,一般情况下，一个,n,维立方体有,N,2,n,个结点，共有,n,种互连函数，分别由,n,位编号中的每一位的位值求反来确定当维数,n,3,时，称为超立方体,(Hyper Cube),网络对于,n,维立方体单级网络，要实现任意两个结点之间的连接，最多需使用,n,次不同的互连函数 因此,n,维立方体单级网络的最大距离为,n,2,PM2I,（是加减,2,i,的简称，,plus,minus2,i,）,PM2I,单级网络能实现,j,号结点与,j,2,i,mod,N,号结点的直接相连，,N,为处理器的个数，,n,log,2,N,因此，它共有,2,n,个互连函数，即,PM2,i,（,j,）,j,2,i,mod,N,PM2,i,（,j,）,j,2,i,mod,N,式中，,0,j,N,1,，,0,i,n,1,。
设,N,8,，则各互连循环为,PM2,0,：（,01234567,）,PM2,0,：（,76543210,）,PM2,1,：（,0246,）（,1357,）,PM2,1,：（,6420,）（,7531,）,PM2,2,：（,04,）（,15,）（,26,）（,37,）,N,8,的,PM2I,互连网络的部分连接图,网络的最大距离为,n/2,=,log2,N,/2,，这里,表示向上取整由三维,PM2I,互连网络可以看出，最多只要两次使用，即可实现任意一对入出端号间的连接PM2I,互连特性,3.,混洗交换,(shuffle exchange),混洗交换互连网络包含全混洗和交换两种互连函数1,）全混洗,全混洗的互连函数为,Shuffle,（,P,n,1,P,n,2,P,1,P,0,）,P,n,2,P,1,P,0,P,n,1,全混洗互连示意图,（,2,）交换,由于单一的全混洗互连网络不能实现二进制编号为全“,0”,和全“,1”,的结点与其他任何结点的连接，所以又增加了,Cube,0,交换互连函数同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络N,8,的全混交换互连网络连接图,在混洗交换网络中，最远的两个入出端号是全“,0”,和全“,1”,，它们的连接需要,n,次交换和,n-1,次混洗，所以其最大距离为,2n-1,。
互连网络的种类,静态互连网络,循环互连网络,多级互连网络,静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能改变一般不能实现任意结点到结点之间的互连循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的一种，适用于,SIMD,和,MIMD,静态互连网络,在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构一般静态互连网络不能实现任意结点到结点之间的互连一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等循环互连网络,一般静态互连网不能实现任意两结点之间的互连有两种解决办法：,循环互连网：多次重复使用同一个单级互连网络,多级互连网：将多套相同的单级互连网络连接起来,前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间多级互连网络,多级网络互连是将多套单级互连网络通过关模块串连扩展成多级互连网络（简称,MIN,）的方式与单级网络相比，多级网络可以通过改变开关的控制方式灵活地实现各种连接，满足系统应用的需要多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。
一个时钟周期就能够实现任意结点到结点之间的互连常见的有多级立方体互连网络、多级混洗交换网络（,Omega,网络）、多级,PM2I,网络、多级,BENES,可重排网络及多级,CLOS,网络等多级互连网络采用的关键技术：,(1),交换开关，,(2),交换开关之间的拓扑连接，,(3),对交换开关的不同控制方式1.,交换开关,一个,a,b,交换开关有,a,个输入和,b,个输出最常用的二元开关：,a=b=2,每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突一对一和一对多映射是容许的；但不容许有多对一映射只容许一对一映射时称为置换连接，称这种开关为交叉开关具有直通和交换两种功能的开关称为二功能开关，或交换开关用一位控制信号控制具有所有,4,种功能的交换开关称为四功能开关，用两位控制信号控制交换开关的四种功能,2.,拓扑结构,又称为级间连接模式,ISC(interstage connection),，是前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构级间连接是固定的，可以用互连函数表示级间连接模式常用的级间连接模式包括混洗、交叉、立方体连接等，从而构成具有不同连接特性的多级互连网络。
3.,控制方式,控制方式是指通过对开关模块的状态控制来实现多级网络间互连要求的方式，称之为互连网络拓扑结构可动态重构有多级交换开关，每一级又有多个交换开关通常有三种控制方式,级控制：同一级交换开关使用同一个控制信号控制单元级控制：每个交换开关分别控制部分级控制：第,i,级使用,i+1,个控制信号控制（,0,i,n-1,）同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络4.,多级立方体网络,是将,Cube0,、,Cube1,和,Cube2,三种函数构成的单级网络串接起来，是一种,STARAN,网络使用二功能交换开关，即直通和交换，分级控制，可实现交换网络功能采用不同方式控制，可实现不同连通功能即当第,i,级控制信号为,0,。