1、1计算机系统结构n第一章 基本概念n第二章 指令系统n第三章 存储系统n第四章 输入输出系统n第五章 标量处理机n第六章 向量处理机n第七章 互连网络n第八章 并行处理机n第九章 多处理机2n互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络n用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接第七章 互连网络3第七章 互连网络n互连网络的基本概念n消息传递机制47.1 互连网络的基本概念n互连网络的作用n互连函数n互连网络的特性和传输的性能参数n互连网络的种类57.1.1互连网络的作用n用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。n为并行处理系统的核心组
2、成部分。n对整个计算机系统的性能价格比有着决定性的影响。6n具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构nIPMN(处理机-存储器网络)nPION(处理机-I/O网络)nIPCN(处理机之间通信网络)nP(处理机)C(高速缓冲存储器)nSM(共享存储器)LM(本地存储器)磁盘SM1SM2SMmIPMNCnPnLMC1P1LMIPCNPION磁带打印机终端网络(共享存储器)(共享I/O与外设)77.1.2互连函数n互连函数n将互连网的N个输入和N个输出端分别用整数(0,1,2,.,N-1)来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系n表示方法：
3、n互连函数法，图形表示法,输入输出对应表示法n函数表示法：nx表示输入端号，常用n位二进制形式表示 xn-1xn-2.x1x0nf(x)表示互连函数，为：f(xn-1xn-2.x1x0)n图形表示法:n用图形表示输入和输出端之间的连接n输入输出对应(矩阵)表示法：n循环表示法:把互连函数f(x)表示为：(x0，x1，.，xj)(xk，xk+1，.，xl).n表示对应关系为:f(x0)=x1，f(x1)=x2，.，f(xj)=x0 nj+1称为该循环的长度 0 1 2.N-1f(0)f(1)f(2).f(N-1)8常用的互连函数如下：n1 恒等置换：I(xn-1xn-2.x1x0)=xn-1xn
4、-2.x1x0 92 交换置换Exchangen实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。E(xn-1xn-2.x1x0)=xn-1xn-2.x1x0 n其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换103、方体置换Cuben当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。n由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。n用交换函数构成的互连网络的结点度为n，网络直径也为n。0111101111.).(xxxxxxxxxxxxCkkknkkkn
5、k012012201201210120120)()()(xxxxxxCxxxxxxCxxxxxxC11变化发生在 0，1，2位分别是高 2，1，0位相同的为一个组组内加/减 1，2，40 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 E0交换函数 E1交换函数 E2交换函数 C0C2C1124、均匀洗牌置换Perfect shufflen把二进制结点循环左移一位。n子混洗(subshuffle)S(k)最低k位循环左移一位n超混洗牌(supershuff
6、le)S(k)最高k位循环左移一位显然成立：逆混洗函数：教材P397L2,3,6错101320121.).(nnnnnxxxxxxxxxS011kn1nkn2n011knkn2n1n(k)1-k012kk2n1n012-k1-kk2n1n(k)xx.xxx.x=)xx.xx.x(xxxx.xx.xx=)xx.xxx.x(xSSxxSxSxSxSxSnn)()()()()()1()1()()(121001211.).(xxxxxxxxSnnnn134、均匀洗牌置换Perfect shufflen子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2)分两组0，1，2，3；4，5，6
7、，7n只用均匀洗牌函数不能实现任意结点之间的互连n通常用均匀洗牌函数与其他函数，如交换函数一起构成互连网络。n均匀洗牌与逆均匀洗牌是两种十分有用的互连函数n以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega()网络与逆Omega(-1)网络。n 逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 均匀洗牌置换 子洗牌置换
8、S(2)超洗牌置换S(2)逆均匀洗牌置换S-1 145、蝶式置换Butterflyn蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。n将输入端二进制结点号的最高位和最低位互换位置。n子蝶式(subbutterfly)B(k)最低k位的最高位与最低位互换位置n超蝶式(superbutterfly)B(k)最高k位的最高位与最低位互换位置n显然成立n教材P398L1,2错11200121.).(nnnnxxxxxxxxB0121120121)(112021012121)(.=).(.=).(xxxxxxxxxxxxBxxxxxxxxxxxxxxBknnknnknknnnkkkknnkkknnk
9、xxBxBxBxBxBnn)()()()()()1()1()()(155、蝶式置换Butterflyn与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 BR函数 B(2)=R(2)函数 B(2)=R(2)函数 166、位序颠倒置换Bit Reversaln将输入端二进制地址的位序反过来就得相应输出的地址。n子反位序函数：最低k位的位序反过来n超反位序函数：最高k位的位序反过来n对于n=3的情况，
10、正好有 R=B，R(2)=B(2)，R(2)=B(2)。12100121.).(nnnnxxxxxxxxR01112101121)(121021012121)(.=).(.=).(xxxxxxxxxxxxxRxxxxxxxxxxxxxxRknnnknknknknnnkkkknnkkknnk177、移数置换n将输入端数组循环移动一定的位置向输出端传输。n也可以将整个输入数组分成若干个子数组，在子数组内进行循环移数置换，这种段内循环移数的表达式可写成为两个式子如下：(a)移数量换k=2 (b)段内移数置换k=1,r=2 NNkxxAx0 ,mod)()(rrrrnrnkxxAxxA2mod)()(
11、)()(0:)1(0:)1(:)1(:)1(188、加减2i置换其中：0 x N-1，0 i n-1，n=log2 N。NxxPMNxxPMiiiimod)2()(2mod)2()(20 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 0 i+1 i+2 A(2)198、加减2i置换n通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。n例如，Illiac函数是
12、构成Illiac IV阵列的基础，它包含PM20和PM2n/2等四个互连函数。n采用全部移数函数构成网络称为移数网，移数网的结点度d=2n-1，网络直径D=n/2207.1.3互连网络的特性和传输的性能参数n1 互连网络的特性n互连网络通常是用有向边或无向边连接有限个结点的组成。n互连网络的主要特性有n(1)网络规模：网络中结点的个数n(2)结点度：与结点相连接的边数称为结点度。包括入度和出度。n进入结点的边数叫入度，从结点出来的边数则叫出度n(3)距离：两个结点之间相连的最少边数n(4)网络直径：网络中任意两个结点间距离的最大值。n用结点间的连接边数表示217.1.3互连网络的特性和传输的性
13、能参数n(5)等分宽度：n当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示。n于是线等分宽度就是B=bw，w为通道宽度(用位表示)。n等分宽度是说明沿等分网络最大通信带宽的一个参数。n网络的所有其它横截面都应限在等分宽度之内。n(6)结点间的线长：n两个结点间连线的长度。用米、公里等表示n(7)对称性：n从任何结点看到拓扑结构都是一样的网络称为对称网络。n对称网络比较易实现，编程也较容易。222 互连网络传输的性能参数n一台机器发送消息给另一台机器时，发送方的步骤如下：n(1)用户程序把要发送的数据拷贝到操作系统的缓冲区。n(2)操作系统把缓冲区中的数据打包，并
14、发送的网络接口部件。n(3)网络接口硬件开始发送消息。n数据包的接收步骤如下：n(1)把数据包从网络接口部件拷贝到操作系统缓冲区。n(2)检查收到的数据包，如果正确，给接收方发回答信号。n(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区23互连网络在传输方面的主要性能参数n(1)频带宽度(Bandwidth)：互连网络传输信息的最大速率n(2)传输时间(Transmission time)：等于消息长度除以频宽n(3)飞行时间(Time of flight)：第一位信息到达接收方所花费的时间n(4)传输时延(Transport latency)：等于飞行时间与传输
15、时间之和n(5)发送方开销(Sender overhead)：处理器把消息放到互连网络的时间n(6)接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间24一个消息的总时延n总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销25例7.1n假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？n解n光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50%，相距100米时总时延n相距10
16、00公里时的总时延sssssssKmKmsT130127080067.0230270/1081000/5.2997925.01.0230秒兆位位接收方开销频宽消息长度飞行时间发送方开销sssssssssT7971=2708006671230=27010810005.2997925.01010002306267.1.4互连网络的种类n互连网络的种类很多，分类方法也很多n以互连特性为特征，可分为如下几类n静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连n循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连n多级互连网络：将多套相同的单级互连
17、网络连接起来，实现任意结点到结点之间的互连n全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连n全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播271 静态互连网络n静态互连网络是指在各结点间有专用的连接通路，且在运行中不能改变的网络n在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的连接通路，直接实现两结点间的通信n一维的有线性阵列结构n二维的有环形、星形、树形、网格形等n三维的有立方体等n三维以上的有超立方体等28(1)线性阵列n一种一维网络，其中N个结点用N-1条链路连成一行n内部
18、的结点度为2，端点的结点度为1。直径为N-1n当N大时，直径也比较大。等分宽度b=1n线性阵列是最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低n在N很小的情况下，如N=2，实现线性阵列是相当经济的。n由于直径随N线性增大，因此当N比较大时，就不应使用这种网络了29(1)线性阵列n线性阵列与总线的区别是很大的，后者是通过切换与其连接的许多结点来实现时分特性的n线性阵列允许不同的源结点和目的结点对并发使用系统的不同部分(通道)7 6 5 4 8 9 10 1115 14 13 12 0 1 2 330(2)环和带弦环(3)循环移数网络n采用移数函数。使用不同的移数函数，可以构成多种环形
19、网n单向环行网n右环网，采用PM2+0函数n左环网，采用PM2-0函数n双向环行网：又称为一维邻居网，采用PM2+0，PM2-0函数n环行网是对称的，结点度是常数2n双向环网的直径为N/2，单向环形网的直径是Nn将结点度由2提高至3，可得到弦环网n增加的弦愈多，则结点度愈高，网络直径愈小n循环移数网络也是一种环形网，它将环上每个结点与其距离为2的整数幂的结点之间连接构成n循环移数网的结点度为2n-1，直径为n/23110234576循环移数网(2)环和带弦环(3)循环移数网络0123456789101112131415度为3的带弦环012345678910111213141532二叉树网二叉胖
20、树网星形网(4)树形和星形(5)胖树形n一棵k层完全平衡二叉树有N=2k-1个结点，结点度3，直径2(k-1)n星形是一种特殊的2层树，结点度很高，为d=N-1，直径2n星形结构已用于有集中监督结点的系统中n二叉胖树的结点度从叶子结点往根结点逐渐增加n胖树缓解了一般二叉树根结点通信速度高的矛盾33(6)网格和环网形n网格网是一种比较流行的网络结构，有各种变体形式n在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现n一般网格网，N=nk 结点的k维网格的结点度为2k，直径为k(n-1)n环网形网格网沿阵列每行每列都有环形连接。n一个nn二元环网的结点度为4，直
21、径为2n/2。n环网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半n一个nn Illiac网格直径为d=n-1，为纯网格直径的一半nIlliac IV的88 Illiac网格，其结点度为4，直径为734网格形环形网Illiac网(6)网格和环网形35(7)搏动式阵列n这是一类为实现确定算法而设计的多维流水线阵列结构n图7.15(d)所示就是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6n一般说来，静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作n商用Intel iWarp系统就是用搏动式结构设计而成n自从1978年Kung和Leiserson提出搏动式阵列后，它已成为
22、广泛研究的领域n通过确定的互连和同步操作，搏动式阵列可与算法的通信结构相匹配n对信号/图象处理等特殊应用，搏动式阵列可提供更好的性能/价格比n但结构的实用性有限，而且编制程序也很难36(7)搏动式阵列nn维立方体由N=2n个结点,分布在n维上,每维有两个结点n超立方体网采用交换函数，结点度为n，直径也为nn4-立方体可通过将两个3-立方体的相应结点互连组成(8)超立方体YXZ01100001011011110110038(9)带环立方体n这种结构是从超立方体改进而来的n一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替n从一个k-立方体构成
23、一个有n=2k个结点环的带环k-立方体n所用的办法是用k个结点的环取代k维超立方体的每个顶角n这样，一个k-立方体可变成k2k个结点的k-CCCn3-CCC的直径为6，比原来3-立方体的直径大一倍。一般说来，k-CCC的网格直径2k。CCC的主要改进之处即在其结点度为常数3，与超立方体的维数无关n一超立方体有N=2n结点。一个有同样N结点数的CCC一定是由低维k-立方体组成，即2n=k2k，其中k=1n最常用的二元开关：a=b=2n每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射n只容许一对一映射时称为置换连接，称这种开关为nn交叉
24、开关n具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制n具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制46直通交换上播下播模块大小合法状态交换连接22424425624881677721640320nnnnn!交换开关和合法状态(3)多级网络n能够实现结点到结点之间的任意互连是互连网络的一种基本功能n多级互连网络采用多个相同的或不同的互连网络直接连接起来n属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连n多级互连网络采用的关键技术n(1)交换开关n(2)交换开关之间的拓扑连接n(3)对交换开关的不同控制方式(3)多级网络n(3a)拓扑
25、结构(级间连接)n前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构n通常采用前面介绍的互连函数实现拓扑结构n从结点的输出到第一级交换开关的输入，及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接n(3b)控制方式n在多级互连网络中有多级交换开关，每一级又有多个交换开关n(1)级控制：同一级交换开关使用同一个控制信号控制n(2)单元级控制：每个交换开关分别控制n(3)部分级控制：如，第i级使用i+1个控制信号控制(0=iLhD；通信时延可以近似为：nT=L/Bn与结点数无关n当出现寻径阻塞时，只能将整个消息存储在寻径结点中n主要优点：n通信延迟与结点数无关n主要
26、缺点：n每个结点需要有足够大的缓冲区来存储最大信息包n在最坏的情况下与存储转发方式的通信时延是一样的，经过的每个结点都发生阻塞，都需缓冲66(4)虫蚀寻径(wormhole)n把包分成更小的片。每个结点的寻径器中有片缓冲区n用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”n当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择n如所选择的通道空闲且所选择的结点B的片缓冲区可用，那么这个头片就不必等待，直接通过结点A传向下一个结点Bn随后的其它数据片跟着相应地向前“蠕动”一步n当消息的尾片向前“蠕动”一步之后，它刚才所占有的结点就
27、被放弃n如果所选择的通道或的结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待n通信时延用公式：nT=TfD+L/B=(Lf/B)D+L/B=(LfD+L)/Bn其中：Lf是片的长度，Tf是片经过一个结点所需时间。n一般有LLfD，可近似为T=L/B，n通信时延与结点数无关67虫蚀寻径的优点n每个结点的缓冲区较小，易于VLSI实现n较低的网络传输时延n所有的片以流水方式向前传输，采用了时间并行性n存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离n虫蚀寻径方式的网络传输时延正比于消
28、息包的长度，传输距离对它的影响很小n通道共享性好，利用率高n对通道的预约和释放是结合在一起的一个完整的过程n有一段新的通道后将立即放弃用过的一段旧通道n易于实现选播和广播通信方式n允许寻径器复制消息包的片并把它们从其多个输出通道输出68n虫蚀寻径的缺点：n当消息的一个片被阻塞时，整个消息都被阻塞，占用了结点资源n需要采用虚拟通道的方式来避免由此引起的一连串的阻塞n虫蚀寻径方式也可以分为无缓冲和有缓冲两类，区别在于缓冲的大小n缓冲大有利于性能的提高，但会增加结点的复杂度nIBM SP2采用的寻径方式就是带缓冲的虫蚀寻径方式，它采用共享的存储区来对输入/输出消息进行缓冲69图7.25 几种寻径方式
29、的时空图n(a)线路开关寻径n(1)N1-N4n(2)通过识别消息头部，N1接到N2，N2接到N3，N3接到N4n(3)N1发送，以极小的延迟通过中间结点N2，N3到达N470(b)存储转发寻径n(1)N1-N4n(2)N1发送到N2存储n(3)N2转发到N3存储n(4)N3转发到N471(c)虫蚀寻径n(1)N1-N4n(2)头片由N1寻径至N2，N1发送头片到N2存储n(3)头片由N2寻径至N3，N2发送头片到N3存储N1发送1号片到N2存储n(4)头片由N3寻径至N4，N3发送头片到N4N2发送1号片到N3存储N1发送2号片到N2存储nN1,N2,N3类似流水线的三段，头片,1号片,2号
30、片类似流水线的三条指令-流水方式，蠕动，n一个包传送完成前，蠕动路径不能和其他包的蠕动路径交叉n头片逐个结点寻径，尾片逐个结点放弃蠕动路径727.2.2死锁和虚拟通道n1虚拟通道n虚拟通道是两个结点间的逻辑链n由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成n物理通道由所有的虚拟通道分时共享n如图四条虚拟通道分时共享一条物理通道73物理通道四条虚拟通道以片传递为基础分时地共享一条物理通道742死锁的产生和避免n由于缓冲区或通道上的循环等待会引起死锁采用存储转发寻径的四个结点间出现缓冲区死锁 D D D D D包缓冲区 C C C C C包缓冲区 B B B B B包缓冲区 A A
31、 A A A包缓冲区75结点A结点D结点B结点Cm3m2m1m4寻径器C寻径器B片缓冲区消息1消息2消息3寻径器A消息4寻径器D采用虫蚀寻径的四个结点之间出现通道死锁76如何避免死锁n缓冲区或通道上的循环等待会引起死锁n利用虚拟通道方法可以减少死锁。增加两条虚拟通道V3和V4n利用虚拟通道避免死锁n虚拟通道可以用单向通道或者双向通道实现n将两条单向通道组合在一起可以构成一条双向通道n虚拟通道可能会使每个请求可用的有效通道频宽降低n确定虚拟通道数目，需要对网络吞吐量和通信时延折衰考虑n实现数目很大的虚拟通道需要用高速的多路选择开关77n(b)包含循环的通道相关图(d)利用虚拟通道后修改的通道相关
32、图787.2.3流控制策略n1包冲突的解决n在两个相邻结点之间传送片时，必须具备三个条件n(1)源缓冲区已存有该片n(2)通道已分配好n(3)接收缓冲区准备接收该片n接收缓冲区或输出通道冲突的仲裁n(1)把后一个包暂时存放在缓冲区n(2)阻塞后一个包n(3)扬弃后一个包n(4)绕道79图7.31解决两个包请求同一条输出通道发生冲突时的流控制方法n(a)用缓冲实现虚拟直径寻径(b)阻塞流控制n(c)扬弃并重发(d)阻塞后绕道 802确定寻径和自适应寻径n如何找出一条从源结点到目的结点的路径来传送消息？n寻径可以分为确定和自适应两类n采用确定寻径时，通信路径完全由源和目的地址确定n即寻找的路径是预
33、先唯一确定的，与网络的状况无关n自适应寻径与网络的状况有关，可能会有几条路径n两种寻径都需要无死锁算法81(1)确定寻径n维序寻径算法n按照多维网络维序的特定顺序来选择后继通道n在二维网格网络中称为X-Y寻径n首先沿着X维方向确定路径，然后沿着Y维方向选择路径n在超立体(或n立方体)网络中，采用最初由Sullivan和Bashkow于1977年提出的称为E立方体寻径(E-cube routing)方法。逐维改变n(a)二维网格网络的X-Y寻径n假定从任意源结点s=(x1，y1)到任意目的结点d=(x2，y2)n寻径从s开始n首先沿X方向前进一直到d所在的第x2列为止n然后沿Y方向前进直到y2,
34、即dn总是首先沿X维方向寻径，然后再沿Y维方向寻径，寻径就不会出现死锁或循环等待82n与东-北、东-南、西-北及西-南的路径方向相对应，X-Y寻径共有4种模式n(2,1;7,6)东-北n(0,7;4,2)东-南n.83n按照维序，可以很容易地将X-Y寻径扩充到n维网络n以三维网格为例，可以类似地说明X-Y-Z寻径方法nX-Y方式不会产生死锁寻径，可用于存储转发或虫蚀寻径网络，在源和目的结点之间形成一条距离最短的路径n对于环网网络，采用维序寻径方法不能得到最短路径n为了减少网络流量或其它原因，不会产生死锁的非最短寻径算法有时会使包通过的路径较长84(b)超立方体网络的E立方体寻径n假设有一N=2
35、n个结点的n方体。每个结点的二进制编码为b=bn-1bn-2b1b0。这样，源结点为s=sn-1sn-2s1s0，目的结点d=dn-1bn-2d1d0n现在要确定一条从s到d的步数最小的路径n将n维表示成i=1，2，n，其中第i维对应于结点地址中的第i-1位。设u=un-1un-2u1u0是路径中的任一结点n路径可以根据以下方法唯一地确定n计算方向位ri=si-1 di-1，其中i=1，2，.，n。使i=1，v=sn如果ri=1，从当前结点u寻径到下一结点。如果ri=0，则跳过这一步n ii+1。如果in，则转第步，否则退出n寻径是按照从维1到维4的顺序进行的n如果s和d的第i位相同，则沿维i
36、方向不需要寻径n否则从当前结点沿着这一维方向走到其它结点n重复这一过程直到到达目的结点nE立方体寻径也不会产生死锁寻径，也可用于存储转发和虫蚀网络，在源和结点之间形成一条距离最短的路径85n图中，n=4，s=0110，d=1101nr=r4r3r2r1=s d=0110 1101=1011ni=1,r1=1，v=s=0110寻径到v=v 20=01101=0111ni=2,r2=1，v=0111寻径到v=v 21=011110=0101ni=3,r3=0，跳过维i=3这一步ni=4,r4=1，v=0101寻径到v=v 23=01011000=1101=d86(2)自适应寻径n采用自适应寻径要特
37、别注意避免死锁n虚拟通道的概念使实现自适应寻径更经济和更灵活n在网格连接网络中，同一维的所有连接都使用虚拟通道n图7.34是一个用X-Y寻径的网格网络，在Y维上用了2对虚拟通道n图7.34(c)中的虚拟网络可以用来避免消息在向西传输出现的死锁，因为所有向东的X通道都没有使用n图7.34(d)中的虚拟网络使用另一组Y方向虚拟通道来支持只向东的传输n不同的时刻使用两个虚拟网络，这样死锁就可以自动避免nP424L3，X 改成 Y87图7.34 利用虚拟通道避免死锁的自适应X-Y寻径n (a)没有虚拟通道的原形网络(b)Y维方向有两对虚拟通道 n (c)向西方向传输信息(d)向东方向传输信息c,d有循
38、环等待吗88n图7.35是在X维和Y维方向各有两条虚拟通道的网格形网络n这些虚拟通道可以用来生成4个虚拟网络n西-北方向通信应该使用图7.35(b)所示的虚拟网络n类似地，其它方向的通信可以构造另外3个虚拟网络n注意，任何一个虚拟网络都不会出现环路n在这些网络上实现X-Y寻径方法时，完全可以避免死锁n如果相邻结点之间的两对通道都是物理通道，那么4个虚拟网络中任何两个都可以同时使用而不会产生冲突n如果相邻结点之间双虚拟通道只能共享一对物理通道n只有(b)和(e)或(c)和(d)可以同时使用n其它组合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同时存在，因为缺少通道
39、n网络的通道数增加，寻径的自适应性也将增加n成本的增加将很可观，要避免使用过多的资源nP425L3，b和c 改成 b和e89图7.35 双通道网格网络可实现4个虚拟网络 n(a)双通道的33网络(b)西-北子网(c)东-北子网n(d)西-南子网 (e)东-南子网b,c,d,e有循环等待吗907.2.4选播与广播寻径算法n四种通信模式n(1)单播(unicast),一对一传送n(2)选播(multicast),一个源结点发送同一个消息到多个目的结点n(3)广播(broadcast),一个源结点发送同一个消息到全部结点n(4)会议(conference),对应于多到多的通信情况91广播与选播算法n
40、广播是将一个结点的数据复制到全部N个结点；选播是将一个结点的数据复制到多个(N个)结点，1NNn研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数(又称流量或通道数)最少的方案n这里所说的并行传输，指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行n(具有这种能力的互连网不属于现在的讨论范围)n对不同的网络，适用的广播与选播算法也不同92选播n选播算法的设计目标有3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案n选播时间最少算法是通过单播时间最少算法裁剪而成(教材P426图7.36(a)(b)n选播流量最少算
41、法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树”(教材P426图7.36(c)n实现第3种目标的一种重要算法是贪婪算法(教材P426图7.36(b)n不论对何种网络，贪婪算法总是重复使用一个固定的操作规则n从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步n如此循环，直至传遍所有需要数据的结点n如果最后发现某个通道(即一次数据发送操作)不在通往给定目标结点的路径上，则应将其删去93扩散向最近的结点的方向移动1步5次点对点,1个流量为相邻结点一次传输向可达结点数最多的方向移动1步123444412364594图7.37 贪婪算法4立方
42、体广播树和选播树n(a)一个根结点为0000的4立方体。超立方体广播树的流量最小。n(b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点 95n贪婪选播算法的基本思想是向那些可达到最多剩余目的结点的维方向发送包n图7.37(a)是一个根结点为0000的4立方体。超立方体广播树的流量最小n图7.37(b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点n从源结点S=0101开始，由维2方向可以到达2个目的结点，由维4方向可以达到5个目的结点。第1层所用的通道是01010111和01011101n从结点1101，由维2方向可以到达3个目的结点，由维1方向可以到达4个目的结点。第2层所
43、用的通道是11011111，11011100和01110110n同理，第3层所用的通道是11111110，11111011，11001000和01100010n第4层所用的通道是1110101096n在扩充选播树时n首先应该比较所有各维方向的可达性(reachability)n然后选择某些维使剩余目的结点的集合最小n如果两维之间有连线，那么选择其中任何一维都可以。因此，所生成的树不是唯一的n已经证明贪婪选播算法所需的通道数与多次单播或广播树相比要少n在虫蚀寻径网络中，实现选播操作时，每个结点的寻径器应有复制片缓冲区中数据的能力n为了与选播树或广播树的增长同步，树中同一层的所有输出通道必须在传输
44、向前推进一层之前处于就绪状态，否则中间结点需要增加缓冲区97(1)单级网格网(Mash网)贪婪算法n教材P426图7.36(a)指出总共有1个源结点S和5个目的结点n图(b)指出从S出发，首先应向右邻结点发送数据，因为S的左方只有1个目的结点、上方有3个目的结点、右方有个目的结点n第二步从这2个拥有数据的结点出发，可以再向右发送(有3个目的结点)，也可以改向上发送(也有3个目的结点)，n只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的98教材P426图7.37(a)指出广播算法的时间是4，流量是15。Cube0 Cuben-1的使用顺序对广播算法的时间和流量没有影响，但对
45、小图(b)的选播算法的时间和流量有影响 先看一个简单的例子(下图)：已知N=4，维数n=2，源结点是0，目的结点是1和3 源结点编号的二进制形式00在bit0位与两个目的结点的二进制形式01、11都不相同，而在bit1位仅与一个目的结点的二进制形式不同，所以应该先传bit0方向、再传bit1方向，如右图(a)所示，这时流量=2；如果先传bit1方向、再传bit0方向，如右图(b)所示，则流量=3(2)单级立方体网络贪婪算法 00 00 Cube0 Cube1 00 01 00 10 Cube1 Cube000 10 01 11 00 01 10 11(a)先传 Cube0方向，流量=2 (b)
46、先传 Cube1方向，流量=3单级立方体网络贪婪算法的简单例子99教材P426图7.37(b)的例子。源结点编号的二进制形式0101在Cube0 Cube3位分别与5、5、4、5个目的结点的二进制形式不同，所以Cube2方向应该最后发送，其它3个方向的发送先后顺序则没有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=107.3 互连网络实例n着重研究下面几种多处理机的互连网络n总线结构、环形互连、交叉开关、混洗交换互连等n处理机系统采用哪种互连结构主要取决于系统的最大通信量n反过来，系统的最大通信量受到互连结构的限制1017.3.
47、1 总线互连n目前，大部分处理机内部采用总线结构nCPU与存储器之间有系统总线n存储器与输入输出设备之间有I/O总线n总线与总线之间通过总线桥连接n总线的主要优点是结构简单，能够很方便实现广播通信n总线的主要缺点是带宽低，发生总线冲突的可能性大n总线冲突的解决办法有n(1)设置静态优先级n(2)在同步方式中采用时间片n(3)采用动态优先级(如LRU法等)n(4)先来先服务102总线结构的多处理机n为了提高总线的通信带宽，有如下方法n(1)采用多总线结构n(2)层次总线结构n(3)多维总线结构n多总线n西门子公司的SMS系统(Stractured Multiprocessor System)n通
48、过8条总线连接128个处理机n层次总线n卡内基梅隆大学的Cm*多处理机系统采用层次总线结构n三级总线：群总线、Map总线、处理机总线n每群14台处理机主机P1P2P16P17P18P32P113P114P128总线驱动器SMS多总线结构卡内基梅隆大学的Cm*层次总线结构CmCmCmKmCmBCmKmCmCmCmKmMIOP群间总线1067.3.2环形互联n一种互连方法，它既能具有总线型互连的简单性，又可以克服总线所固有的缺点n信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止 107IEEE 802.5令牌环(Token Ring)nIEEE
49、802.5令牌环(Token Ring)标准是把环形看作逻辑总线的协议n发送信息的处理机拥有一个唯一的令牌，在同一时刻只有一台处理机持有这个令牌n当发送者发送信息时，这个环形网络的作用如同总线一样，其它处理机都处于接收信息的状态n信息传送结束时，发送者播送一个令牌，这个令牌是在普通信息中不会出现的特定信号。每台处理机依次看到令牌n如果某台处理机等待发送信息，那么它便接收这个令牌而不再传递给下一台处理机，这时这台处理机就可以通过环形网络发送信息了n假如没有想发送信息的处理机，那么令牌就将在环形网络上不断循环，直到某台处理机需要发送信息为止108n令牌环的优点是点点连接，而不是总线连接，其物理参数
50、更容易控制n令牌环形互连非常适于高带宽的光纤通信。N较小的总线互连系统很难采用光纤通信，N较大的系统也还未实现n令牌环形互连的一个主要缺点是每个总线接口都有延迟n通常是1位的延迟n当互连处理机台数增加时，在环中的信息传输延迟将正比例地增加n但是当系统负载很重时，系统的带宽却不会像总线互连系统那样下降7.3.3 交叉开关互连 n交叉开关网络，它把N台处理机和N个存储器连接起来n图中处理机台数与存储器个数相等，一般情况是存储器数目等于或是处理机数目的几倍n网络中每个交叉点是一个允许任何一台处理器与任何一个存储器连接的开关110n系统允许N个存取操作并行执行n任意两个存取操作不能涉及同一台处理机或同
