计算机系统结构-第六章(互连网络).ppt

互连网络,基本概念互连网络种类消息传递机制,基本概念,本章内容,互连网络的作用互连网络的表示常用互连函数互连网络的特性传输性能参数,互连网络的作用,本章内容基本概念,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。,3 之 1,举例说明(多处理机),本章内容基本概念,3 之 2,SM:共享存储器LM:本地存储器 P:处理机C:高速缓存IPMN：内部处理机-存储器网络 IPCN：内部处理机间通信网络PION：处理机-输入输出间网络,本章内容基本概念,3 之 3,基本模型,互连网络的表示,本章内容基本概念,为了在输入结点与输出结点之间建立对应关系，互连网络有两种表示方法：互连函数表示法 自变量和函数常用二进制表示。例如：f(xn-1x1x0)=x0 xn-2x1xn-1。输入输出对应表示法,输入:0 1 2 3 4 5 6 7输出:0 4 2 6 1 5 3 7,输入:0 1 2.n 输出:f(0)f(1)f(2).f(n),常用互连函数,恒等置换交换置换方体置换均匀洗牌置换,蝶式置换位序颠倒置换移数置换加减2i置换,本章内容基本概念,恒等置换,I(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7,本章内容基本概念常用互连函数,N=8 的恒等置换,交换置换,E(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7,本章内容基本概念常用互连函数,N=8 的交换置换,方体置换 互连函数,Ck(xn-1xn-2.xk.x1x0)=xn-1xn-2.xk.x1x0例如：当N=8时，有3种函数，每种能表示8个结点之间的连接关系。C2(x2x1x0)=x2x1x0 C1(x2x1x0)=x2x1x0C0(x2x1x0)=x2x1x0 C0就是交换置换。,本章内容基本概念常用互连函数,3 之 1,方体置换 图示（N=8）,0000001 111112 222223 333334 444445 555556 666667 77777C0方体置换 C1方体置换 C2方体置换,本章内容基本概念常用互连函数,3 之 2,方体置换 提示,由于方体置换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。,本章内容基本概念常用互连函数,3 之 3,z,y,x,010,011,110,111,000,001,101,100,Cube0=(b2b1b0)Cube1=(b2b1b0)Cube2=(b2b1b0),001,均匀洗牌置换 互连函数,本章内容基本概念常用互连函数,均匀洗牌(shuffle:循环左移一位)(xn-1xn-2.xk.x1x0)=xn-2.xk.x1x0 xn-1 子洗牌(subshuffle:最低k位循环左移一位)(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkxk-2.x1x0 xk-1 超洗牌(supershuffle:最高k位循环左移一位)(k)(xn-1xn-2.xn-kxn-k-1.x1x0)=xn-2.xn-kxn-1xn-k-1.x1x0,4 之 1,均匀洗牌置换 图示（N=8）,本章内容基本概念常用互连函数,4 之 2,0000001 111112 222223 333334 444445 555556 666667 77777均匀洗牌 子洗牌(2)超洗牌(2),均匀洗牌置换 提示,本章内容基本概念常用互连函数,4 之 3,三种置换之间的关系逆洗牌（二进制结点号循环右移一位）-1(xn-1xn-2.x1x0)=x0 xn-1xn-2.x1,均匀洗牌置换 应用,均匀洗牌与逆均匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega（）网络与逆Omega（）网络。函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛的应用。,本章内容基本概念常用互连函数,4 之 4,蝶式置换 互连函数,本章内容基本概念常用互连函数,3 之 1,蝶式(butterfly:高低位互换)(xn-1xn-2.xk.x1x0)=x0 xn-2.xk.x1xn-1 子蝶式(subbutterfly:最低k位高低位互换)(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkx0 xk-2.x1xk-1 超蝶式(superbutterfly:最高k位高低位互换)(k)(xn-1xn-2.xn-k+1xn-kxn-k-1.x1x0)=xn-kxn-2.xn-k+1xn-1xn-k-1.x1x0,蝶式置换 图示（N=8）,本章内容基本概念常用互连函数,0000001 111112 222223 333334 444445 555556 666667 77777 蝶式子蝶式(2)超蝶式(2),3 之 2,蝶式置换 提示,本章内容基本概念常用互连函数,3 之 3,三种置换之间的关系 应用 蝶式与子蝶式置换和交换置换多级组合可作为构成方体多级网络的基础。,位序颠倒置换 互连函数,本章内容基本概念常用互连函数,位序颠倒置换（Bit Reversal:位序颠倒）(xn-1xn-2.xk.x1x0)=x0 x1.xk.xn-2xn-1 子位序颠倒置换（最低k位的位序颠倒）(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkx0 x1.xk-2xk-1 超位序颠倒置换（最高k位的位序颠倒）(k)(xn-1xn-2.xn-k+1xn-kxn-k-1.x1x0)=xn-kxn-k+1.xn-2xn-1xn-k-1.x1x0,2 之 1,位序颠倒置换 图示（N=8）,本章内容基本概念常用互连函数,0000001 111112 222223 333334 444445 555556 666667 77777位序颠倒 子位序颠倒(2)位序颠倒(2),2 之 2,移数置换 互连函数,移数函数子移数函数,本章内容基本概念常用互连函数,2 之 1,移数置换 图示（N=8）,本章内容基本概念常用互连函数,00001 1112 2223 3334 4445 5556 6667 777 移数置换k=2 子移数置换（k=1,r=2）,2 之 2,加减2i置换,实际上是一种移数置换。其中：0 xN-1，0in-1，n=log2N。,本章内容基本概念常用互连函数,你掌握了吗？,本章内容基本概念常用互连函数,假设16个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal问：第12号处理机分别与哪一个处理机相连？,2 之 1,你掌握了吗？,本章内容基本概念常用互连函数,2 之 2,解：(12)10=(1100)2 Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal1100最高位取反得01004号处理机(12+23)MOD 16=4 4号处理机(1220)MOD 16=1111号处理机1100循环左移1位得到1001 9号处理机1100的最高最低位交换01015号处理机1100的位序反过来为00113号处理机,互连网络的特性,本章内容基本概念,互连网络通常是用有向边或无向边连接有限个结点，主要特性有：网络规模：网络中结点的个数。结点度：与结点相连接的边数称为结点度，包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度。距离：两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示。,2 之 1,互连网络的特性,本章内容基本概念,等分宽度 当网络被切成相等的两半时，沿切口的最小边数（通道）称为通道等分长度。结点间的线长 两个结点间连线的长度，用米等表示。对称性 从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。,2 之 2,传输性能参数,本章内容基本概念,5 之 1,一个连接两台机器的简单网络模型为：,机器A,机器B,传输性能参数,本章内容基本概念,5 之 2,发送方开销,传输时间,飞行时间,传输时间,接收方开销,传输时延,总时延,时间,发送方,接收方,传输性能参数,本章内容基本概念,5 之 3,频带宽度(Bandwidth)互连网络传输信息的最大速率，单位为Mbps。传输时间(Transmission time)等于消息长度除以频宽。飞行时间(Time of flight)第一位信息到达接收方所花费的时间。传输时延(Transport latency)等于飞行时间与传输时间之和。,传输性能参数,本章内容基本概念,5 之 4,发送方开销(Sender overhead)处理器把消息放到互连网络的时间。接收方开销(Receiver overhead)处理器把消息从互连网络取出来的时间。总时延总时延=发送方开销传输时延接收方开销=发送方开销飞行时间传输时间接收方开销,举 例,本章内容基本概念,5 之 5,问：假设一个网络的频宽为10Mbps，发送方开销为230s，接收方开销为270s。如果两台机器相距100m，信号传播速度为200m/s，现在要发送一个1000Byte的消息给另一台机器，试计算总时延。解：,互连网络种类,本章内容,静态互连网络动态互连网络,静态互连网络,本章内容互连网络种类,在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。按拓朴结构又可分为一维、二维、三维等，一维的有线性阵列结构；二维的有环形、树形、星形、网格形等；三维的有立方体等；三维以上的有超立方体等。静态互连网络灵活性和适应性较差，很少使用。,线性阵列,本章内容互连网络种类静态互连网络,有N个结点，结点度等于2，网络直径为N-1，等分宽度为1，拓扑结构不对称。线性阵列结构最简单，但网络的延迟比较大，S0有信息发送到SN-1必需通过所有其他结点。,S0,SN-2,S4,S3,S2,S1,SN-1,环 形,本章内容互连网络种类静态互连网络,单向环 右环网采用PM2+0函数，左环网采用PM2-0函数，对称，直径是N-1，结点度是2。双向环 又称一维邻居网，采用PM2+0，PM2-0函数，对称，直径为N/2，结点度是2。弦环网 将结点度由2提高至3。增加的弦愈多，则结点度愈高，网络直径愈小。极端情况是全连接，网络直径为1。,3 之 1,环 形,本章内容互连网络种类静态互连网络,3 之 2,循环移数网络,本章内容互连网络种类静态互连网络,循环移数网络是将环上每个结点与其距离为2的整数幂的结点之间连接构成。即，采用2n-1个互连函数：PM2i(j)=(j2i)mod N，n=log2N，0in-1,0jN-1；其中：PM2+(n-1)=PM2-(n-1)。若循环移数网的网络规模是2n，则结点度d=2n-1，网络直径D=n/2。例如：结点数64，n=6，d=11，D=3。,3 之 3,树 形,本章内容互连网络种类静态互连网络,二叉树 一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。星形 一种特殊的2层树，结点度很高，为d=N-1，直径是2。二叉胖树 缓解了根结点通信速度高的矛盾。,2 之 1,树 形,本章内容互连网络种类静态互连网络,2 之 2,二叉树网,二叉胖树网,星形网,网格形,本章内容互连网络种类静态互连网络,网格形是一种比较流行的网络结构，有各种变体形式在ILLIAC IV、MPP、DAP、CM-2和Intel Paragon等中得到了实现。,5 之 1,二维网格,本章内容互连网络种类静态互连网络,一般的二维网格有Nn1n2 个结点组成，直径是D=（n1 1）+（n2 1）。实际上经常是n1=n2=n。结点度为4，是一种非对称的拓扑结构。,5 之 2,环形二维网格,本章内容互连网络种类静态互连网络,环形二维网格沿阵列每行每列都有环形连接。nn二元环网的结点度为4，直径为D=2n/2。环网是一种对称的拓扑结构。,5 之 3,ILLIAC网格,本章内容互连网络种类静态互连网络,二维网格逐行（或列）串形连接。nn ILLIAC 网格的直径为D=n-1，为纯网格直径的一半。例如：Illiac IV的88 Illiac网格，其结点度为4，直径为7。,5 之 4,ILLIAC网格,本章内容互连网络种类静态互连网络,ILLIAC网络的结点连接按一定的算法进行:Illiac+1(j)=(j+1)mod(N)Illiac-1(j)=(j-1)mod(N)Illiac+n(j)=(j+n)mod(N)Illiac-n(j)=(j-n)mod(N),5 之 5,超立方体,本章内容互连网络种类静态互连网络,超立方体也称 n 维立方体，由N2n 个结点组成，分布在n维上，每维有两个结点。超立方体结点度为n，直径也为n，每个结点由n个二进制数实行编号，相邻结点只能有一个数字不同。超立方体缺乏可扩展性，难以组成高维超立方体。,3 之 1,超立方体,本章内容互连网络种类静态互连网络,3 之 2,Y,X,Z,011,000,010,110,111,101,100,001,11,00,10,01,2维立方体,3维立方体,2,3,1,0,6,7,3,2,0,1,5,4,0,1,1维立方体,0,1,超立方体,本章内容互连网络种类静态互连网络,3 之 3,总 结,本章内容互连网络种类静态互连网络,动态互连网络,本章内容互连网络种类,动态互连网络中的连接通路是可变的，结点之间的连接可以重新配置。一般由开关和连线组成，通过控制开关来建立不同的连接。,分 类,本章内容互连网络种类,动态网络,交叉开关,多级网络,全排列网络,总线网络,总线网络,多个处理机、存储器模块和外围设备通过接口与公用总线相连，多个结点将争用总线，必需裁决或分时使用。但连接可以任意、动态地变化。,本章内容互连网络种类动态互连网络,4 之 1,问题及解决,问题：公用总线上的结点数目增多会导致系统效率急剧下降。解决：采用优质高频同轴电缆来提高总线的传输速率；采用多总线方式来减少访问总线的冲突概率。,本章内容互连网络种类动态互连网络,4 之 2,问题及解决,问题：存在访问冲突。解决：静态优先级算法：为连接到总线的每个部件分配一个固定的优先级。固定时间片算法：将总线按时间分成固定大小的时间片，轮流提供给部件使用。动态优先级算法：让总线上各部件优先级根据情况和一定规则动态地改变。例如：LRU。先来先服务算法：按接受到访问总线请求的先后顺序来响应。,本章内容互连网络种类动态互连网络,4 之 3,举 例,本章内容互连网络种类动态互连网络,4 之 4,P1,P2,Pn,M1,M2,Mm,共享总线,总线接口,总线接口,总线接口,总线控制器（仲裁逻辑）,总线忙,总线许可,总线请求,交叉开关网络,一组纵横开关阵列构成多总线（总线数为m+n+i，且mn+i；可同时通信的总线数为m），交叉点开关能在对偶（源和目的）之间形成动态连接。,本章内容互连网络种类动态互连网络,5 之 1,举 例 C.mmp多处理机,本章内容互连网络种类动态互连网络,P1,P2,P16,M1,M2,M16,开关,处理机-存储器交叉开关网络,5 之 2,问题及解决,问题：交叉开关网络很复杂，代价大。因为开关阵列的每个交叉点上均有一套开关，每套开关内部含有多选一的仲裁模块和多路转换器模块。解决：通过用多个较小规模的交叉开关网络“串联”和“并联”来构成多级交叉开关网络，以取代单级的大规模的交叉开关。,本章内容互连网络种类动态互连网络,5 之 3,Delta网,本章内容互连网络种类动态互连网络,用ab的交叉开关模块构成anbn的交叉开关网络，其中指数n为互连网络的级数。例如：用44的交叉开关模块构成4242的交叉开关网络，其中指数2为互连网络的级数。,5 之 4,图 示,本章内容互连网络种类动态互连网络,0,3,4,7,8,11,12,15,0,3,4,7,8,11,12,15,出端,入端,5 之 5,多级网络,基本思想关键技术开关模块控制方式级间连接模式,常见多级网络STARAN网络间接二进制n方体网络Omega（）网络基准网络,本章内容互连网络种类动态互连网络,基本思想,多级互连网络用若干个较小规模的开关模块组成开关级，开关级之间有固定连接的级间连接，通过控制信号改变开关模块的输入端与输出端之间的连接状态，从而可改变网络输入端与输出端之间的连接。,本章内容互连网络种类动态互连网络多级网络,2 之 1,通用多级网络结构,本章内容互连网络种类动态互连网络多级网络,2 之 2,ab开关,0,1,a-1,ab开关,a,a+1,2a-1,ab开关,an-1,an-a,级间连接模式ISC1,ab开关,ab开关,ab开关,ISC2,ISCn-1,ab开关,ab开关,ab开关,0,1,b-1,b,b+1,2b-1,bn-1,bn-b,级1,级2,级n,开关模块,本章内容互连网络种类动态互连网络多级网络,4 之 1,一个ab开关模块有a个输入和b个输出，最常用的是二元开关（22）。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。即：一对一和一对多映射是容许的，但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为nn交叉开关。,开关模块和合法状态,本章内容互连网络种类动态互连网络多级网络,4 之 2,模块大小,合法状态,置换连接,22,4,2,44,256,24,88,16777216,40320,nn,nn,n!,二元开关,本章内容互连网络种类动态互连网络多级网络,4 之 3,具有直通和交换两种功能的二元开关称为二功能开关，或交换开关，用一位控制信号控制。具有所有四种功能的二元开关称为四功能开关，用两位控制信号控制。,二功能开关的实现,本章内容互连网络种类动态互连网络多级网络,4 之 4,控制方式,本章内容互连网络种类动态互连网络多级网络,在多级互连网络中有多级开关模块，每一级又有多个开关模块。通常有三种控制方式：级控制 同一级开关模块使用同一个控制信号控制。单元级控制 每个开关模块分别控制。部分级控制 例如，第i级使用i+1个控制信号控制(0 i n-1)。,级间连接模式,本章内容互连网络种类动态互连网络多级网络,级间连接模式是指前一级开关模块的输出端与后一级开关模块的输入端之间的连接模式，也称为拓扑结构。通常，采用前面介绍过的互连函数实现拓扑结构。实际上，从结点的输出到第一级开关模块的输入，以及从最后一级开关模块的输出到结点的输入也可以采用拓扑结构连接。,STARAN网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0为恒等置换，C1Cn 都是逆洗牌置换；开关有两种控制方式：级控制方式（交换网络）和部分级控制方式（移数网络）。,4 之 1,A,E,I,B,F,J,C,G,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,4 之 2,STARAN交换网络,4 之 3,STARAN移数网络,4 之 4,间接二进制n方体网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0为恒等置换，C1Cn-1 都是子蝶式置换，且Ci=(i+1)，Cn为逆洗牌置换；开关采用单元控制方式。,3 之 1,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,A,E,I,B,G,J,C,F,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,3 之 2,提 示,STARAN网络和间接二进制n方体网络都是多级立方体网络，因为当第i级（0in-1）交换开关处于交换状态时实现的是Cubei函数。两个网络很相似（F、G交换位置），唯一不同之处在于：交换开关的控制方式不同，前者采用级控制和部分级控制方式，后者采用单元控制方式。,3 之 3,本章内容互连网络种类动态互连网络多级网络,Omega网络,本章内容互连网络种类动态互连网络多级网络,采用22的四功能开关，对于NN网络，有n=log2N个开关级，每级有N/2个开关；n个开关级从输入端到输出端依次为Kn-1、K1、K0，n+1个级间连接依次为Cn、C1、C0，其中C0为恒等置换，C1Cn都为均匀洗牌置换；开关采用单元控制方式。本网络也称为：多级洗牌置换网络或多级混洗网络。,3 之 1,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,3 之 2,提 示,Omega网络（网络）可看作是多级立方体网络的逆网络。级控制且开关为二功能开关 网络是STARAN交换网络的逆网络。部分级控制且开关为二功能 网络是STARAN移数网络的逆网络。单元控制且开关为二功能 网络是间接二进制n方体网络的逆网络。,本章内容互连网络种类动态互连网络,3 之 3,基准网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0 和Cn为恒等置换，C1为逆洗牌置换-1，C2 Cn-1 都是逆子洗牌置换，且Ci=-1(n-i+1)，2in-1；开关采用单元控制方式。,全排列网络,本章内容互连网络种类动态互连网络,5 之 1,在同时实现两对或多对入端和出端之间的连接时，有可能因争用数据传送通路而发生冲突的网络称为阻塞型网络。反之，将能够实现所有可能的入、出端间的连接而不发生冲突的互连网络称为非阻塞型网络或全排列网络。,阻塞型网络举例,本章内容互连网络种类动态互连网络,5 之 2,例如：在Omega网络中，如果同时进行50（JGA=101）和71（LGA=110）连接时，产生冲突，不能同时进行（见后图）；则Omega网络就是阻塞型网络。其实前面介绍的各种多级网络都是阻塞型网络。,图 示,本章内容互连网络种类动态互连网络,5 之 3,A,E,I,B,F,J,C,G,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,原因分析,本章内容互连网络种类动态互连网络,5 之 4,多级网络的排列数满足不了要求。以间接二进制n方体网络为例：该互连网络共有n=log2N级，每级N/2个交换开关，共有log2N*N/2个开关，每个开关只有直连和交换两个功能，故组合数为 2 log2N*N/2，即NN/2，小于实现N个处理单元所需N！组合数。,全排列网络的实现,本章内容互连网络种类动态互连网络,5 之 5,多次经过同一多级网络 将这种只要经过重新排列已有入出端对的连接，就可以完成所有可能的入出端间的连接而不发生冲突的互连网络称为可重排列网络。多个多级网络串联使用 例如：将多级立方体网络和它的逆网络连在一起，省去中间重复的一级后，构成的全排列网络称为Benes网络。,消息传递机制,本章内容,消息寻径方式死锁和虚拟通道流控制策略,消息寻径方式,本章内容消息传递机制,消息格式寻径方式线路交换寻径存储转发寻径虚拟直通寻径虫蚀寻径,消息格式,本章内容消息传递机制消息寻径方式,数据发送的基本形式为：消息 Message；任意长度。包 Packet；信息传送的最小单位，含路由信息及序号。片 Slice；固定大小 64512bit，可分为路由片、序号片、数据片。,2 之 1,示意图,本章内容消息传递机制消息寻径方式,2 之 2,D,D,D,D,D,D,S,R,消息,包,片,D：数据；S：序号；R：路由；,线路交换寻径（circuit switch）,本章内容消息传递机制消息寻径方式,方法 先建立一条从源结点到目的结点的物理通路，然后再传递消息。优点 实际通信时间较短，使用缓冲区少。缺点 建立源结点到目的结点的物理通路开销很大，占用物理通路的时间长。,2 之 1,传输时延,本章内容消息传递机制消息寻径方式,TCS=(LtB)DLB其中：Lt为建立路径所需小信息包的长度；L为信息包的长度；D为经过的结点数；B为带宽。,2 之 2,存储转发寻径（store and forward）,本章内容消息传递机制消息寻径方式,方法 信息流的基本单位是包，每个结点有一个包缓冲区，包从源结点经过中间结点（存储-转发）到达目的结点。优点 占用物理通路的时间比较短。缺点 包缓冲区大，时延大（与结点距离成正比）。,2 之 1,传输时延,本章内容消息传递机制消息寻径方式,TSF=(LB)D其中：L为信息包的长度；D为经过的结点数；B为带宽。,2 之 2,D,TSF,时间,N1,N2,N3,N4,L/B,头,数据,包,虚拟直通寻径（virtual cut through）,本章内容消息传递机制消息寻径方式,方法 当接收到用作寻径的包头部时，即开始路由选择，这样可以降低时延。优点 通信延迟与结点数无关。缺点 出现寻径阻塞时只能将整个包存储在寻径结点中，故结点皆需足够大的缓冲区来存储最大包。最坏情况下的通信时延同“存储转发寻径”，此时经过的每个结点都发生阻塞，都需缓冲。,2 之 1,传输时延,本章内容消息传递机制消息寻径方式,TVCT=(LhB)(D-1)+L/B其中：Lh为消息的寻径头部的长度；L为信息包的长度；D为经过的结点数；B为带宽。一般有：LLhD，通信时延可以近似为：TVCTL/B，与结点数无关。,2 之 2,D,TVCT,时间,N1,N2,N3,N4,L/B,虫蚀寻径（wormhole）,本章内容消息传递机制消息寻径方式,将包分成更小的片，在每个结点的寻径器中设置片缓冲区。用头片直接开辟一条从输入结点到输出结点的路径。每个包中的片以流水方式在网络中向前“蠕动”。当包的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择。如果所选择的通道或结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待。,4 之 1,握手协议,本章内容消息传递机制消息寻径方式,路由选择器S,路由选择器D,R/A(低),通道,(a)D已就绪可以接收一片,路由选择器S,路由选择器D,R/A(高),通道,(b)S已就绪准备发送片i,路由选择器S,路由选择器D,R/A(高),通道,(c)D接收片i,路由选择器S,路由选择器D,R/A(低),通道,(d)片i从D中移走，片i+1到达S的片缓冲区,4 之 2,传输时延,本章内容消息传递机制消息寻径方式,TWH=(LfB)(D-1)+L/B其中：Lf为片的长度；L为信息包的长度；D为经过的结点数；B为带宽。一般有：LLfD，通信时延可以近似为：TWHL/B，与结点数无关。,D,TWH,时间,N1,N2,N3,N4,L/B,4 之 3,特 点,本章内容消息传递机制消息寻径方式,虫蚀寻径的优点：每个结点的缓冲区较小；较低的网络传输时延；通道共享性好，利用率高；易于实现选播和广播通信方式；虫蚀寻径的缺点：当包的一个片被阻塞时，整个包都被阻塞，占用了结点资源。,4 之 4,虚拟通道,本章内容消息传递机制,虚拟通道是两个结点间的逻辑链路，由源结点的片缓冲区、结点间的物理通道及接收结点的片缓冲区组成。,四条虚拟通道分时共用一条物理通道,5 之 1,死锁的产生,本章内容消息传递机制,缓冲区或通道上的循环会引起死锁。下面通过两个例子进行说明：,采用存储转发寻径时 采用虫蚀寻径时,5 之 2,采用存储转发寻径时,本章内容消息传递机制死锁的产生,5 之 3,采用虫蚀寻径时,本章内容消息传递机制死锁的产生,5 之 4,死锁的避免,利用虚拟通道打破循环，可以避免死锁。每条物理通道包含两条虚拟通道（左图）。目标结点号小于源结点号走里环，目标结点号大于源结点号走外环，永远不成循环。,本章内容消息传递机制,5 之 5,流控制策略,本章内容消息传递机制,解决包冲突的策略寻径算法选播和广播寻径算法,解决包冲突的策略,本章内容消息传递机制流控制策略,包缓冲器,片缓冲区,包2,包1,输出通道,(a)用缓冲实现虚拟直通寻径,片缓冲区,与,包2,包1,输出通道,(b)阻塞流控制,控制,片缓冲区,丢弃,包1,(c)扬弃并重发,包2,输出通道,片缓冲区,绕道,包1,(d)阻塞后绕道,包2,输出通道,片缓冲区,寻径算法,本章内容消息传递机制流控制策略,寻径算法的目的是找出一条从源结点到目的结点的路径以便传送消息。寻径算法可分为两大类（都需要无死锁算法）确定寻径算法 寻找的路径是预先唯一确定的，完全根据源和目的地址确定，与网络的状况无关。自适应寻径算法 寻找的路径可能会有多条，取决于网络的状况。可采用虚拟通道避免死锁。,确定寻径算法,本章内容消息传递机制流控制策略寻径算法,例如：维序寻径，是一种在多维网络中按照维序的特定顺序来选择后继通道。维序寻径在二维网格网络中称为X-Y寻径，在三维网格网络中称为X-Y-Z寻径，维序寻径在超立方体（n维立方体）网络中称为E立方体寻径（E-cube routing）。,X-Y寻径,本章内容消息传递机制流控制策略寻径算法确定寻径算法,假定从任意源结点s=(x1,y1)到任意目的结点d=(x2,y2)，寻径从s开始，首先沿X方向前进到d所在的第x2列，然后沿Y方向一直前进到d。X-Y寻径共有四种寻址模式：东-北、东-南、西-北、西-南。例子见后图。,2 之 1,举 例,本章内容消息传递机制流控制策略寻径算法确定寻径算法,0,3,0,2,0,1,0,0,1,3,1,2,1,1,1,0,2,3,2,2,2,1,2,0,3,3,3,2,3,1,3,0,X,Y,东-北寻径模式：（2，0）（3，3）东-南寻径模式：（1，3）（2，1）西-北寻径模式：（2，1）（0，3）西-南寻径模式：（1，1）（0，0）,2 之 2,E立方体寻径,本章内容消息传递机制流控制策略寻径算法确定寻径算法,2 之 1,寻径是按照维的顺序进行的（维1维2 维n）。如果源结点和目的结点二进制编号的第i位相同，则沿维i方向不需要寻径，否则从当前结点沿着这一维方向走到其他结点，重复此过程直到到达目的结点。,举 例,本章内容消息传递机制流控制策略寻径算法确定寻径算法,2 之 2,0011,0000,0010,0110,0111,0101,0100,0001,源 结 点：s=0110目的结点：d=1101路 径：0110011101011101,6,7,3,2,0,1,5,4,1011,1000,1010,1110,1111,1101,1100,1001,14,15,11,10,8,9,13,12,利用虚拟通道避免死锁的自适应X-Y寻径（在Y维上用了2对虚拟通道）,2 之 1,利用虚拟通道避免死锁的自适应X-Y寻径（在X和Y维上各用了2对虚拟通道）,2 之 2,通信模式,本章内容消息传递机制流控制策略,多计算机网络中会出现四种通信模式：单播（unicast）模式 一对一的通信方式。选播（multicast）模式 一对多的通信方式。广播（broadcast）模式 一对全体的通信方式。会议（conference）模式 多对多的通信方式。,4 之 1,通信效率,本章内容消息传递机制流控制策略,描述通信效率常用有两个参数：通道流量 可用传输有关信息所使用的通道数来表示。通信时延 用包的最长传输时间来表示。提示：优化的寻径网络应能以最小流量和最小时延实现有关通信模式。,4 之 2,在网格网络中实现选播和广播,4 之 3,在n方体网络中实现选播和广播,4 之 4,