哈工大并行计算课件第六章

第6章系统的互联和千兆位网络

1系统互连基础

2静态连接网络

3动态连接网络

4消息传递机制

5千兆位网络技术

6ATM交换器和网络哈尔滨工业大学计算机科学与技术学院

1

系统互连基础一.网络的分类方式静态网络动态网络哈尔滨工业大学计算机科学与技术学院二.网络特性和寻径功能1.结点度包括出度和入度2.网络直径3.等分宽度当某一网络被切成相等的两半时，沿切口的最小边数(通道)哈尔滨工业大学计算机科学与技术学院4.数据寻径功能

数据寻径网络用来进行PE间数据交换。

通常见到的PE之间的数据寻径功能有移数(shifting)、循环(rotation)、置换(一对一)、广播(一对全体)、选播(多对多)、个人通信(一对多)、洗牌、交换等。哈尔滨工业大学计算机科学与技术学院5.置换对n个对象来说，有n！种置换，n个对象可照此重新排序。整个置换集合形成一个与复合运算有关的置换群。可以用轮换方法来描述置换功能。哈尔滨工业大学计算机科学与技术学院例如，置换

＝(a，b，c)(d，e)即是以轮换形式表示的置换映射。(d，e)循环周期为2。哈尔滨工业大学计算机科学与技术学院三.互连函数（一）基本概念除了上述的置换表示，还有函数表示。1.互连函数：表示相互连接的输出端号和输入端号之间的一一对应关系。哈尔滨工业大学计算机科学与技术学院互连函数有时可表示成为置换函数或排列函数。函数表示法用x表示输入端变量，用f(x)表示互连函数。x还常用n位二进制形式来表示:写成xn-1，xn-2…x1x0。互连函数则对应地表示为:f(xn-1，xn-2…x1x0)。哈尔滨工业大学计算机科学与技术学院2.输入输出对应表示法

优点：更直观哈尔滨工业大学计算机科学与技术学院（二）常用的基本互连函数和特征1．恒等置换相同编号的输入端与输出端一一对应互连所实现的置换。f(xn-1，xn-2…x1x0)=xn-1xn-2…x1x0哈尔滨工业大学计算机科学与技术学院2.交换置换哈尔滨工业大学计算机科学与技术学院3．方体置换是实现二进制地址编号中第k位位值不同的输入端和输出端之间的连接。其表达式为：哈尔滨工业大学计算机科学与技术学院如以N=8为例。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院4．均匀洗牌置换均匀洗牌置换将输入端分成数目相等的两半，前一半和后一半按序一个隔一个地从头至尾依次与输出端相连。这好比洗扑克牌时，将整副牌分成相等的两叠来洗，以达到理想的一张隔一张的均匀情况，故称为均匀洗牌置换，或简称为洗牌置换。哈尔滨工业大学计算机科学与技术学院其函数关系可表示为：由此表达式可见，洗牌变换是将输入端二进制地址循环左移一位即得到对应的输出端二进制地址。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院还可以定义:子洗牌超洗牌:哈尔滨工业大学计算机科学与技术学院逆均匀洗牌是均匀洗牌的逆函数，其函数表达式为：哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院5.蝶式置换蝶式置换的名称源于FFT变换的实现时其图形的形状如蝴蝶式样。哈尔滨工业大学计算机科学与技术学院可定义子蝶式:超蝶式哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院6.位序颠倒置换位序颠倒置换是将输入端二进制地址的位序颠倒过来求得相应输出的地址。其表达:(k)(xn-1xn-2…x1x0)=x0x1…xn-1哈尔滨工业大学计算机科学与技术学院7．移数置换移数置换是将输入端数组循环移动一定的位置向输出端传输。其函数表示式无需用二进制编号来写，可表达如下：d(X)＝(X+k)modN，0≤X≤Nk为常数，指移过的位置值，也可以将整个输入数组分成若干个子数组。哈尔滨工业大学计算机科学与技术学院三、网络性能(1)功能特性——这指的是网络如何支持数据寻径、中断处理、同步、请求／消息组合和一致性。(2)网络时延——这是指单位消息通过网络传送时，最坏情况下的时间延迟。(3)带宽——这是指通过网络的最大数据传输率，用M字节／秒表示。哈尔滨工业大学计算机科学与技术学院(4)硬件复杂性——这是指诸如导线、开关、连接器、仲裁和接口逻辑等的造价。(5)可扩展性——这是指在增加机器资源使性能可扩展的情况下，网络具备模块化可扩展的能力。

哈尔滨工业大学计算机科学与技术学院

2静态连接网络静态网络的基本概念1.线性阵列

内部结点度直径等分宽度b＝1。

哈尔滨工业大学计算机科学与技术学院2.环和带弦环结点度是常数直径双向环单向环

哈尔滨工业大学计算机科学与技术学院带弦环可以提高结点度减小直径哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3.循环移数网络一个循环移数网络，其结点数N＝16，它是将环上每个结点到与其距离为2整数幂的结点之间增加一条附加链而构成的。哈尔滨工业大学计算机科学与技术学院结点度：网络直径：哈尔滨工业大学计算机科学与技术学院4.树形和星形（1）树形：结点数一棵k层完全平衡的二叉树应有N＝2k-1个结点。最大结点度直径二叉树是一种可扩展的系统结构由于结点度是常数，但其直径相当长。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院（2）星形如上图所示直径结点数哈尔滨工业大学计算机科学与技术学院5.胖树形1985年Leiserson提出将计算机科学中所用的一般树结构修改为胖树形(fattree)。二叉胖树结构的通道宽度从叶结点往根结点上行方向逐渐增宽，它更象真实的树，其向树根方向的枝叉变得愈来愈粗。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院解决了使用传统二叉树的主要问题；CM—5已采用胖树结构；胖树体系结构在ConnectionMachine的CM-5系统中实现。CM5采用4叉胖树来构造数据网络，允许每个结点有4个子结点和2个或4个父结点。还可将二叉胖树的思想推广到多路胖树。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院6.网格形和环网形(1)3X3网格如下图所示：这是一种比较流行的结构，它已以各种变体形式在ILLiac4、MPP、DAP、CM-2和IntelParagon中得到了实现。N＝nk结点的k维网格的内部结点度为2k；可知边界点度和角节点度；网格直径为k(n-1)。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院(2)Illiac4网格是一种可回绕连接的网格图，如上图所示。假定Illiac4系统采用8X8的这种Illiac网格，则其结点度为常数4，直径为7。N＝16＝4X4构型的Illiac网格与图所示的结点度为4的带弦环在拓扑上是等效的。一般说来，一个nXn的Illiac网格的直径应为d＝n-1，它仅为纯网格直径的一半。哈尔滨工业大学计算机科学与技术学院(3)环网形上图所示,可看做是另一种直径更短的网格。这种拓扑结构将环形和网格组合在一起，并能向高维扩展。环网形沿阵列每行每列都有环形连接。一个n×n二元环网的结点度为4，直径为2[n／2]。环网是一种对称的拓扑结构，所有附加的回绕连接可使其直径较之网格结构减少1/2。哈尔滨工业大学计算机科学与技术学院7.搏动式阵列

这是一类为实现确定算法而设计的多维流水线阵列结构。上图所示就是为完成矩阵--矩阵相乘而专门设计的搏动式阵列。此例的内部结点度为6。静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作。商用IntelWarp系统(Anaratone等，1986)就是用搏动式结构设计而成的。自从1978年Kung和Leiserson提出搏动式阵列后，它已成为广泛研究的领域。哈尔滨工业大学计算机科学与技术学院通过确定的互连和同步操作，搏动式阵列可与算法的通信结构相匹配。针对信号/图象处理等特殊应用，可提供更好的性能／价格比。缺点：其结构的实用性有限，而且编程难。有兴趣的读者可参考S．Y．Kung(1988)关于用搏动式和波前沿结构实现VLSI阵列处理机的专著。哈尔滨工业大学计算机科学与技术学院8.超立方体

这是一种二元n-立方体结构，它已在iPSC、nCUBE和CM-2系统中得到实现。一个n-立方体由N＝2n个结点组成，它们分布在n维上，每维有两个结点。8个结点的3-立方体如下图所示。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院9.带环立方体这种结构是从超立方体改进而来的。如下图所示，一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替。

哈尔滨工业大学计算机科学与技术学院可以从一个k-立方体构成一个有n＝2k个结点环的带环k—立方体；如下图所示，所用的办法是用k个结点的环取代k维超立方体的每个顶角。一个k—立方体可变为kX2k个结点的k-CCC。哈尔滨工业大学计算机科学与技术学院如图所示3-CCC的直径为6，比原来3-立方体的直径大一倍。一般说来，k-CCC的网络直径2k，CCC的主要改进之处即在其结点度为常数3，与超立方体的维数无关。假设一超立方体有N=2n结点。一个有同样N结点数的CCC一定是由低维k—立方体组成，即2n＝k·2k，其中k<n。哈尔滨工业大学计算机科学与技术学院例题：对应于n＝6和k=4的情况；一个64结点的CCC可用4结点的环取代4—立方体的角结点组成。CCC的直径为2k＝8；比6-立方体的6要长些。CCC的结点度为3，比6-立方体的结点度6要小。如果容许一定的时延，则CCC是一种构造可扩展系统的较好的结构。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院10.k元n-立方体网络环形、网格形、环网形、二元n-立方体(超立方体)和Ω网络都是k元n-立方体网络系列的拓扑同构体。下图所示是一种4元3-立方体网络。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院参数n是立方体的维数，k是基数或者说是沿每个方向的结点数(多重性)。这两个数与网络中结点数N的关系为：N＝kn，(k=N1/n，n＝logkN)哈尔滨工业大学计算机科学与技术学院k元n-立方体的结点可用基数为k的n位地址；A＝a0a1a2…an来表示，其中ai代表第i维结点的位置。为简单起见，所有链路都认为是双向的。各结点之间的连线都是双向链路。哈尔滨工业大学计算机科学与技术学院低维k元n-立方体称为环网；而高维二元n-立方体则称为超立方体。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院总结：大多数网络的结点度都小于4，这是比较理想的。网络直径的变化范围很大，直径已不是一个严重问题。链路数会影响网络价格，等分宽度将影响网络的带宽。对称性会影响可扩展性和寻径效率。客观地说，网络的总价格随节点度和链路度增大而上升。直径小仍然是一种优点。结点间的平均距离可能是一种更好的量度指标。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院第6章系统的互联和千兆位网络

1互连网络基础

2静态连接网络

3动态连接网络

4消息传递机制

5千兆位网络技术

6ATM交换器和网络哈尔滨工业大学计算机科学与技术学院

3动态连接网络目的和种类：按照价格和性能增加的顺序，动态连接网络的排队次序为：多处理机的总线；交叉开关网络。多级互连网络(MIN)；哈尔滨工业大学计算机科学与技术学院动态网络的性能：可用网络带宽通过网络的最大数据传输率，用M字节／秒表示数据传输速率网络时延单位消息通过网络传送时最坏情况下的时间延迟

所用的通信模式哈尔滨工业大学计算机科学与技术学院一.多处理机的总线定义：特点：数字总线已被称为多个功能模块间的争用总线(contentionbus)或时分总线(time-sharingbus)。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院二.开关模块1.一个a×b开关模块有a个输入和b个输出。一个二元开关则与a＝b＝2的2X2开关模块相对应哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2X2交叉开关可有两种连接模式：直送交叉哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4X4的交叉开关的模块哈尔滨工业大学计算机科学与技术学院3.交叉开关网络

特点：交叉开关网络的带宽和互连特性最好。可看作是一个单级开关网络。交叉点开关能在对偶(源、目的)之间形成动态连接，每个交叉点开关在对偶间提供一条专用连接通路，开关可根据程序的要求动态地设置“开”或“关”。哈尔滨工业大学计算机科学与技术学院例题：下图所示两种交叉开关网络(1)C.mmp多处理机可以在处理机和存储模块之间用交叉开关网络构成一个共享存储型多处理机，实际上这是一个存储器访问网络C.mmp多处理机已实现了一个16X16交叉开关网络哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院(2)Fujitsu公司(1992)制造的向量并行处理机还有一种交叉开关网络可用于处理机间通信，如下图所示。(VPP500)实际上就是采用了这种大型交叉开关网络(224X224)其中PE为接有存储器的处理机，CP代表控制处理机，用来监控整个系统，包括交叉开关网络的运行。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院交叉开关网络的局限性每台处理机可以向多个存储模块发出请求。n×n的交叉开关网络在每个存储周期最多可为n台处理机发送n个存储字。交叉开关网络每个存储周期可以实现n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。由于所有必要的开关和解决冲突的逻辑都做在交叉点开关中，所以处理机接口和存储器端口的逻辑就变得比较简单，因而也比较便宜。哈尔滨工业大学计算机科学与技术学院交叉开关网络对只有几台处理机访问几个存储器模块的小型多处理机系统来说性能价格比比较高。单级交叉开关网络一旦构成后将不能扩充冗余或奇偶校验线可以做在每个交叉点开关中，以便增强交叉开关网络的容错性和可靠性除了用电子元件构造交叉开关网络外，科研机构正在研究用光电元件构造较大较快的网络。哈尔滨工业大学计算机科学与技术学院三.多级网络

一种通用多级网络如下图所示；各种MIN的区别就在于：所用开关模块和级间连接(ISC)模式的不同。最简单的开关模块是2×2开关。常用的ISC模式包括有均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院四.Ω网络1.Ω网络的构造下图所示的是一个16×16Ω网络，共需4级2×2开关。网络左侧有16个输入，右侧有16个输出ISC是对16个对象的均匀洗牌模式

哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院一个n输入的Ω网络需要log2n级2X2开关，每级要用n／2个开关模块，Ω网络共需nlog2n／2个开关。每个开关模块采用单元控制方式。不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接哈尔滨工业大学计算机科学与技术学院2.Ω网络寻径控制8个输入端的Omega网络如下图所示。通常，n个输入端的Omega网络有logan级(开关输入a个）从输入级到输出级依次编号为:0到log2n-1哈尔滨工业大学计算机科学与技术学院控制方法:目的地址控制法;通过检查二进制目的地址编码来控制数据路径。目的地址编码从高位开始的第i位为0时，第i级的2X2开关的输入端与上输出端连接否则输入端与下输出端连接。哈尔滨工业大学计算机科学与技术学院例题：下图的开关设置对应于置换

1=(0，7，6，4，2)(1，3)(5)中的开关设置，

1的映射为0—7，7—6，6—4，4—2，2—0，1—3，3—1，5—5。观察一个消息从输入端001到输出端011的路径。它使用了开关A、B和C。实现

1的置换所要求的开关设置，不存在冲突。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院置换

2＝(0，6，4，7，3)(1，5)(2)。现在再来考察8个输入端口的Omega网络实现置换

2的情况。开关F、G和H的设置发生了冲突哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院F冲突---由000→110和100→111引起；G冲突---由011→000和111→011引起；H冲突---由101→001和011→000引起哈尔滨工业大学计算机科学与技术学院Omega网络是一种阻塞网络。当出现阻塞时，可以采用几次通过的方法解决冲突。例如

2

，在第一次通过时实现连接000—110，001→101，010→010，101→001，110→100。在第二次通过时实现连接011→000，100→111，111→011。哈尔滨工业大学计算机科学与技术学院讨论：如果采用2X2开关元件，n个输入端Omega网络一次通过可以实现nn／2个置换，但总共有n!个置换。n个输入端的Omega网络一次通过只能实现全部置换的nn／2/n!一般来说，n个输入端的Omega网络实现非阻塞连接最多需要通过的次数为log2n。在任何多级网络中都不希望出现阻塞，阻塞将降低有效频宽。哈尔滨工业大学计算机科学与技术学院例题：n＝8时：8个输入端的Omega网络一次通过只能实现全部置换的10．16％，即84／8！＝4096／40320＝0．1016＝10．16％。所有其它置换将引起阻塞。实现这些置换需要三次通过。哈尔滨工业大学计算机科学与技术学院例题如下图所示，采用上播或下播开关设置，Omega网络也可以从一个源将数据广播给多个目的地。在输人端001的消息通过二进制树的连接广播到所有8个输出端。

哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例题：下图是用4X4开关元件作为构成块的Omega网络，级间是4路洗牌连接，而不是2路洗牌连接。16个输入端的Omega网络的级数为:log416＝2哈尔滨工业大学计算机科学与技术学院4路洗牌相当于把16个输人端平均地分成4个子组，然后4个子组均匀地洗牌。当采用是kXk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的Omega网络。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院五.基准网络

Wu和Feng(1980)研究过多级互连网络之间的关系。基准网络可如下图所示递归生成。第一级为一个N×N模块；第二级为两个(N／2)X(N／2)子模块，以C0和C1表示。以上构成方法可递归用于子模块，直至得到2×2的N／2子模块为止。每个块有两个合法状态：两个输出和输入的直送和交叉。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院总结：总线的造价最低其缺点是每台处理机可用的带宽较窄。总线所存在的另一个问题是容易产生故障。交叉开关硬件复杂性以n2上升，所以其造价最为昂贵。但是，交叉开关的带宽和寻径性能最好。如网络的规模较小，它是一种理想的选择。哈尔滨工业大学计算机科学与技术学院多级网络：则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网络的级数log2n而上升。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院第6章系统的互联和千兆位网络

1互连网络基础

2静态连接网络

3动态连接网络

4消息传递机制

5千兆位网络技术

6ATM交换器和网络哈尔滨工业大学计算机科学与技术学院

4消息传递机制主要研究：存储转发；虫蚀寻径方法；它们的通信时延问题；针对无死锁的消息寻径确定的寻径算法和自适应两种寻径算法。哈尔滨工业大学计算机科学与技术学院一、

消息寻径方式1.消息的格式（1）消息(message)是结点间通信的逻辑单位，它常常由任意数目的长度固定的包组成，因此它的长度是可变的。在消息传递网络中通信的信息单位是：消息、包和片的格式。消息寻径中的信息单位如下图所示。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院（2）包(packet)是含寻径目的地址的基本单位；每个包需要一个序号；不同的包可能异步地到达目的结点，以便把传送的消息重新装配起来。在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位。哈尔滨工业大学计算机科学与技术学院包的长度取决于寻径方式和网络的实现方法。典型的包长度为64--512位。序号可能占用1--2个片，取决于消息的长度。包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关。哈尔滨工业大学计算机科学与技术学院（3）片：包可分成一些固定长度的数据片。寻径信息(目的地址)和序号形成头片，其余的片是数据。在采用虫蚀寻径网络的多计算机中，包可进一步分成片。片的长度往往受网络大小的影响，256个结点的网络需要片长为8位。哈尔滨工业大学计算机科学与技术学院2.存储转发寻径定义：下图说明了这一概念。在存储转发网络中包是信息流的基本单位。存储转发网络的时延与源和目的之间的距离(段数)成正比。第一代多计算机系统采用这种寻径方式。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3.虫蚀寻径新型的计算机系统都采用虫蚀寻径方式，把包进一步分成更小的片；与结点相连的硬件寻径器中有片缓冲区。消息从源结点传送到目的结点要经过一系列寻径器。同一个包中所有的片，象不可分离的同伴一样以流水方式顺序地传送。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院特点：所有数据片必须跟着头片。不同的包可交替地传送，但不同包的片不能交叉。否则它们可能被送到错误的目的地。虫蚀寻径的时延几乎与源和目的之间的距离无关。哈尔滨工业大学计算机科学与技术学院4.异步流水采用如下图所示的握手协议，可以实现一个包内相继片的异步流水运行。异步流水的效率很高，所用的时钟比同步流水的时钟快，如果路径中的片、缓冲片或后继通道在某个周期不能使用的话，则流水线将出现阻塞。如果出现这种情况，则包可能要缓冲、阻塞、延缓或绕道通过。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院5.时延分析下图是包通过存储转发网络和虫蚀网络的时间比较情况其中：L是包的长度(位)W是通道频宽(位／秒)D是距离(经过的结点数-1)F是片的长度(位)哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院存储寻径网络的通信时延TSF可表示为：TSF＝L／W×(D+1)虫蚀寻径TWH：TWH

＝L／W+F／W×D显然：TSF与D成正比；如果L》F，那么TWH=L／W，距离D对寻径延时的影响可忽略不计。哈尔滨工业大学计算机科学与技术学院典型的TSF值约在2000至6000

s之间，而典型的TWH值只有5

s或者更小。存储转发寻径往往由软件控制，而虫蚀寻径则完全用硬件寻径器以流水方式工作。哈尔滨工业大学计算机科学与技术学院二、死锁和虚拟通道1.虚拟通道虚拟通道是两个结点间的逻辑链，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。下图说明了四条虚拟通道共享一条物理通道的概念。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院通道的特点：两个端点增加了缓冲区和用来控制虚拟通道状态的R／A线。实现虚拟通道需要用交叉开关控制、多路选择器和多路分配器。物理通道由所有的虚拟通道分时地共享。以片传递为基础的分时方法可使一组虚拟通道共享一条物理通道。用某些通道状态(如R／A信号)来表示不同的虚拟通道，控制源缓冲区存放等待使用通道片。通道(电缆或光纤)是它们之间的通信媒介哈尔滨工业大学计算机科学与技术学院例题

通道上的循环等待引起的死锁如下图所示，有两类死锁是由缓冲区或通道上的循环等待引起的。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院如下图采用虫蚀寻径的网格形网络中，四条消息沿四个通道同时传送也会产生通道死锁(channeldeadlock)

4个消息的4个片同时占用了4个通道。如果循环中没有一个通道被释放，死锁状态将持续下去哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.死锁的避免通过增加两条虚拟通道V3和V4，可以打破死锁循环。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院双向通道与单项通道的实现比较虚拟通道可以用单向通道或者双向通道实现。把两条单向通道组合可以构成一条双向通道；双向通道中的仲裁要复杂一点。单向通道相比较，双向通道由于要做方向仲裁，因而增加了延迟，又由于控制复杂，因而还增加了成本。网络的流量不大时，双向通道效率比较高。确定虚拟通道数目时，需要对网络吞吐量和通信时延折衷考虑。实现数目很大的虚拟通道需要用高速的多路选择开关。哈尔滨工业大学计算机科学与技术学院三、流控制策略1.问题的提出：当两个或更多的包在某个结点为竞争缓冲区或通道资源而发生冲突时，必须确定如何解决冲突的策略。针对一对一通信寻径算法和自适应寻径算法进行讨论。哈尔滨工业大学计算机科学与技术学院2.包冲突的解决

必须具备三个条件：(1)源缓冲区已存有该片；(2)通道已分配好；(3)接收缓冲区准备接收该片哈尔滨工业大学计算机科学与技术学院另外还存在：当两个包到达同一个结点时，它们可能会请求用同一个接收缓冲区或者要用同一个输出通道，因此必须对两个问题做出仲裁：(1)把通道分配给哪个包?(2)没有分配到通道的包做什么事?哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3.两个包争用的主要解决方法：虚拟直通寻径缓冲方法虚拟直通方法是存储转发和虫蚀两种寻径方法的折衷。当不发生冲突时，就如同虫蚀寻径方法一样工作，效果与存储转发寻径方法相同。阻塞策略虫蚀寻径在出现冲突时就采用阻塞策略。第2个包被阻塞不再前进，但并没有被扬弃。某些多计算机网络综合了以上某些流控制策略的优点，采用混合策略。哈尔滨工业大学计算机科学与技术学院4.维序寻径包寻径可以归结为确定和自适应两类。确定寻径通信路径完全由源和目的地址确定。维序寻径需要一种按照多维网络维序的特定顺序来选择后继通道。在二维网格网络中称为X—Y寻径，首先沿着X维方向确定路径，然后沿着Y维方向选择路径。代表是E立方体寻径(E—cuberouting)方法哈尔滨工业大学计算机科学与技术学院超立方体网络的E立方体寻径

假设有一N＝2n个结点的n方体。每个结点的二进制编码为:b＝bn-1bn-2…b1b0。源结点为s＝sn-1ssn-2…s1s0目的结点d＝dn-1sdn-2…d1d0要确定一条从s到d的步数最小的路径。哈尔滨工业大学计算机科学与技术学院将n维表示成i＝1，2，…n，其中第i维对应于结点地址中的第i-1位。设v=vn-1vn-2…v1v0是路径中的任一结点。路径可以根据以下方法唯一地确定。①计算方向位ri＝si-1

di-1，其中i＝1，2，…，n。使i＝1，v＝s，开始以下步骤。哈尔滨工业大学计算机科学与技术学院②如果ri=1，则从当前结点v寻径到下一结点：v

2i-1。如果ri=0则跳过这步；③i

i+1。如果i≤n，则转第2步，否则退出。哈尔滨工业大学计算机科学与技术学院例题4维超立方体网络的正方体寻径n＝4，s＝0110，d＝1101，因而r＝r4r3r2r1＝1011。由于r1＝0

1＝1，因此s就寻径到s

20＝0111。由于r2＝1

0＝1，因此v＝0111就寻径到v

21＝0101。由于r3＝1

1＝0，因此就可以跳过维i＝3这一步。由于r4＝1，因此v＝0101就寻径到v

23＝1101＝d。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院5.二维网格网络的X-Y寻径X-Y寻径共有四种模式。东—北、东—南、西—北和西—南的路径方向假定从任意源结点s＝(x1,y1)到任意目的结点d＝(x2,y2);寻径从s开始，首先沿x方向前进一直到d所在的第y2列为止，然后沿y方向前进直到d。

哈尔滨工业大学计算机科学与技术学院例题：二维网格连接多计算机的X—Y寻径下图中有4个(源，目的)对，可用以说明二维网格的4种寻径模式。从结点(2，1)到结点(7，6)需要一条东—北路径。从结点(0，7)到结点(4，2)要建立一条东—南路径。从结点(5，4)到结点(2，0)需要一条西—南路径。从结点(6，3)到结点(1，5)需要一条西—北方向路径。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院6.自适应寻径方法

采用自适应寻径的主要目的是避免死锁。采用的方法--虚拟通道哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例题使用虚拟通道的自适应X-Y寻径这是一个用X—Y寻径的网格网络示例，在Y维上用了2对虚拟通道。哈尔滨工业大学计算机科学与技术学院四、选播寻径算法1.通信模式多计算机网络中可能会出现四类通信模式一个源结点和一个目的结点的一对一的单播(Unicast)模式哈尔滨工业大学计算机科学与技术学院选播(Multicast)模式：对应于一到多的通信情况，即一个源结点发送同一个消息到多个目的结点。广播(Broadcast)模式：对应于一到全体的通信情况。会议(Conference)模式是多到多的通信。实现这些多目的模式必须使用特殊的硬件或寻径方法。哈尔滨工业大学计算机科学与技术学院2.寻径效率常用的两个参数是通道流量和通信时延。通道流量：任何时刻的传输有关消息所使用的通道数来表示。通信时延：包的最长传输时间来表示。优化的寻径网络应能以最小流量和最小时延实现有关通信模式。在存储转发网络中时延是最重要的问题；在虫蚀寻径网络中流量对效率的影响更大。哈尔滨工业大学计算机科学与技术学院例题网格连接计算机中的选播和广播

下图是在3X3网格上实现的选播寻径。源结点用S表示，传送一个包到标号为n的s个目的结点。这里，i＝1，2，…，5。目的为5个的选播可以用5次单播来实现，如下图所示。X-Y寻径的流量需要用1+3+4+3+2=13条通道，到D3的路径最长，所以时延是4。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例题超立方体计算机上选播和广播

为在n方体上实现广播，可用类似的生成树时延不超过n就能到达所有结点。下图是一个根结点为0000的4-立方体。超立方体广播树的流量最小。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院可以得到一棵贪婪选播树，可从结点0101发送包到7个目的结点。这个贪婪选播算法的基本思想是向那些可达最多剩余目的结点的维方向发送包。从源结点S＝0101开始，由维2方向可以到达2个目的结点，由维4方向可以到达5个目的结点。哈尔滨工业大学计算机科学与技术学院第一层所用的通道是0101

0111和0101

1101。从结点1101，由维2方向可以到达3个目的结点，由维1方向可以到达4个目的结点。第二层所用的通道是1101

1111，1101

1100和0111

0110。第三层所用的通道是1111

1110，1111

1011，1100-1000和0110-0010。第四层所用的通道是1110

1010。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院所生成的树不是唯一的在扩充选播树时，首先应该比较所有各维方向的可达性(reachability)，然后选择某些维使剩余目的结点的集合最小。两维之间有连线，那么选择其中任何一维都可以。已经证明贪婪选播算法所需的通道数与多次单播或广播树相比要少。在虫蚀寻径网络中，实现选播操作时，每个结点的寻径器应有复制片缓冲区中数据的能力。为了与选播树或广播树的增长同步，树中同一层的所有输出通道必须在传输向前推进一层之前处于就绪状态，否则中间结点需要增加缓冲区。哈尔滨工业大学计算机科学与技术学院第6章系统互联和千兆位网络

1互连网络基础

2静态连接网络

3动态连接网络

4消息传递机制

5千兆位网络技术

6ATM交换器和网络哈尔滨工业大学计算机科学与技术学院

5千兆位网络技术一、问题的提出1.机群系统如下图哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院1.机群系统5个体系结构概念融为一个机群，它是全体计算机(结点)的互连集。这些互连的计算机能集体地工作，尤如一个单一系统，以提供不会被中断(可用性)和有效的(性能)服务。哈尔滨工业大学计算机科学与技术学院解释：机群是全体计算机(结点)的集合，这些计算机由高性能网络或局域网(LAN)物理地互连典型情况下，每个计算机结点是一台SMP服务器、一台工作站或是一台PC计算机所有机群结点必须能一起集体工作，如同一个单一集成的计算资源，除了满足由交互用户单独地使用每个结点的协定任务之外哈尔滨工业大学计算机科学与技术学院2.特征计算机机群特征（一）COW的每个结点是一个完整工作站，但没有某些外围设备(如监视器、键盘、鼠标等)。有时称这类结点为“无头工作站”。一个结点也可以是一台SMP或是一台PC。结点通过低廉的商品化网络，如以太网、FDDI、光通道和ATM开关实现互连，虽然在某些商用机群中也使用专用网络。哈尔滨工业大学计算机科学与技术学院计算机机群特征（二）网络接口与结点中的I/O总线松耦合相连。与此相反，MPP中则用紧耦合网络接口,它与处理结点的存储器总线连接。总有一个局部磁盘，而在MPP结点中可能没有在每个结点上驻留有完整的操作系统，而在某些MPP的结点中只有操作系统的微核哈尔滨工业大学计算机科学与技术学院总之：COW的操作系统是相同的工作站UNIX，加上一个附加软件层以支持单一系统映像、可用性、并行性、通信以及负载平衡现在MPP和COW之间的界限正变得日益模糊。IBMSP2被认为是一个MPP。但除了用作通信网络的专用高性能开关之外，它是机群体系结构与MPP相比，机群具有许多成本/性能优点。机群化正成为开发可扩展并行计算机的趋向。哈尔滨工业大学计算机科学与技术学院二、千兆位的光纤通道和FDDI环……哈尔滨工业大学计算机科学与技术学院

6ATM交换器和网络异步传输模式(ATM)由ATM论坛(成立于1991年)和ITU标准定义。大多数计算机公司都有它们的ATM组网技术以支持企业和局域网。哈尔滨工业大学计算机科学与技术学院一、ATM技术ATM是一种独立于介质的消息传输协议，它将消息段传输转变成更短的固定长度为53字节的报元传输。这种技术是基于片交换机制。ATM的目的是将实时(也就是延时敏感的)和突发数据(也就是非延时敏感的)两个方面的传输变成统一的网络技术。哈尔滨工业大学计算机科学与技术学院1.ATM报元格式如图所示，长报文在传输经过ATM网络之前，必须分成多个报元。使用小报元、虚路径和虚通道使