第7章图形、文本和位图.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,第,7,章 互连网络,,7.1,互连网络的基本概念,,,7.2,互连网络的种类,,,7.3,消息传递机制,,,7.4,互连网络实例,1,,7.1,互连网络的基本概念,7.1.1,互连网络的作用,,7.1.2,互连网络的特性,,7.1.3,互连网络的性能参数,,7.1.4,互连网络的表示方法,,7.1.5,互连函数,2,,7.1.1,互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接互连网络已成为并行处理系统的核心组成部分互连网络对整个计算机系统的性能价格比有着决定性的影响一个例子：,具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构,,3,,磁盘,SM,1,SM,2,SM,m,PMN,……,C,n,P,n,LM,C,1,P,1,LM,PCN,……,……,……,……,PION,磁带,打印机,终端,网络,…,(共享存储器),(共享I/O与外设),4,,互连网络,通常是用有向边或无向边连接有限个结点组成如果用图形表示，一个网络可以表示为若干有相互连线的结点组成的图。

互连网络的,主要特性,有：,,(1),网络规模：,网络中结点的个数,,(2),结点度：,与结点相连接的边数称为结点度,,进入结点的边数叫,入度,,从结点出来的边数则叫,出度,,(3),距离：,两个结点之间相连的最少边数,,(4),网络直径,：网络中任意两个结点间距离的最大值用结点间的连接边数表示,7.1.2,互连网络的特性,5,,,网络规模,：即一个网络中所连接的结点数该指标可以用于衡量网络,可扩展性的一个方面,，例如，有没有结点数量限制，如果有，最大能够容纳多少结点单纯从拓扑结构上讲，一般的网络结构都能够容纳无限多的结点，如果要评估不同网络结构的相对性能优劣，必须给它们指定相同的规模，即网络规模也用作建立,一致性评估的基础,6,,,,结点度,：每个结点与外部连接的边数称为一个结点的度，用,d,表示图,6-3,表示了单向和双向通道连接和情况结点度和结点成本是成正比的,，因为度越大，结点上需要构造的接口也越多，因而成本也越高一般使用,平均结点度,或,最大结点度,来衡量一个网络结构中的结点成本7,,结点,A,结点,B,线路,( b ),双向,结点,A,结点,B,线路,( a ),单向,图,6-3,结点间连接示意图,返回,上一张,8,,,,距离,：任意两结点之间相连的最少边数。

距离,与,两结点间最快的信息传输速度,是成正比的平均距离,与,最长距离,可以用于衡量由于网络结构而限定的信息传输,速度指标,,网络直径,：网络中任意结点之间距离中的最大值即,最长距离,，它和网络结构中,最慢的传输速度,成正比，可以在一定程度上衡量网络结构的,速度指标,9,,,等分宽度,：一个网络被切割成对等的两半时（两半网络中结点数相等），沿切口所具有的边数（通道数），称为通道等分宽度，用,b,表示1,）等份切割面可能不止一个，得到的等分宽度也可能不止一个网络的等分宽度一般是指,最小的等分宽度,2,）对于其它,任意切割面,，只要它,不与当前讨论的等份切割面相交,，则该切割面的,宽度必须小于等分宽度,，,否则,网络结构中存在,固定瓶颈,等分宽度,与网络结构的,最大通信带宽,成正比，可以从宏观上分析网络结构中的固定瓶颈，衡量网络结构的,速度指标,10,,,,结点间线长,：两个结点之间实际连接用的线长与,两结点间的,实际,信息传输速率,成正比，因为信号在传输线上传输需要时间，线长越大，速率越慢如果只是评估网络拓扑结构的优劣，并不会采用这一指标11,,,链路数量,：网络中边的总数量与,网络本身,的成本成正比，边数越多，成本越高，可以用于评估网络成本。

,对称性,：如果从任一个结点观察网络，所看到的网络拓扑结构都是相同的，该网络是一个对称网络网络结构的对称性,与,结点概念的一致性等价,，如果网络是一个对称结构，则所有结点上都使用,相同的通信机制或协议软件,，即,软件可扩展性高,一般而言，在对称网络中添加结点比非对称网络更容易，即,硬件扩展性也相对较高,，但这并不是绝对的一定程度上，可以用对称性来衡量网络,可扩展性,的一个方面12,,7.1.3,互连网络的性能参数,发送方的步骤如下：,,(1),用户程序把要发送的数据拷贝到系统缓冲区2),缓冲区中的数据打包并发送到网络接口部件3),网络接口硬件开始发送消息数据包的接收步骤如下：,,(1),把数据包从网络接口部件拷贝到系统缓冲区2),检查收到的数据包，如果正确，发回答信号3),把接收到的数据拷贝到用户地址空间发送方接收到回答信号后释放系统缓冲区,13,,1,、互连网络的主要性能参数：,,(1),频带宽度,(Bandwidth),：,传输信息的最大速率,,(2),传输时间,(Transmission time),：,等于消息长度除以频宽3),飞行时间,(Time of flight),：,第一位信息到达接收方所花费的时间。

4),传输时延,(Transport latency),：,等于飞行时间与传输时间之和5),发送方开销,(Sender overhead),：,处理器把消息放到互连网络的时间6),接收方开销,(Receiver overhead),：,处理器把消息从网络取出来的时间14,,2,、标志网络传输性能的若干参数,,,所谓网络的传输性能主要指一个网络对信息的延迟尺度以一个消息从发送方操作系统取出开始，到接收方操作系统正确,,收到该消息为止，,,一个消息的总时延可以用下面公式表示：,,,总时延＝发送方开销＋飞行时间＋ 消息长度,/,频宽＋接收方开销,15,,,例,7.1,：,假设一个网络的频宽为,10Mb/S,，,发送方开销为,230us,，,接收方开销分别为,270us,如果两台机器相距,100,米，现在要发送一个,1000,字节的消息给另一台机器，试计算总时延如果两台机器相距,1000,公里，那么总时延为多大？,16,,解：,光的速度为,299792.5KM/S,，,信号在导体中传递速度大约是光速的,50,％相距,100,米时总时延为：,,,,,,,相距,1000,公里时的总时延为：,17,,为了在输入结点与输出结点之间建立对应关系，,互连网络有三种表示方法,：,,(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,7.1.4,互连网络的表示方法,18,,7.1.5,互连函数,互连函数也称为互连置换或互连排列等。

1.,交换函数（,Exchange,）,,,,当,n,＝,3,时，有,3,种函数，每种能表示,8,个结点之间的连接关系由于交换函数主要用于,超立方体互连网,中，因此也称为超立方体函数， 用,Cube,表示，如：,Cube0,、,Cube1,、,Cube2,等19,,20,,2.,全混洗函数（,Perfect shuffle,）,,函数关系,：,把二进制结点号循环左移一位,,,子混洗,(,subshuffle)S,(k,),,,最低,k,位循环左移一位,,,超混洗,(,supershuffle)S,(k,),,,最高,k,位循环左移一位,,,显然成立：,,,逆混洗函数,：,起始位,0,终止位,K-1,,右侧,k,位,起始位,n-k,终止位,n-1,,左侧,k,位,21,,22,,3.,蝶式函数（,Butterfly,）,,蝶式函数的名称来自于,FFT,变换时的图形，如蝴蝶式样函数关系：,将输入端二进制结点号的最高位和最低位互换位置,子蝶式,(,subbutterfly)B,(k,),,最低,k,位的,高低位互换,,,超蝶式,(,superbutterfly)B,(k,),,最高,k,位的,高低位互换,,,,显然成立：,23,,24,,4.,反位序函数（,Bit Reversal,）,,函数关系,：,将二进制自变量的位序反过来,。

子反位序函数，,最低,k,位的,位序反过来,,超反位序函数，,最高,k,位的,位序反过来,,,,,对于,n,＝,3,的情况，正好有：,,,R,＝,B,，,R,(2),＝,B,(2),，,R,(2),＝,B,(2),25,,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,个相邻接点连接,26,,27,,例,6.2,：,假设,16,个处理机的编号分别为,0,、,1,、,…,、,15,，采用单级互连网络互连函数分别为：,,,(1)Cube3,,(2)PM2+3,,(3)PM2-0,,(4)Shuffle,,(5),Butterfly,,,(6),Reversal,,,第,13,号处理机分别与哪一个处理机相连？,28,,解：,(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,号处理机,29,,7.2,互连网络的种类,,7.2.1,静态互连网络,,,7.2.2,循环互连网络,,,7.2.3,多级互连网络,,,7.2.4,全排列互连网络,,,7.2.5,全交叉开关网络,30,,静态互连网络,：连接通路是固定的，一般不能实现任意结点到结点之间的互连。

循环互连网络,：,通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 多级互连网络,：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连全排列互连网络：,能够同时实现任意结点到结点之间的互连全交叉开关网络：,能够同时实现任意结点到结点之间的互连，还能够实现广播和多播31,,7.2.1,静态互连网络,按照网络的互连特性为特征分类，可分为如下几类：,,,静态互连网络,,在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构一般静态互连网络不能实现任意结点到结点之间的互连一维,的有线性阵列结构；,二维,的有环形、星形、树形、网格形等；,三维,的有立方体等；,三维以上,的有超立方体等32,,1.,超立方体网,,n,维立方体由,N,＝,2,n,个结点，分布在,n,维上,,超立方体网采用交换函数,网络规模为,2,n,个结点,,结点度为,n,,直径也为,n,33,,2.,环形网,,采用,移数函数,,单向环行网：,右环网采用,PM2,+0,函数，左环网采用,PM2,-0,函数，对称，直径是,N,，,结点度是,2,,双向环行网：,又称一维邻居网，采用,{PM2,+0,，,PM2,-0,},函数，对称，直径为,N/2,，,结点度是,2,,弦环网：,增加的弦愈多，则结点度愈高，网络直径愈小。

循环移数网络：,将每个结点与其距离为,2,的整数幂的结点连接构成循环移数网的结点度为,2n-1,，,直径为,,n/2,,34,,1,0,2,3,4,5,7,6,循环移数网,1,0,2,3,4,5,7,6,度为3的弦环网,1,0,2,3,4,5,7,6,环形网,环形网,35,,3.,树形和星形网,,二叉树：,一棵,k,层二叉树有,N,＝,2,k,－,1,个结点，结点度是,3,，直径是,2(k-1),星形：,一种特殊的,2,层树，结点度很高，为,d=N-1,，,直径是,2,二叉胖树：,缓解了根结点通信速度高的矛盾,36,,4.,网格形网,,二维网格网：,结点度为,,，直径为,,k,维网格网：,网络规模为,,，结点度为,,，,直径为,,,环网形网格网：,沿阵列每行每列都有环形连接n×n,二元环网的结点度为,,，直径为,,环网形网格网是一种,,的拓扑结构,4,2(n-1),4,2,,n/2,,对称,N=,n,k,2k,k(n-1),37,,5.,二维闭合螺旋线网格网,,结点度为,4,，网络直径为,n-1,一个,n×n,的,Illiac,,网格的直径为,,n-1,8×8,网格，结点度为,4,，直径为,7,。

38,,7.2.2,循环互连网络,一般静态互连网不能实现任意两结点之间的互连有两种解决办法：,,循环互连网：,多次重复使用同一个单级互连网络,,多级互连网：,将多套相同的单级互连网络连接起来,,前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间,,RN,为网络连接寄存器，它有三个用处：发送消息，接收消息，转发消息,,39,,例如：,对于一个,3,维立方体网，如果要从,PE0,发送消息到,PE3,，,需要经过如下,4,步：,,周期,1,：,PE0,,RN0,，,周期,2,：,RN0,,RN1,,,周期,3,：,RN1,,RN3,，,周期,4,：,RN3,,PE3,40,,7.2.3,多级互连网络,循环互连网络虽然能够实现结点到结点之间的任意互连，但是其通信速度低多级互连网络采用多个相同的或不同的单级互连网络直接连接起来一个时钟周期就能够实现任意结点到结点之间的互连多级互连网络采用的关键技术：,,,(1),交换开关，,,,(2),交换开关之间的拓扑连接，,,,(3),对交换开关的不同控制方式41,,1.,交换开关,,一个,a×b,交换开关有,a,个输入和,b,个输出最常用的二元开关：,a=b=2,。

每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突一对一和一对多映射是容许的；但不容许有多对一映射只容许一对一映射时称为置换连接，称这种开关为交叉开关具有直通和交换两种功能的开关称为,二功能开关，,或交换开关用一位控制信号控制具有所有,4,种功能的交换开关称为,四功能开关,，用两位控制信号控制42,,43,,2.,拓扑结构,,前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构通常，采用前面介绍过的互连函数实现拓扑结构实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接44,,3.,控制方式,,有多级交换开关，每一级又有多个交换开关通常有三种控制方式,,级控制,：同一级交换开关使用同一个控制信号控制单元级控制,：每个交换开关分别控制部分级控制,：第,i,级使用,i+1,个控制信号控制（,0,,i,,n-1,）同一个多级互连网络分别采用三种不同的控制方式，可以构成三种不同的互连网络45,,4.,多级立方体网,,采用二功能开关,，总共需要开关,n 2,n-1,个采用交换函数,，各级分别采用,E,0,,E,1,,…E,n-1,函数,,当所有开关都直通时，实现恒等变换。

当,A,、,B,、,C,、,D,交换，其余直通实现,E,0,函数当,E,、,F,、,G,、,H,交换，其余直通实现,E,1,函数当,I,、,J,、,K,、,L,交换，其余直通实现,E,2,函数采用不同的控制方式,，可构成不同的互连网络,,采用级控制可以构成,STARAN,交换网采用部分级控制，可以构成,STARAN,移数网采用级控制可以构成间接二进制,n,方体网46,,多级立方体网,47,,7.2.4,全排列互连网络,循环互连网络和多级互连网络不能实现同时多个结点之间的互连例如：多级立方体网中，如果要求同时实现,0,,5,和,1,,7,的互连，在开关,A,发生冲突全排列互连网络不仅能够实现任意结点到结点之间的互连，而且能够实现同时任意结点之间的互连解决方法：采用多个多级互连网络连接原理：,N,个结点的全排列需要有,N,！,，,,N,个结点的多级互连网络共有二功能开关,n 2,n-1,个，共有不同的状态种类：,48,,7.2.5,全交叉开关网络,全交叉开关网络除了能够实现同时任意结点之间的互连之外，还能够,实现广播和多播,在多处理机系统中，处理机、存储器和,IOP,之间用交叉开关网络连接。

49,7.3,消息传递机制,,7.3.1,消息寻经方式,,,7.3.2,虚拟通道,,,7.3.3,流控制策略,,,7.3.4,选播与广播,50,,7.3.1,消息寻径方式,1.,线路交换,(circuit switch),,先建立一条从源结点到目的结点的物理通路，然后传递消息传输时延用公式：,T,＝,(Lt/B)×D+L/B,，,,,,其中：,Lt,为建立路径所需的小信息包的长度，,,,L,为信息包的长度，,,,D,为经过的结点数，,B,为带宽优点：实际通信时间较短，使用缓冲区少缺点：建立物理通路的开销很大，占用物理通路的时间长51,,2.,存储转发,(store and forward),,每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点存储转发网络的时延与源和目的地之间的距离成正比时延用公式：,,,T,＝,(L/B)×D+L/B=(D+1)×L/B,,优点：占用物理通路的时间比较短缺点：包缓冲区大，时延大（与结点距离成正比）52,,3.,虚拟直通,(virtual cut through),,当接收到用作寻径的消息头部时，即开始路由选择通信时延公式：,,,T=(,L,h,/B)×D+L/B=(,L,h,×D+L,)/B≈L/B,,,其中：,L,h,是寻径头部的长度，一般,L>>,L,h,×D,,当出现寻径阻塞时，只能将整个消息存储在寻径结点中。

优点：通信延迟与结点数无关缺点：每个结点需要有足够大的缓冲区在最坏的情况下与存储转发方式的通信时延相同，经过的每个结点都阻塞，都需要缓冲53,,4.,虫蚀寻径,(wormhole),,把包分成更小的片,每个结点的寻径器中设置有片缓冲区用头片直接开辟一条从输入结点到输出结点的路径,每个消息中的片以流水方式在网络中向前“蠕动”当消息的头片到达一个结点的寻径器后，寻径器根据头片的寻径消息立即做出路由选择,,如果所选择的通道或结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待54,,时延公式：,,,T=,T,f,×D+L,/B=(L,f,/B)×D,＋,L/B=(L,f,×D,＋,L)/B,,,,其中：,L,f,是片的长度，,,,T,f,是片经过一个结点所需时间一般有,L>>L,f,×D,，,时延近似为：,T,＝,L/B,，,与结点数无关优点：,每个结点的缓冲区较小较低的网络传输时延；通道共享性好，利用率高；易于实现选播和广播通信方式缺点：,当消息的一个片被阻塞时，整个消息都被阻塞55,,7.3.2,虚拟通道,1.,虚拟通道,,虚拟通道是两个结点间的逻辑链路，由源结点的片缓冲区、结点间的物理通道及接收结点的片缓冲区组成。

56,,2.,死锁的产生与避免,,缓冲区或通道上的循环等待会引起死锁利用虚拟通道可以减少死锁,虚拟通道可能会使每个请求可用的有效通道频宽降低57,,7.3.3,流控制策略,在相邻结点间传送片时，必须具备三个条件：,,,(1),源缓冲区已存有该片；,,,(2),通道已分配好；,,,(3),接收缓冲区准备接收该片接收缓冲区或输出通道冲突的仲裁：,,,(1),把后一个包暂时存放在缓冲区2),阻塞后一个包3),场弃后一个包4),绕道58,,维序寻径算法：,,按照特定顺序选择后继通道在二维网格网络中称为,X-Y,寻径：,,例如，,X,优先于,Y,,,在超立方体中称为,E,立方体寻径：,,逐维改变59,,采用双虚拟通道和,X-Y,寻经可以完全避免死锁,,60,,7.3.4,选播与广播寻径算法,四种通信模式：,,(1),单播,(,unicast,),，,一对一传送2),选播,(multicast),，,从一个源结点发送同一消息到多个目的结点,,(3),广播,(broadcast),，,从一个源结点发送同一消息到全部结点4),会议,(conference),，,多到多的通信情况扩充选播树的原则：选择某些维使剩余目的结点的集合最小。

贪婪选播算法所需的通道数，与多次单播或广播树所需的通道数相比要少61,,62,,7.4,互连网络实例,7.4.1,总线互连,,7.4.2,多端口存储器,,7.4.3 STARAN,交换网和,STARAN,移数网,,7.4.4 Omega,互连网,63,,7.4.1,总线互连,总线的优点：结构简单，很方便实现广播总线的缺点：带宽低，发生冲突的可能性大总线冲突的解决办法有：,,,(1),设置静态优先级,,,(2),在同步方式中采用时间片,,,(3),采用动态优先级（如,LRU,法等）,,,(4),先来先服务,,提高总线通信带宽的方法有：,,,(1),采用多总线结构,,,(2),层次总线结构,,,(3),多维总线结构,64,,多总线：,西门子公司的,SMS,系统（,Stractured,Multiprocessor System,）,通过,8,条总线连接,128,个处理机65,,层次总线：,卡内基梅隆大学的,C,m,*,多处理机系统采用层次总线结构三级总线：,群总线、,Map,总线、处理机总线,,,,每群,14,台处理机,66,,7.4.2,多端口存储器,多个多端口存储器与多个,CPU,和,IOP,连接。

多端口存储器用于处理机个数不多的系统中把复杂的互连网络移到了存储器中67,,7.4.3 STARAN,交换网和移数网,多级立方体网，应用在巨型机,STARAN,中采用级控制可以构成,STARAN,交换网采用部分级控制，可以构成,STARAN,移数网子洗,2,蝶,1+,逆洗,68,,STARAN,交换网实现交换函数关系,,例如：,输入端：,0 1 2 3 4 5 6 7,,4G2E,：,1,,0 3,,2 5,,4 7,,8,,2G4E,：,2 3,,0 1 6 7,,4 5,,,结果为：,(0,2) (1,3) (4,6) (5,7),69,,STARAN,移数网,实现移数函数关系,,因为,第,i,级用,i+1,个控制信号,，因此共有,6,个控制信号有,64,种不同的控制表中仅列出了一小部分70,,7.4.4 Omega,互连网,采用全混洗函数和交换函数，又称混洗交换网络N,个输入的,Omega,网络有,log2N,级，每级有,N/2,个,2×2,的四功能交换开关，每级的拓扑结构相同，采用单元控制（每一级的控制信号均相同）Omega,网能够实现任意一个输入端到任意一个输出端的连接。

但不能同时实现多个输入端到多个输出端的连接当有,N,个输入端时，共有,N,N/2,个种变换如果要同时实现任意一个输入端到任意一个输出端的连接，共需要,N,！,种变换换Omega,网能够实现从任意一个输入端到所有输出端的广播71,,同时实现,0,,6,和,4,,7,有冲突，同样还有：,3,,0,和,5,,1,，,3,,0,和,7,,3,，,5,,0,和,7,,1,等8,个输入端的,Omega,网络实际上只能实现全部变换的,10%, 8,4,/8! = 4096/40320=0.1016,72,,本章重点：,,1.,主要的互连函数,,2.,几种典型互连网络的构成方法及特点,,3.,寻径方式的原理及优缺点,,,,练习题,:,,7.3 7.5 7.19 7.23 7.27/(1)(2),73,,。