《计算机系统机构 ppt 第7章课件.ppt》由会员分享，可在线阅读，更多相关《计算机系统机构 ppt 第7章课件.ppt（124页珍藏版）》请在三一办公上搜索。
1、1,计算机系统结构,第一章 基本概念第二章 指令系统第三章 存储系统第四章 输入输出系统第五章 标量处理机第六章 向量处理机第七章 互连网络第八章 并行处理机第九章 多处理机,2,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接,第七章 互连网络,3,第七章 互连网络,互连网络的基本概念消息传递机制,4,7.1 互连网络的基本概念,互连网络的作用互连函数互连网络的特性和传输的性能参数互连网络的种类,5,7.1.1互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。为并行处理系统的核心组成部分。对
2、整个计算机系统的性能价格比有着决定性的影响。,6,具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构IPMN(处理机-存储器网络)PION(处理机-I/O网络)IPCN (处理机之间通信网络)P(处理机) C(高速缓冲存储器)SM(共享存储器) LM(本地存储器),7,7.1.2互连函数,互连函数将互连网的N个输入和N个输出端分别用整数(0, 1, 2, ., N-1)来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系表示方法：互连函数法，图形表示法, 输入输出对应表示法函数表示法：x表示输入端号，常用n位二进制形式表示 xn-1xn-2.x1x0f(x
3、)表示互连函数，为：f(xn-1xn-2.x1x0 )图形表示法: 用图形表示输入和输出端之间的连接输入输出对应(矩阵)表示法：循环表示法: 把互连函数f(x)表示为：(x0，x1，.，xj) (xk，xk+1，.，xl) .表示对应关系为: f(x0)=x1，f(x1)=x2，.，f(xj)=x0 j+1称为该循环的长度,8,常用的互连函数如下：,1 恒等置换： I( xn-1xn-2 . x1x0 )= xn-1xn-2 .x1x0,9,2 交换置换Exchange,实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。 E(xn-1xn-2 . x1x0 )= xn-1xn-2 .
4、 x1x0 其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换,10,3、方体置换Cube,当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。用交换函数构成的互连网络的结点度为n，网络直径也为n。,11,变化发生在 0，1，2位分别是高 2，1，0位相同的为一个组组内加/减 1，2，4,12,4、均匀洗牌置换Perfect shuffle,把二进制结点循环左移一位。子混洗(subshuffle)S(k) 最低k位循环左移一
5、位超混洗牌(supershuffle) S(k) 最高k位循环左移一位显然成立：逆混洗函数：教材P397L2,3,6错,13,4、均匀洗牌置换Perfect shuffle,子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2) 分两组0，1，2，3；4，5，6，7只用均匀洗牌函数不能实现任意结点之间的互连通常用均匀洗牌函数与其他函数，如交换函数一起构成互连网络。均匀洗牌与逆均匀洗牌是两种十分有用的互连函数以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega()网络与逆Omega(-1)网络。逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换,14,5、蝶
6、式置换Butterfly,蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly) B(k)最低k位的最高位与最低位互换位置超蝶式(superbutterfly) B(k)最高k位的最高位与最低位互换位置显然成立教材P398L1,2错,15,5、蝶式置换Butterfly,与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。,16,6、位序颠倒置换Bit Reversal,将输入端二进制地址的位序反过来就得相应输出的地址。子反位序函数：最低k位的位序反过来超反位序函数：最高k位的位序反过来对于n=3的情况，正好
7、有 R=B，R(2)=B(2)，R(2)=B(2)。,17,7、移数置换,将输入端数组循环移动一定的位置向输出端传输。也可以将整个输入数组分成若干个子数组，在子数组内进行循环移数置换，这种段内循环移数的表达式可写成为两个式子如下： (a)移数量换k=2 (b)段内移数置换k=1,r=2,18,8、加减2i置换,其中：0 x N-1，0 i n-1，n = log2 N。,19,8、加减2i置换,通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。例如，Illiac函数是构成Illiac IV阵列的基础，它包含PM20和PM2n/2等四个互连函数。采用全部移数函数
8、构成网络称为移数网，移数网的结点度d=2n-1，网络直径D=n/2,20,7.1.3互连网络的特性和传输的性能参数,1 互连网络的特性互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有(1) 网络规模：网络中结点的个数(2) 结点度：与结点相连接的边数称为结点度。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度(3) 距离：两个结点之间相连的最少边数(4) 网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示,21,7.1.3互连网络的特性和传输的性能参数,(5) 等分宽度：当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度
9、，用b表示。于是线等分宽度就是B=bw，w为通道宽度(用位表示)。等分宽度是说明沿等分网络最大通信带宽的一个参数。网络的所有其它横截面都应限在等分宽度之内。(6) 结点间的线长：两个结点间连线的长度。用米、公里等表示(7) 对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。,22,2 互连网络传输的性能参数,一台机器发送消息给另一台机器时，发送方的步骤如下：(1) 用户程序把要发送的数据拷贝到操作系统的缓冲区。(2) 操作系统把缓冲区中的数据打包，并发送的网络接口部件。(3) 网络接口硬件开始发送消息。数据包的接收步骤如下：(1) 把数据包从网络接口部
10、件拷贝到操作系统缓冲区。(2) 检查收到的数据包，如果正确，给接收方发回答信号。(3) 把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区,23,互连网络在传输方面的主要性能参数,(1) 频带宽度(Bandwidth)：互连网络传输信息的最大速率(2) 传输时间(Transmission time)：等于消息长度除以频宽(3) 飞行时间(Time of flight)：第一位信息到达接收方所花费的时间(4) 传输时延(Transport latency)：等于飞行时间与传输时间之和(5) 发送方开销(Sender overhead)：处理器把消息放到互连网络的时间(6)
11、接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间,24,一个消息的总时延,总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销,25,例7.1,假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？解光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50%，相距100米时总时延相距1000公里时的总时延,26,7.1.4互连网络的种类,互连网络的种类很多，分类方法也很多以互连特性为
12、特征，可分为如下几类静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播,27,1 静态互连网络,静态互连网络是指在各结点间有专用的连接通路，且在运行中不能改变的网络在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之
13、间的连接通路，直接实现两结点间的通信一维的有线性阵列结构二维的有环形、星形、树形、网格形等三维的有立方体等三维以上的有超立方体等,28,(1)线性阵列,一种一维网络，其中N个结点用N-1条链路连成一行内部的结点度为2，端点的结点度为1。直径为N-1当N大时，直径也比较大。等分宽度b=1线性阵列是最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低在N很小的情况下，如N=2，实现线性阵列是相当经济的。由于直径随N线性增大，因此当N比较大时，就不应使用这种网络了,29,(1)线性阵列,线性阵列与总线的区别是很大的，后者是通过切换与其连接的许多结点来实现时分特性的线性阵列允许不同的源结点和目的
14、结点对并发使用系统的不同部分(通道),30,(2)环和带弦环(3)循环移数网络,采用移数函数。使用不同的移数函数，可以构成多种环形网单向环行网右环网，采用PM2+0函数左环网，采用PM2-0函数双向环行网：又称为一维邻居网，采用PM2+0，PM2-0函数环行网是对称的，结点度是常数2双向环网的直径为N/2，单向环形网的直径是N将结点度由2提高至3，可得到弦环网增加的弦愈多，则结点度愈高，网络直径愈小循环移数网络也是一种环形网，它将环上每个结点与其距离为2的整数幂的结点之间连接构成循环移数网的结点度为2n-1，直径为n/2,31,(2)环和带弦环(3)循环移数网络,32,二叉树网,二叉胖树网,星
15、形网,(4)树形和星形(5)胖树形,一棵k层完全平衡二叉树有N=2k-1个结点，结点度3，直径2(k-1)星形是一种特殊的2层树，结点度很高，为d=N-1，直径2星形结构已用于有集中监督结点的系统中二叉胖树的结点度从叶子结点往根结点逐渐增加胖树缓解了一般二叉树根结点通信速度高的矛盾,33,(6)网格和环网形,网格网是一种比较流行的网络结构，有各种变体形式在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现一般网格网，N=nk 结点的k维网格的结点度为2k，直径为k(n-1)环网形网格网沿阵列每行每列都有环形连接。一个nn二元环网的结点度为4，直径为2n/2。环
16、网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半一个nn Illiac网格直径为d=n-1，为纯网格直径的一半Illiac IV的88 Illiac网格，其结点度为4，直径为7,34,网格形,环形网,Illiac网,(6)网格和环网形,35,(7)搏动式阵列,这是一类为实现确定算法而设计的多维流水线阵列结构图7.15(d)所示就是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6一般说来，静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作商用Intel iWarp系统就是用搏动式结构设计而成自从1978年Kung和Leiserson提出搏动式阵列后，它已成为广泛研究的领域通
17、过确定的互连和同步操作，搏动式阵列可与算法的通信结构相匹配对信号/图象处理等特殊应用，搏动式阵列可提供更好的性能/价格比但结构的实用性有限，而且编制程序也很难,36,(7)搏动式阵列,n维立方体由N=2n个结点, 分布在n维上, 每维有两个结点超立方体网采用交换函数，结点度为n，直径也为n4-立方体可通过将两个3-立方体的相应结点互连组成,(8)超立方体,38,(9)带环立方体,这种结构是从超立方体改进而来的一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替从一个k-立方体构成一个有n=2k个结点环的带环k-立方体所用的办法是用k个结点的环
18、取代k维超立方体的每个顶角这样，一个k-立方体可变成k2k个结点的k-CCC3-CCC的直径为6，比原来3-立方体的直径大一倍。一般说来，k-CCC的网格直径2k。CCC的主要改进之处即在其结点度为常数3，与超立方体的维数无关一超立方体有N=2n结点。一个有同样N结点数的CCC一定是由低维k-立方体组成，即2n=k2k，其中kn对应于n=6和k=4的情况，一个64结点的CCC可用4结点的环取代4-立方体的角结点组成。CCC的直径为2k=8，比6-立方体的6要长些。但是，CCC的结点度为3，比6-立方体的结点度6要小容许一定的时延,CCC是一种构造可扩展系统的较好的结构,39,(9)带环立方体,
19、40,(10)k元n-立方体网络,环形、网格形、环网形、二元n-立方体(超立方体)和W网络都是k元n-立方体网络系列的拓扑同构体参数n是立方体的维数，k是基数或者说是沿每个方向的结点数(多重性)。这两个数与网络中结点数N的关系为k元n-立方体的结点可用基数为k的n位地址A=a1a2an来表示，其中ai代表第i维结点位置。为简单起见，所有链路都认为是双向的。网络中每条线代表两个通信通道，每个方向一个,41,图7.17 k=4和n=3的k元n-立方体网络,(1)4结点串成绿色环(2)4绿色环并排成面，同一列用黄色环连接(3)4黄色面堆成体，同一行用蓝色环连接,42,(a)传统环网(4元2-立方体)
20、(b)折叠连接的环网SHOW AVI,43,2 动态互连网络,动态互连网络设置有源开关根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式包括总线、多级互连网和交叉开关网络,44,(1)总线,总线系统是一组导线和插座用于处理与总线相连接的处理机、存储器模块和外围设备间的数据业务总线被称为多个功能模块间争用总线或时分总线总线系统与其它两种动态连接网络相比，其价格较低，带宽较窄。有很多可用的工业和IEEE总线标准,45,(2)开关模块,一个ab开关模块有a个输入和b个输出。一个二元开关则与a=b=2的22开关模块相对应。实际中a和b通常选为a=b=2k，k=1最常用的二元开关：a=b=
21、2每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射只容许一对一映射时称为置换连接，称这种开关为nn交叉开关具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制,46,模块大小,合法状态,交换连接,22,4,2,44,256,24,88,16777216,40320,nn,nn,n!,交换开关和合法状态,(3)多级网络,能够实现结点到结点之间的任意互连是互连网络的一种基本功能多级互连网络采用多个相同的或不同的互连网络直接连接起来属于组合逻辑线路，一个
22、时钟周期就能够实现任意结点到结点之间的互连多级互连网络采用的关键技术(1) 交换开关(2) 交换开关之间的拓扑连接(3) 对交换开关的不同控制方式,(3)多级网络,(3a)拓扑结构(级间连接)前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构通常采用前面介绍的互连函数实现拓扑结构从结点的输出到第一级交换开关的输入，及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接(3b)控制方式在多级互连网络中有多级交换开关，每一级又有多个交换开关(1)级控制：同一级交换开关使用同一个控制信号控制(2)单元级控制：每个交换开关分别控制(3)部分级控制：如，第i级使用i+1个控制
23、信号控制 (0=i=n-1)同一个多级互连网络分别使用三种不同的控制方式，可以构成三种不同的互连网络,49,图7.20 一种由ab开关模块和级间连接模式,50,采用二功能开关，总共需要开关 n 2(n-1)个。采用交换函数构成拓扑结构，各级分别采用E0、E1、En-1交换函数当所有开关都直通时，实现恒等变换当A、B、C、D四个开关交换，其余直通时实现 E0 互连函数当E、F、G、H四个开关交换，其余直通时实现 E1 互连函数当I、J、K、L四个开关交换，其余直通时实现 E2 互连函数采用三种不同的控制方式，可以构成三种不同的互连网络。采用级控制可以构成STARAN交换网采用部分级控制，可以构成
24、STARAN移数网采用单元控制可以构成间接二进制n方体网,(3c)多级立方体网,51,B(2) B(3) S -1,(3c)多级立方体网,52,(4)网络,1616网络，共需4级22开关网络左侧有16个输入，右侧有16个输出 ISC是对16个对象的均匀洗牌模式2路洗牌相当于n个输入端平均地分成2个子组，然后2个子组均匀地洗牌一个n输入的网络需要log2n级22开关，每级要用n/2个开关模块，网络共需(nlog2n)/2个开关不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接每级的拓扑结构相同采用单元控制能够实现任意一个输入端到任意一个输出端的连接不能同时实现多个输入端到多个输出端的
25、连接通过检查二进制目的地址编码来控制数据路径目的地址编码从高位开始的第i位为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接,53,均匀洗牌置换,输入1可连接到哪几个输出?,54,(5)基准网络,Wu和Feng 研究过多级互连网络之间的关系基准网络可如图7.22(a)所示递归生成第1级为一个NN模块第2级为两个(N/2)(N/2)子模块，以C0和C1表示以上构成方法可递归用于子模块直至得到22的N/2子模块为止各小框和最终的子模块构件是22开关，每个有两个合法连接状态：两个输入和两个输出间的直送和交叉连接,55,每个交换开关的输出分成上下两组，分别连到两个N/2,56,1
26、组16结点S -1 2组8结点S -1 4组4结点S -1,递归终点为1个2x2子模块，即仅有两个结点,57,(6)交叉开关网络,全交叉开关网络能够同时实现任意结点到结点之间的互连还能够实现广播和多播全交叉开关网络的带宽和互连特性最好在多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接可看作是一个单级开关网络。象电话交换机一样，交叉点开关能在对偶(源、目的)之间形成动态连接，每个交叉点开关在对偶间提供一条专用连接通路，开关可根据程序的要求动态地设置“开”或“关”,58,另一种分类,59,7.2 消息传递机制,研究各种寻径方法，并分析它们的通信时延问题引入虚拟通道的概念，说明怎样用虚拟
27、通道来避免死锁确定的和自适应两种寻径算法拓扑结构与寻径策略有一定的关系,60,7.2.1 消息寻径方式,四种寻径方式线路交换存储转发虚拟直通虫蚀寻径1. 消息格式消息是结点间通信的逻辑单位常常由任意数目的长度固定的包所组成其长度是可变的。包是包含寻径目的地址的基本单位。每个包需要一个序号，以便重新组装消息。可以将包进一步分成一些固定长度的片寻径信息和序号形成头片，其余的片是数据片。,61,62,在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位在采用虫蚀寻径网络的多计算机中，包可以进一步分成片。片的长度往往受网络大小的影响256个结点的网络需要片长为8位包的长度取决于寻径方式和网络
28、的实现方法典型的包的长度为64512位。序号可能占用12个片，取决于消息的长度包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关,63,2、四种寻径方式,两大类线路交换包交换(存储转发、虚拟直通和虫蚀寻径 )(1)线路交换(circuit switch)先建立一条从源结点到目的结点的物理通路，然后再传递消息传输时延公式T = (Lt/B)*D+L/B其中：Lt为建立路径所需小信息包的长度L为信息包的长度D为经过的结点数B为带宽优点：实际通信时间较短，使用缓冲区少缺点：建立源结点到目的结点的物理通路开销很大，占用物理通路时间长,64,(2)存储转发(store and forward),
29、每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点存储转发网络的时延与源和目的地之间的距离成正比。传输时延公式：T = (L/B) *D + L/B = (D + 1) * L/B优点：占用物理通路的时间比较短缺点：包缓冲区大，时延大(与结点距离成正比),65,(3)虚拟直通(virtual cut through),当接收到用作寻径的消息头部时，即开始路由选择。通信时延公式：T=(Lh/B) * D + L/B = (Lh * D+ L)/B其中：Lh是消息的寻径头部的长度，一般有，LLhD；通信时延可以近似为：T=L/B与结点数无关当出现寻径阻塞时，只能将整个消息存储在寻径结点中主
30、要优点：通信延迟与结点数无关主要缺点：每个结点需要有足够大的缓冲区来存储最大信息包在最坏的情况下与存储转发方式的通信时延是一样的，经过的每个结点都发生阻塞，都需缓冲,66,(4)虫蚀寻径(wormhole),把包分成更小的片。每个结点的寻径器中有片缓冲区用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择如所选择的通道空闲且所选择的结点B的片缓冲区可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B随后的其它数据片跟着相应地向前“蠕动”一步当消息的尾片向前“蠕动”一步之后
31、，它刚才所占有的结点就被放弃如果所选择的通道或的结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待通信时延用公式：T=TfD+L/B=(Lf/B)D+L/B=(LfD+L)/B其中：Lf是片的长度，Tf是片经过一个结点所需时间。一般有LLfD，可近似为T=L/B，通信时延与结点数无关,67,虫蚀寻径的优点,每个结点的缓冲区较小，易于VLSI实现较低的网络传输时延所有的片以流水方式向前传输，采用了时间并行性存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离虫蚀寻径方式的网络传输时延正
32、比于消息包的长度，传输距离对它的影响很小通道共享性好，利用率高对通道的预约和释放是结合在一起的一个完整的过程有一段新的通道后将立即放弃用过的一段旧通道易于实现选播和广播通信方式允许寻径器复制消息包的片并把它们从其多个输出通道输出,68,虫蚀寻径的缺点：当消息的一个片被阻塞时，整个消息都被阻塞，占用了结点资源需要采用虚拟通道的方式来避免由此引起的一连串的阻塞虫蚀寻径方式也可以分为无缓冲和有缓冲两类，区别在于缓冲的大小缓冲大有利于性能的提高，但会增加结点的复杂度IBM SP2采用的寻径方式就是带缓冲的虫蚀寻径方式，它采用共享的存储区来对输入/输出消息进行缓冲,69,图7.25 几种寻径方式的时空图
33、,(a) 线路开关寻径(1)N1-N4(2)通过识别消息头部，N1接到N2，N2接到N3，N3接到N4(3)N1发送，以极小的延迟通过中间结点N2，N3到达N4,70,(b) 存储转发寻径,(1)N1-N4(2)N1发送到N2存储(3)N2转发到N3存储(4)N3转发到N4,71,(c) 虫蚀寻径,(1)N1-N4(2)头片由N1寻径至N2，N1发送头片到N2存储(3)头片由N2寻径至N3，N2发送头片到N3存储N1发送1号片到N2存储(4)头片由N3寻径至N4，N3发送头片到N4N2发送1号片到N3存储N1发送2号片到N2存储N1,N2,N3类似流水线的三段，头片,1号片,2号片类似流水线的
34、三条指令-流水方式，蠕动，一个包传送完成前，蠕动路径不能和其他包的蠕动路径交叉头片逐个结点寻径，尾片逐个结点放弃蠕动路径,72,7.2.2死锁和虚拟通道,1虚拟通道虚拟通道是两个结点间的逻辑链由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成物理通道由所有的虚拟通道分时共享如图四条虚拟通道分时共享一条物理通道,73,四条虚拟通道以片传递为基础分时地共享一条物理通道,74,2死锁的产生和避免,由于缓冲区或通道上的循环等待会引起死锁采用存储转发寻径的四个结点间出现缓冲区死锁,75,采用虫蚀寻径的四个结点之间出现通道死锁,76,如何避免死锁,缓冲区或通道上的循环等待会引起死锁利用虚拟通道
35、方法可以减少死锁。增加两条虚拟通道V3和V4利用虚拟通道避免死锁虚拟通道可以用单向通道或者双向通道实现将两条单向通道组合在一起可以构成一条双向通道虚拟通道可能会使每个请求可用的有效通道频宽降低确定虚拟通道数目，需要对网络吞吐量和通信时延折衰考虑实现数目很大的虚拟通道需要用高速的多路选择开关,77,(b)包含循环的通道相关图(d)利用虚拟通道后修改的通道相关图,78,7.2.3流控制策略,1包冲突的解决在两个相邻结点之间传送片时，必须具备三个条件(1) 源缓冲区已存有该片(2) 通道已分配好(3) 接收缓冲区准备接收该片接收缓冲区或输出通道冲突的仲裁(1) 把后一个包暂时存放在缓冲区(2) 阻塞
36、后一个包(3) 扬弃后一个包(4) 绕道,79,图7.31解决两个包请求同一条输出通道发生冲突时的流控制方法,(a)用缓冲实现虚拟直径寻径(b)阻塞流控制(c)扬弃并重发(d)阻塞后绕道,80,2确定寻径和自适应寻径,如何找出一条从源结点到目的结点的路径来传送消息？寻径可以分为确定和自适应两类采用确定寻径时，通信路径完全由源和目的地址确定即寻找的路径是预先唯一确定的，与网络的状况无关自适应寻径与网络的状况有关，可能会有几条路径两种寻径都需要无死锁算法,81,(1)确定寻径,维序寻径算法按照多维网络维序的特定顺序来选择后继通道在二维网格网络中称为X-Y寻径首先沿着X维方向确定路径，然后沿着Y维方
37、向选择路径在超立体(或n立方体)网络中，采用最初由Sullivan和Bashkow于1977年提出的称为E立方体寻径(E-cube routing)方法。 逐维改变(a) 二维网格网络的X-Y寻径假定从任意源结点s=(x1，y1)到任意目的结点d=(x2，y2)寻径从s开始首先沿X方向前进一直到d所在的第x2列为止然后沿Y方向前进直到y2, 即d总是首先沿X维方向寻径，然后再沿Y维方向寻径，寻径就不会出现死锁或循环等待,82,与东-北、东-南、西-北及西-南的路径方向相对应，X-Y寻径共有4种模式(2,1;7,6)东-北(0,7;4,2)东-南.,83,按照维序，可以很容易地将X-Y寻径扩充到
38、n维网络以三维网格为例，可以类似地说明X-Y-Z寻径方法X-Y方式不会产生死锁寻径，可用于存储转发或虫蚀寻径网络，在源和目的结点之间形成一条距离最短的路径对于环网网络，采用维序寻径方法不能得到最短路径为了减少网络流量或其它原因，不会产生死锁的非最短寻径算法有时会使包通过的路径较长,84,(b) 超立方体网络的E立方体寻径,假设有一N=2n个结点的n方体。每个结点的二进制编码为b=bn-1bn-2b1b0。这样，源结点为s=sn-1sn-2s1s0，目的结点d=dn-1bn-2d1d0现在要确定一条从s到d的步数最小的路径将n维表示成i=1，2，n，其中第i维对应于结点地址中的第i-1位。设u=
39、un-1un-2u1u0是路径中的任一结点路径可以根据以下方法唯一地确定计算方向位ri=si-1di-1，其中i=1，2，.，n。使i=1，v=s如果ri=1，从当前结点u寻径到下一结点。如果ri=0，则跳过这一步 ii+1。如果in，则转第步，否则退出寻径是按照从维1到维4的顺序进行的如果s和d的第i位相同，则沿维i方向不需要寻径否则从当前结点沿着这一维方向走到其它结点重复这一过程直到到达目的结点E立方体寻径也不会产生死锁寻径，也可用于存储转发和虫蚀网络，在源和结点之间形成一条距离最短的路径,85,图中，n=4，s=0110，d=1101r=r4r3r2r1=sd=01101101=1011
40、i=1, r1=1，v=s=0110寻径到v=v20=01101=0111i=2, r2=1，v=0111寻径到v=v21=011110=0101i=3, r3=0，跳过维i=3这一步i=4, r4=1，v=0101寻径到v=v23=01011000=1101=d,86,(2)自适应寻径,采用自适应寻径要特别注意避免死锁虚拟通道的概念使实现自适应寻径更经济和更灵活在网格连接网络中，同一维的所有连接都使用虚拟通道图7.34是一个用X-Y寻径的网格网络，在Y维上用了2对虚拟通道图7.34(c)中的虚拟网络可以用来避免消息在向西传输出现的死锁，因为所有向东的X通道都没有使用图7.34(d)中的虚拟网
41、络使用另一组Y方向虚拟通道来支持只向东的传输不同的时刻使用两个虚拟网络，这样死锁就可以自动避免P424L3，X 改成 Y,87,图7.34 利用虚拟通道避免死锁的自适应X-Y寻径,(a)没有虚拟通道的原形网络(b)Y维方向有两对虚拟通道 (c)向西方向传输信息(d)向东方向传输信息,c,d有循环等待吗,88,图7.35是在X维和Y维方向各有两条虚拟通道的网格形网络这些虚拟通道可以用来生成4个虚拟网络西-北方向通信应该使用图7.35(b)所示的虚拟网络类似地，其它方向的通信可以构造另外3个虚拟网络注意，任何一个虚拟网络都不会出现环路在这些网络上实现X-Y寻径方法时，完全可以避免死锁如果相邻结点之
42、间的两对通道都是物理通道，那么4个虚拟网络中任何两个都可以同时使用而不会产生冲突如果相邻结点之间双虚拟通道只能共享一对物理通道只有(b)和(e)或(c)和(d)可以同时使用其它组合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同时存在，因为缺少通道网络的通道数增加，寻径的自适应性也将增加成本的增加将很可观，要避免使用过多的资源P425L3，b和c 改成 b和e,89,图7.35 双通道网格网络可实现4个虚拟网络,(a)双通道的33网络(b)西-北子网(c)东-北子网(d)西-南子网 (e)东-南子网,b,c,d,e有循环等待吗,90,7.2.4选播与广播寻径算法,
43、四种通信模式(1)单播(unicast),一对一传送(2)选播(multicast),一个源结点发送同一个消息到多个目的结点(3)广播(broadcast),一个源结点发送同一个消息到全部结点(4)会议(conference),对应于多到多的通信情况,91,广播与选播算法,广播是将一个结点的数据复制到全部N个结点；选播是将一个结点的数据复制到多个(N个)结点，1NN研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数(又称流量或通道数)最少的方案这里所说的并行传输，指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行(具有这种能
44、力的互连网不属于现在的讨论范围)对不同的网络，适用的广播与选播算法也不同,92,选播,选播算法的设计目标有3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案选播时间最少算法是通过单播时间最少算法裁剪而成(教材P426图7.36(a)(b)选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树”(教材P426图7.36(c)实现第3种目标的一种重要算法是贪婪算法(教材P426图7.36(b)不论对何种网络，贪婪算法总是重复使用一个固定的操作规则从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步如此循环，直至传遍所有
45、需要数据的结点如果最后发现某个通道(即一次数据发送操作)不在通往给定目标结点的路径上，则应将其删去,93,扩散,向最近的结点的方向移动1步,5次点对点,1个流量为相邻结点一次传输,向可达结点数最多的方向移动1步,1,2,3,4,4,4,4,1,2,3,6,4,5,94,图7.37 贪婪算法4立方体广播树和选播树,(a)一个根结点为0000的4立方体。超立方体广播树的流量最小。 (b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点,95,贪婪选播算法的基本思想是向那些可达到最多剩余目的结点的维方向发送包图7.37(a)是一个根结点为0000的4立方体。超立方体广播树的流量最小图7.37(
46、b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点从源结点S=0101开始，由维2方向可以到达2个目的结点，由维4方向可以达到5个目的结点。第1层所用的通道是01010111和01011101从结点1101，由维2方向可以到达3个目的结点，由维1方向可以到达4个目的结点。第2层所用的通道是11011111，11011100和01110110同理，第3层所用的通道是11111110，11111011，11001000和01100010第4层所用的通道是11101010,96,在扩充选播树时首先应该比较所有各维方向的可达性(reachability)然后选择某些维使剩余目的结点的集合最小如
47、果两维之间有连线，那么选择其中任何一维都可以。因此，所生成的树不是唯一的已经证明贪婪选播算法所需的通道数与多次单播或广播树相比要少在虫蚀寻径网络中，实现选播操作时，每个结点的寻径器应有复制片缓冲区中数据的能力为了与选播树或广播树的增长同步，树中同一层的所有输出通道必须在传输向前推进一层之前处于就绪状态，否则中间结点需要增加缓冲区,97,(1)单级网格网(Mash网)贪婪算法,教材P426图7.36 (a)指出总共有1个源结点S和5个目的结点图(b)指出从S出发，首先应向右邻结点发送数据，因为S的左方只有1个目的结点、上方有3个目的结点、右方有个目的结点第二步从这2个拥有数据的结点出发，可以再向
48、右发送(有3个目的结点)，也可以改向上发送(也有3个目的结点)，只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的,98,教材P426图7.37(a)指出广播算法的时间是4，流量是15。Cube0 Cuben-1的使用顺序对广播算法的时间和流量没有影响，但对小图(b)的选播算法的时间和流量有影响 先看一个简单的例子(下图)：已知N=4，维数n=2，源结点是0，目的结点是1和3 源结点编号的二进制形式00在bit0位与两个目的结点的二进制形式01、11都不相同，而在bit1位仅与一个目的结点的二进制形式不同，所以应该先传bit0方向、再传bit1方向，如右图(a)所示，这时流
49、量=2；如果先传bit1方向、再传bit0方向，如右图(b)所示，则流量=3,(2)单级立方体网络贪婪算法,99,教材P426图7.37(b)的例子。源结点编号的二进制形式0101在Cube0 Cube3位分别与5、5、4、5个目的结点的二进制形式不同，所以Cube2方向应该最后发送，其它3个方向的发送先后顺序则没有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=10,7.3 互连网络实例,着重研究下面几种多处理机的互连网络总线结构、环形互连、交叉开关、混洗交换互连等处理机系统采用哪种互连结构主要取决于系统的最大通信量反过来，系统
50、的最大通信量受到互连结构的限制,101,7.3.1 总线互连,目前，大部分处理机内部采用总线结构CPU与存储器之间有系统总线存储器与输入输出设备之间有I/O总线总线与总线之间通过总线桥连接总线的主要优点是结构简单，能够很方便实现广播通信总线的主要缺点是带宽低，发生总线冲突的可能性大总线冲突的解决办法有(1) 设置静态优先级(2) 在同步方式中采用时间片(3) 采用动态优先级(如LRU法等)(4) 先来先服务,102,总线结构的多处理机,为了提高总线的通信带宽，有如下方法(1) 采用多总线结构(2) 层次总线结构(3) 多维总线结构多总线西门子公司的SMS系统(Stractured Multip
