计算机系统机构-第7章课件

计算机系统结构第一章基本概念第二章指令系统第三章存储系统第四章输入输出系统第五章标量处理机第六章向量处理机第七章互连网络第八章并行处理机第九章多处理机1计算机系统结构第一章基本概念1互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接第七章互连网络2互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网第七章互连网络互连网络的基本概念消息传递机制3第七章互连网络互连网络的基本概念37.1互连网络的基本概念互连网络的作用互连函数互连网络的特性和传输的性能参数互连网络的种类47.1互连网络的基本概念互连网络的作用47.1.1互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。为并行处理系统的核心组成部分。对整个计算机系统的性能价格比有着决定性的影响。57.1.1互连网络的作用用来实现计算机系统内部多个处理机或多具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构IPMN(处理机-存储器网络)PION(处理机-I/O网络)IPCN(处理机之间通信网络)P(处理机)C(高速缓冲存储器)SM(共享存储器)LM(本地存储器)磁盘SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)6具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般7.1.2互连函数互连函数将互连网的N个输入和N个输出端分别用整数(0,1,2,...,N-1)来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系表示方法：互连函数法，图形表示法,输入输出对应表示法函数表示法：x表示输入端号，常用n位二进制形式表示xn-1xn-2...x1x0f(x)表示互连函数，为：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称为该循环的长度012...N-1f(0)f(1)f(2)...f(N-1)77.1.2互连函数互连函数012...常用的互连函数如下：1恒等置换：

I(xn-1xn-2...

x1x0)=xn-1xn-2...x1x08常用的互连函数如下：1恒等置换：82交换置换Exchange实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。

E(xn-1xn-2...

x1x0)=xn-1xn-2...

x1x0其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换92交换置换Exchange实现二进制地址编号中第0位位值不3、方体置换Cube当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。用交换函数构成的互连网络的结点度为n，网络直径也为n。103、方体置换Cube10变化发生在0，1，2位分别是高2，1，0位相同的为一个组组内加/减1，2，4C0C2C111变化发生在0，1，2位C0C2C1114、均匀洗牌置换Perfectshuffle把二进制结点循环左移一位。子混洗(subshuffle)S(k)最低k位循环左移一位超混洗牌(supershuffle)S(k)最高k位循环左移一位显然成立：逆混洗函数：教材P397L2,3,6错124、均匀洗牌置换Perfectshuffle124、均匀洗牌置换Perfectshuffle子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2)分两组0，1，2，3；4，5，6，7只用均匀洗牌函数不能实现任意结点之间的互连通常用均匀洗牌函数与其他函数，如交换函数一起构成互连网络。均匀洗牌与逆均匀洗牌是两种十分有用的互连函数以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega(Ω)网络与逆Omega(Ω^-1)网络。

逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换134、均匀洗牌置换Perfectshuffle135、蝶式置换Butterfly蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)最低k位的最高位与最低位互换位置超蝶式(superbutterfly)B(k)最高k位的最高位与最低位互换位置显然成立教材P398L1,2错145、蝶式置换Butterfly蝶式函数的名称来自于FFT变换5、蝶式置换Butterfly与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。155、蝶式置换Butterfly156、位序颠倒置换BitReversal将输入端二进制地址的位序反过来就得相应输出的地址。子反位序函数：最低k位的位序反过来超反位序函数：最高k位的位序反过来对于n=3的情况，正好有R=B，R(2)=B(2)，R(2)=B(2)。166、位序颠倒置换BitReversal将输入端二进制地址的7、移数置换将输入端数组循环移动一定的位置向输出端传输。也可以将整个输入数组分成若干个子数组，在子数组内进行循环移数置换，这种段内循环移数的表达式可写成为两个式子如下： (a)移数量换k=2(b)段内移数置换k=1,r=2177、移数置换将输入端数组循环移动一定的位置向输出端传输。178、加减2i置换其中：0xN-1，0in-1，n=log2N。188、加减2i置换188、加减2i置换通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。例如，Illiac函数是构成IlliacIV阵列的基础，它包含PM20和PM2n/2等四个互连函数。采用全部移数函数构成网络称为移数网，移数网的结点度d=2n-1，网络直径D=n/2198、加减2i置换通常采用移数函数可以构成环型网(包括单向环网7.1.3互连网络的特性和传输的性能参数1互连网络的特性互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有(1)网络规模：网络中结点的个数(2)结点度：与结点相连接的边数称为结点度。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度(3)距离：两个结点之间相连的最少边数(4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示207.1.3互连网络的特性和传输的性能参数1互连网络的特性27.1.3互连网络的特性和传输的性能参数(5)等分宽度：当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示。于是线等分宽度就是B=b×w，w为通道宽度(用位表示)。等分宽度是说明沿等分网络最大通信带宽的一个参数。网络的所有其它横截面都应限在等分宽度之内。(6)结点间的线长：两个结点间连线的长度。用米、公里等表示(7)对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。217.1.3互连网络的特性和传输的性能参数(5)等分宽度：22互连网络传输的性能参数一台机器发送消息给另一台机器时，发送方的步骤如下：(1)用户程序把要发送的数据拷贝到操作系统的缓冲区。(2)操作系统把缓冲区中的数据打包，并发送的网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到操作系统缓冲区。(2)检查收到的数据包，如果正确，给接收方发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区222互连网络传输的性能参数一台机器发送消息给另一台机器时，发互连网络在传输方面的主要性能参数(1)频带宽度(Bandwidth)： 互连网络传输信息的最大速率(2)传输时间(Transmissiontime)： 等于消息长度除以频宽(3)飞行时间(Timeofflight)：

第一位信息到达接收方所花费的时间(4)传输时延(Transportlatency)： 等于飞行时间与传输时间之和(5)发送方开销(Senderoverhead)： 处理器把消息放到互连网络的时间(6)接收方开销(Receiveroverhead)： 处理器把消息从网络取出来的时间23互连网络在传输方面的主要性能参数(1)频带宽度(Bandw一个消息的总时延总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销24一个消息的总时延总时延=发送方开销+飞行时间+消息长度/频宽例7.1假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？解光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50%，相距100米时总时延相距1000公里时的总时延25例7.1假设一个网络的频宽为10Mb/S，发送方开销为2307.1.4互连网络的种类互连网络的种类很多，分类方法也很多以互连特性为特征，可分为如下几类静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播267.1.4互连网络的种类互连网络的种类很多，分类方法也很多21静态互连网络静态互连网络是指在各结点间有专用的连接通路，且在运行中不能改变的网络在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的连接通路，直接实现两结点间的通信一维的有线性阵列结构二维的有环形、星形、树形、网格形等三维的有立方体等三维以上的有超立方体等271静态互连网络静态互连网络是指在各结点间有专用的连接通路，(1)线性阵列一种一维网络，其中N个结点用N-1条链路连成一行内部的结点度为2，端点的结点度为1。直径为N-1当N大时，直径也比较大。等分宽度b=1线性阵列是最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低在N很小的情况下，如N=2，实现线性阵列是相当经济的。由于直径随N线性增大，因此当N比较大时，就不应使用这种网络了28(1)线性阵列一种一维网络，其中N个结点用N-1条链路连成一(1)线性阵列线性阵列与总线的区别是很大的，后者是通过切换与其连接的许多结点来实现时分特性的线性阵列允许不同的源结点和目的结点对并发使用系统的不同部分(通道)765489101115141312012329(1)线性阵列线性阵列与总线的区别是很大的，后者是通过切换与(2)环和带弦环(3)循环移数网络采用移数函数。使用不同的移数函数，可以构成多种环形网单向环行网右环网，采用PM2+0函数左环网，采用PM2-0函数双向环行网：又称为一维邻居网，采用{PM2+0，PM2-0}函数环行网是对称的，结点度是常数2双向环网的直径为N/2，单向环形网的直径是N将结点度由2提高至3，可得到弦环网增加的弦愈多，则结点度愈高，网络直径愈小循环移数网络也是一种环形网，它将环上每个结点与其距离为2的整数幂的结点之间连接构成循环移数网的结点度为2n-1，直径为[n/2]30(2)环和带弦环(3)循环移数网络采用移数函数。使用不同的移10234576循环移数网(2)环和带弦环(3)循环移数网络0123456789101112131415度为3的带弦环01234567891011121314153110234576循环移数网(2)环和带弦环(3)循环移数网络二叉树网二叉胖树网星形网(4)树形和星形(5)胖树形一棵k层完全平衡二叉树有N=2^k-1个结点，结点度3，直径2(k-1)星形是一种特殊的2层树，结点度很高，为d=N-1，直径2星形结构已用于有集中监督结点的系统中二叉胖树的结点度从叶子结点往根结点逐渐增加胖树缓解了一般二叉树根结点通信速度高的矛盾32二叉树网二叉胖树网星形网(4)树形和星形(5)胖树形32(6)网格和环网形网格网是一种比较流行的网络结构，有各种变体形式在IlliacIV、MPP、DAP、CM-2和InetlParagon中得到了实现一般网格网，N=n^k结点的k维网格的结点度为2k，直径为k(n-1)环网形网格网沿阵列每行每列都有环形连接。一个n×n二元环网的结点度为4，直径为2[n/2]。环网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半一个n×nIlliac网格直径为d=n-1，为纯网格直径的一半IlliacIV的8×8Illiac网格，其结点度为4，直径为733(6)网格和环网形网格网是一种比较流行的网络结构，有各种变体网格形环形网Illiac网(6)网格和环网形34网格形环形网Illiac网(6)网格和环网形34(7)搏动式阵列这是一类为实现确定算法而设计的多维流水线阵列结构图7.15(d)所示就是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6一般说来，静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作商用InteliWarp系统就是用搏动式结构设计而成自从1978年Kung和Leiserson提出搏动式阵列后，它已成为广泛研究的领域通过确定的互连和同步操作，搏动式阵列可与算法的通信结构相匹配对信号/图象处理等特殊应用，搏动式阵列可提供更好的性能/价格比但结构的实用性有限，而且编制程序也很难35(7)搏动式阵列这是一类为实现确定算法而设计的多维流水线阵列(7)搏动式阵列36(7)搏动式阵列36n维立方体由N=2^n个结点,分布在n维上,每维有两个结点超立方体网采用交换函数，结点度为n，直径也为n4-立方体可通过将两个3-立方体的相应结点互连组成(8)超立方体YXZ011000010110111101100n维立方体由N=2^n个结点,分布在n维上,每维有两个结(9)带环立方体这种结构是从超立方体改进而来的一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替从一个k-立方体构成一个有n=2^k个结点环的带环k-立方体所用的办法是用k个结点的环取代k维超立方体的每个顶角这样，一个k-立方体可变成k×2^k个结点的k-CCC3-CCC的直径为6，比原来3-立方体的直径大一倍。一般说来，k-CCC的网格直径2k。CCC的主要改进之处即在其结点度为常数3，与超立方体的维数无关一超立方体有N=2^n结点。一个有同样N结点数的CCC一定是由低维k-立方体组成，即2^n=k×2^k，其中k<n对应于n=6和k=4的情况，一个64结点的CCC可用4结点的环取代4-立方体的角结点组成。CCC的直径为2k=8，比6-立方体的6要长些。但是，CCC的结点度为3，比6-立方体的结点度6要小容许一定的时延,CCC是一种构造可扩展系统的较好的结构38(9)带环立方体这种结构是从超立方体改进而来的38(9)带环立方体YXZ01100001011011110110039(9)带环立方体YXZ0110000101101111011(10)k元n-立方体网络环形、网格形、环网形、二元n-立方体(超立方体)和W网络都是k元n-立方体网络系列的拓扑同构体参数n是立方体的维数，k是基数或者说是沿每个方向的结点数(多重性)。这两个数与网络中结点数N的关系为k元n-立方体的结点可用基数为k的n位地址A=a1a2…an来表示，其中ai代表第i维结点位置。为简单起见，所有链路都认为是双向的。网络中每条线代表两个通信通道，每个方向一个40(10)k元n-立方体网络环形、网格形、环网形、二元n-立方图7.17k=4和n=3的k元n-立方体网络(1)4结点串成绿色环(2)4绿色环并排成面，同一列用黄色环连接(3)4黄色面堆成体，同一行用蓝色环连接41图7.17k=4和n=3的k元n-立方体网络41(a)传统环网(4元2-立方体) (b)折叠连接的环网SHOWAVI42422动态互连网络动态互连网络设置有源开关根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式包括总线、多级互连网和交叉开关网络432动态互连网络动态互连网络设置有源开关43(1)总线总线系统是一组导线和插座用于处理与总线相连接的处理机、存储器模块和外围设备间的数据业务总线被称为多个功能模块间争用总线或时分总线总线系统与其它两种动态连接网络相比，其价格较低，带宽较窄。有很多可用的工业和IEEE总线标准44(1)总线总线系统是一组导线和插座用于处理与总线相连接的处理(2)开关模块一个ab开关模块有a个输入和b个输出。一个二元开关则与a=b=2的22开关模块相对应。实际中a和b通常选为a=b=2^k，k>=1最常用的二元开关：a=b=2每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射只容许一对一映射时称为置换连接，称这种开关为n×n交叉开关具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制45(2)开关模块一个ab开关模块有a个输入和b个输出。一个二直通交换上播下播模块大小合法状态交换连接2×2424×4256248×81677721640320n×nnnn!交换开关和合法状态46直通交换上播下播模块大小合法状态交换连接2×2424×425(3)多级网络能够实现结点到结点之间的任意互连是互连网络的一种基本功能多级互连网络采用多个相同的或不同的互连网络直接连接起来属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连多级互连网络采用的关键技术(1)交换开关(2)交换开关之间的拓扑连接(3)对交换开关的不同控制方式(3)多级网络能够实现结点到结点之间的任意互连是互连网络的一(3)多级网络(3a)拓扑结构(级间连接)前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构通常采用前面介绍的互连函数实现拓扑结构从结点的输出到第一级交换开关的输入，及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接(3b)控制方式在多级互连网络中有多级交换开关，每一级又有多个交换开关(1)级控制：同一级交换开关使用同一个控制信号控制(2)单元级控制：每个交换开关分别控制(3)部分级控制：如，第i级使用i+1个控制信号控制(0<=i<=n-1)同一个多级互连网络分别使用三种不同的控制方式，可以构成三种不同的互连网络(3)多级网络(3a)拓扑结构(级间连接)图7.20一种由a×b开关模块和级间连接模式49图7.20一种由a×b开关模块和级间连接模式49采用二功能开关，总共需要开关n2^(n-1)个。采用交换函数构成拓扑结构，各级分别采用E0、E1、…En-1交换函数当所有开关都直通时，实现恒等变换当A、B、C、D四个开关交换，其余直通时实现E0互连函数当E、F、G、H四个开关交换，其余直通时实现E1互连函数当I、J、K、L四个开关交换，其余直通时实现E2互连函数采用三种不同的控制方式，可以构成三种不同的互连网络。采用级控制可以构成STARAN交换网采用部分级控制，可以构成STARAN移数网采用单元控制可以构成间接二进制n方体网(3c)多级立方体网50采用二功能开关，总共需要开关n2^(n-1)个。(3c)

B(2) B(3) S-1ABCDEFGHIJKL0123456701234567k=0k=1k=2(3c)多级立方体网51ABCDEFGHIJKL0123456701234567k=(4)Ω网络16×16Ω网络，共需4级2×2开关网络左侧有16个输入，右侧有16个输出ISC是对16个对象的均匀洗牌模式2路洗牌相当于n个输入端平均地分成2个子组，然后2个子组均匀地洗牌一个n输入的Ω网络需要log2n级2×2开关，每级要用n/2个开关模块，网络共需(nlog2n)/2个开关不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接每级的拓扑结构相同采用单元控制能够实现任意一个输入端到任意一个输出端的连接不能同时实现多个输入端到多个输出端的连接通过检查二进制目的地址编码来控制数据路径目的地址编码从高位开始的第i位为0时，第i级的2×2开关的输入端与上输出端连接，否则输入端与下输出端连接52(4)Ω网络16×16Ω网络，共需4级2×2开关52均匀洗牌置换输入1可连接到哪几个输出?53均匀洗牌置换输入1可连接到哪几个输出?53

(5)基准网络Wu和Feng研究过多级互连网络之间的关系基准网络可如图7.22(a)所示递归生成第1级为一个N×N模块第2级为两个(N/2)×(N/2)子模块，以C0和C1表示以上构成方法可递归用于子模块直至得到2×2的N/2子模块为止各小框和最终的子模块构件是2×2开关，每个有两个合法连接状态：两个输入和两个输出间的直送和交叉连接54

(5)基准网络Wu和Feng研究过多级互连网络之间的每个交换开关的输出分成上下两组，分别连到两个N/255551组16结点S-12组8结点S-14组4结点S-1递归终点为1个2x2子模块，即仅有两个结点56递归终点为1个2x2子模块，即仅有两个结点56(6)交叉开关网络全交叉开关网络能够同时实现任意结点到结点之间的互连还能够实现广播和多播全交叉开关网络的带宽和互连特性最好在多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接可看作是一个单级开关网络。象电话交换机一样，交叉点开关能在对偶(源、目的)之间形成动态连接，每个交叉点开关在对偶间提供一条专用连接通路，开关可根据程序的要求动态地设置“开”或“关”57(6)交叉开关网络全交叉开关网络能够同时实现任意结点到结点之另一种分类58另一种分类587.2消息传递机制研究各种寻径方法，并分析它们的通信时延问题引入虚拟通道的概念，说明怎样用虚拟通道来避免死锁确定的和自适应两种寻径算法拓扑结构与寻径策略有一定的关系597.2消息传递机制研究各种寻径方法，并分析它们的通信时延问7.2.1消息寻径方式四种寻径方式线路交换存储转发虚拟直通虫蚀寻径1.消息格式消息是结点间通信的逻辑单位常常由任意数目的长度固定的包所组成其长度是可变的。包是包含寻径目的地址的基本单位。每个包需要一个序号，以便重新组装消息。可以将包进一步分成一些固定长度的片寻径信息和序号形成头片，其余的片是数据片。607.2.1消息寻径方式四种寻径方式60消息包片DDDDDDSRR：在消息传递网络中通信的信息单位：消息、包和片的格式R：导径信息S：序号D：数据片包消息包片据片头片尾片……顺序号数bbbbbbbb61消息包片DDDDDDSRR：在消息传递网络中通信的信息单位：在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位在采用虫蚀寻径网络的多计算机中，包可以进一步分成片。片的长度往往受网络大小的影响256个结点的网络需要片长为8位包的长度取决于寻径方式和网络的实现方法典型的包的长度为64～512位。序号可能占用1～2个片，取决于消息的长度包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关62在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单2、四种寻径方式两大类线路交换包交换(存储转发、虚拟直通和虫蚀寻径)(1)线路交换(circuitswitch)先建立一条从源结点到目的结点的物理通路，然后再传递消息传输时延公式T=(Lt/B)*D+L/B其中：Lt为建立路径所需小信息包的长度L为信息包的长度D为经过的结点数B为带宽优点：实际通信时间较短，使用缓冲区少缺点：建立源结点到目的结点的物理通路开销很大，占用物理通路时间长632、四种寻径方式两大类63(2)存储转发(storeandforward)每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点存储转发网络的时延与源和目的地之间的距离成正比。传输时延公式：T=(L/B)*D+L/B=(D+1)*L/B优点：占用物理通路的时间比较短缺点：包缓冲区大，时延大(与结点距离成正比)64(2)存储转发(storeandforward)每个结点(3)虚拟直通(virtualcutthrough)当接收到用作寻径的消息头部时，即开始路由选择。通信时延公式：T=(Lh/B)*D+L/B=(Lh*D+L)/B其中：Lh是消息的寻径头部的长度，一般有，L>>Lh×D；通信时延可以近似为：T=L/B与结点数无关当出现寻径阻塞时，只能将整个消息存储在寻径结点中主要优点：通信延迟与结点数无关主要缺点：每个结点需要有足够大的缓冲区来存储最大信息包在最坏的情况下与存储转发方式的通信时延是一样的，经过的每个结点都发生阻塞，都需缓冲65(3)虚拟直通(virtualcutthrough)当接(4)虫蚀寻径(wormhole)把包分成更小的片。每个结点的寻径器中有片缓冲区用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择如所选择的通道空闲且所选择的结点B的片缓冲区可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B随后的其它数据片跟着相应地向前“蠕动”一步当消息的尾片向前“蠕动”一步之后，它刚才所占有的结点就被放弃如果所选择的通道或的结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待通信时延用公式：T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B其中：Lf是片的长度，Tf是片经过一个结点所需时间。一般有L>>Lf×D，可近似为T=L/B，通信时延与结点数无关66(4)虫蚀寻径(wormhole)把包分成更小的片。每个结点虫蚀寻径的优点每个结点的缓冲区较小，易于VLSI实现较低的网络传输时延所有的片以流水方式向前传输，采用了时间并行性存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离虫蚀寻径方式的网络传输时延正比于消息包的长度，传输距离对它的影响很小通道共享性好，利用率高对通道的预约和释放是结合在一起的一个完整的过程有一段新的通道后将立即放弃用过的一段旧通道易于实现选播和广播通信方式允许寻径器复制消息包的片并把它们从其多个输出通道输出67虫蚀寻径的优点每个结点的缓冲区较小，易于VLSI实现67虫蚀寻径的缺点：当消息的一个片被阻塞时，整个消息都被阻塞，占用了结点资源需要采用虚拟通道的方式来避免由此引起的一连串的阻塞虫蚀寻径方式也可以分为无缓冲和有缓冲两类，区别在于缓冲的大小缓冲大有利于性能的提高，但会增加结点的复杂度IBMSP2采用的寻径方式就是带缓冲的虫蚀寻径方式，它采用共享的存储区来对输入/输出消息进行缓冲68虫蚀寻径的缺点：68图7.25几种寻径方式的时空图(a)线路开关寻径(1)N1-->N4(2)通过识别消息头部，N1接到N2，N2接到N3，N3接到N4(3)N1发送，以极小的延迟通过中间结点N2，N3到达N469图7.25几种寻径方式的时空图(a)线路开关寻径69(b)存储转发寻径(1)N1-->N4(2)N1发送到N2存储(3)N2转发到N3存储(4)N3转发到N470(b)存储转发寻径70(c)虫蚀寻径(1)N1-->N4(2)头片由N1寻径至N2，N1发送头片到N2存储(3)头片由N2寻径至N3，N2发送头片到N3存储

N1发送1号片到N2存储(4)头片由N3寻径至N4，N3发送头片到N4

N2发送1号片到N3存储

N1发送2号片到N2存储N1,N2,N3类似流水线的三段，头片,1号片,2号片类似流水线的三条指令

--------流水方式，蠕动，一个包传送完成前，蠕动路径不能和其他包的蠕动路径交叉头片逐个结点寻径，尾片逐个结点放弃蠕动路径71(c)虫蚀寻径717.2.2死锁和虚拟通道1虚拟通道虚拟通道是两个结点间的逻辑链由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成物理通道由所有的虚拟通道分时共享如图四条虚拟通道分时共享一条物理通道727.2.2死锁和虚拟通道1虚拟通道72物理通道四条虚拟通道以片传递为基础分时地共享一条物理通道73物理通道四条虚拟通道以片传递为基础分时地共享一条物理通道732死锁的产生和避免由于缓冲区或通道上的循环等待会引起死锁采用存储转发寻径的四个结点间出现缓冲区死锁DDDDD包缓冲区CCCCC包缓冲区BBBBB包缓冲区AAAAA包缓冲区742死锁的产生和避免由于缓冲区或通道上的循环等待会引起死锁D结点A结点D结点B结点Cm3m2m1m4寻径器C寻径器B片缓冲区消息1消息2消息3寻径器A消息4寻径器D采用虫蚀寻径的四个结点之间出现通道死锁75结点A结点D结点B结点Cm3m2m1m4寻径器C寻径器B片缓如何避免死锁缓冲区或通道上的循环等待会引起死锁利用虚拟通道方法可以减少死锁。增加两条虚拟通道V3和V4利用虚拟通道避免死锁虚拟通道可以用单向通道或者双向通道实现将两条单向通道组合在一起可以构成一条双向通道虚拟通道可能会使每个请求可用的有效通道频宽降低确定虚拟通道数目，需要对网络吞吐量和通信时延折衰考虑实现数目很大的虚拟通道需要用高速的多路选择开关76如何避免死锁缓冲区或通道上的循环等待会引起死锁76(b)包含循环的通道相关图 (d)利用虚拟通道后修改的通道相关图77777.2.3流控制策略1包冲突的解决在两个相邻结点之间传送片时，必须具备三个条件(1)源缓冲区已存有该片(2)通道已分配好(3)接收缓冲区准备接收该片接收缓冲区或输出通道冲突的仲裁(1)把后一个包暂时存放在缓冲区(2)阻塞后一个包(3)扬弃后一个包(4)绕道787.2.3流控制策略1包冲突的解决78图7.31解决两个包请求同一条输出通道发生冲突时的流控制方法(a)用缓冲实现虚拟直径寻径 (b)阻塞流控制(c)扬弃并重发 (d)阻塞后绕道79图7.31解决两个包请求同一条输出通道发生冲突时的流控制方法2确定寻径和自适应寻径如何找出一条从源结点到目的结点的路径来传送消息？寻径可以分为确定和自适应两类采用确定寻径时，通信路径完全由源和目的地址确定即寻找的路径是预先唯一确定的，与网络的状况无关自适应寻径与网络的状况有关，可能会有几条路径两种寻径都需要无死锁算法802确定寻径和自适应寻径如何找出一条从源结点到目的结点的路径来(1)确定寻径维序寻径算法按照多维网络维序的特定顺序来选择后继通道在二维网格网络中称为X-Y寻径首先沿着X维方向确定路径，然后沿着Y维方向选择路径在超立体(或n立方体)网络中，采用最初由Sullivan和Bashkow于1977年提出的称为E立方体寻径(E-cuberouting)方法。逐维改变(a)二维网格网络的X-Y寻径假定从任意源结点s=(x1，y1)到任意目的结点d=(x2，y2)寻径从s开始首先沿X方向前进一直到d所在的第x2列为止然后沿Y方向前进直到y2,即d总是首先沿X维方向寻径，然后再沿Y维方向寻径，寻径就不会出现死锁或循环等待81(1)确定寻径维序寻径算法81与东-北、东-南、西-北及西-南的路径方向相对应，X-Y寻径共有4种模式(2,1;7,6)东-北(0,7;4,2)东-南...82与东-北、东-南、西-北及西-南的路径方向相对应，X-Y寻径按照维序，可以很容易地将X-Y寻径扩充到n维网络以三维网格为例，可以类似地说明X-Y-Z寻径方法X-Y方式不会产生死锁寻径，可用于存储转发或虫蚀寻径网络，在源和目的结点之间形成一条距离最短的路径对于环网网络，采用维序寻径方法不能得到最短路径为了减少网络流量或其它原因，不会产生死锁的非最短寻径算法有时会使包通过的路径较长83按照维序，可以很容易地将X-Y寻径扩充到n维网络83(b)超立方体网络的E立方体寻径假设有一N=2n个结点的n方体。每个结点的二进制编码为b=bn-1bn-2…b1b0。这样，源结点为s=sn-1sn-2…s1s0，目的结点d=dn-1bn-2…d1d0现在要确定一条从s到d的步数最小的路径将n维表示成i=1，2，…，n，其中第i维对应于结点地址中的第i-1位。设u=un-1un-2…u1u0是路径中的任一结点路径可以根据以下方法唯一地确定①计算方向位ri=si-1⊕di-1，其中i=1，2，...，n。使i=1，v=s②如果ri=1，从当前结点u寻径到下一结点。如果ri=0，则跳过这一步③i←i+1。如果i≤n，则转第②步，否则退出寻径是按照从维1到维4的顺序进行的如果s和d的第i位相同，则沿维i方向不需要寻径否则从当前结点沿着这一维方向走到其它结点重复这一过程直到到达目的结点E立方体寻径也不会产生死锁寻径，也可用于存储转发和虫蚀网络，在源和结点之间形成一条距离最短的路径84(b)超立方体网络的E立方体寻径假设有一N=2n个结点的n图中，n=4，s=0110，d=1101r=r4r3r2r1=s⊕d=0110⊕1101=1011i=1,r1=1，v=s=0110寻径到v=v⊕2^0=0110⊕1=0111i=2,r2=1，v=0111寻径到v=v⊕2^1=0111⊕10=0101i=3,r3=0，跳过维i=3这一步i=4,r4=1，v=0101寻径到v=v⊕2^3=0101⊕1000=1101=d85图中，n=4，s=0110，d=110185(2)自适应寻径采用自适应寻径要特别注意避免死锁虚拟通道的概念使实现自适应寻径更经济和更灵活在网格连接网络中，同一维的所有连接都使用虚拟通道图7.34是一个用X-Y寻径的网格网络，在Y维上用了2对虚拟通道图7.34(c)中的虚拟网络可以用来避免消息在向西传输出现的死锁，因为所有向东的X通道都没有使用图7.34(d)中的虚拟网络使用另一组Y方向虚拟通道来支持只向东的传输不同的时刻使用两个虚拟网络，这样死锁就可以自动避免P424L3，X改成Y86(2)自适应寻径采用自适应寻径要特别注意避免死锁86图7.34利用虚拟通道避免死锁的自适应X-Y寻径(a)没有虚拟通道的原形网络 (b)Y维方向有两对虚拟通道

(c)向西方向传输信息 (d)向东方向传输信息c,d有循环等待吗87图7.34利用虚拟通道避免死锁的自适应X-Y寻径c,d有循图7.35是在X维和Y维方向各有两条虚拟通道的网格形网络这些虚拟通道可以用来生成4个虚拟网络西-北方向通信应该使用图7.35(b)所示的虚拟网络类似地，其它方向的通信可以构造另外3个虚拟网络注意，任何一个虚拟网络都不会出现环路在这些网络上实现X-Y寻径方法时，完全可以避免死锁如果相邻结点之间的两对通道都是物理通道，那么4个虚拟网络中任何两个都可以同时使用而不会产生冲突如果相邻结点之间双虚拟通道只能共享一对物理通道只有(b)和(e)或(c)和(d)可以同时使用其它组合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同时存在，因为缺少通道网络的通道数增加，寻径的自适应性也将增加成本的增加将很可观，要避免使用过多的资源P425L3，b和c改成b和e88图7.35是在X维和Y维方向各有两条虚拟通道的网格形网络88图7.35双通道网格网络可实现4个虚拟网络(a)双通道的3×3网络 (b)西-北子网 (c)东-北子网 (d)西-南子网 (e)东-南子网b,c,d,e有循环等待吗89图7.35双通道网格网络可实现4个虚拟网络b,c,d,e7.2.4选播与广播寻径算法四种通信模式(1)单播(unicast),一对一传送(2)选播(multicast),一个源结点发送同一个消息到多个目的结点(3)广播(broadcast),一个源结点发送同一个消息到全部结点(4)会议(conference),对应于多到多的通信情况907.2.4选播与广播寻径算法四种通信模式90广播与选播算法广播是将一个结点的数据复制到全部N个结点；选播是将一个结点的数据复制到多个(N'个)结点，1≤N'≤N研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数(又称"流量"或"通道数")最少的方案这里所说的并行传输，指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行(具有这种能力的互连网不属于现在的讨论范围)对不同的网络，适用的广播与选播算法也不同91广播与选播算法广播是将一个结点的数据复制到全部N个结点；选播选播选播算法的设计目标有3种：时间最少、流量最少、在时间最少的多个方案中选取流量最少方案选播时间最少算法是通过单播时间最少算法裁剪而成(教材P426图7.36(a)→(b))选播流量最少算法是最小成本生成树算法，具体操作顺序既可以是先短边后长边“长树”，也可以是先长边后短边“砍树”(教材P426图7.36(c))实现第3种目标的一种重要算法是贪婪算法(教材P426图7.36(b))不论对何种网络，贪婪算法总是重复使用一个固定的操作规则从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步如此循环，直至传遍所有需要数据的结点如果最后发现某个通道(即一次数据发送操作)不在通往给定目标结点的路径上，则应将其删去92选播选播算法的设计目标有3种：时间最少、流量最少、在时间最少扩散向最近的结点的方向移动1步5次点对点,1个流量为相邻结点一次传输向可达结点数最多的方向移动1步123444412364593扩散向最近的结点的方向移动1步5次点对点,向可达结点数最多的图7.37贪婪算法4立方体广播树和选播树(a)一个根结点为0000的4立方体。超立方体广播树的流量最小。(b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点94图7.37贪婪算法4立方体广播树和选播树(a)一个根结点为贪婪选播算法的基本思想是向那些可达到最多剩余目的结点的维方向发送包图7.37(a)是一个根结点为0000的4立方体。超立方体广播树的流量最小图7.37(b)是一棵贪婪选播树，可从结点0101发送包到7个目的结点从源结点S=0101开始，由维2方向可以到达2个目的结点，由维4方向可以达到5个目的结点。第1层所用的通道是0101→0111和0101→1101从结点1101，由维2方向可以到达3个目的结点，由维1方向可以到达4个目的结点。第2层所用的通道是1101→1111，1101→1100和0111→0110同理，第3层所用的通道是1111→1110，1111→1011，1100→1000和0110→0010第4层所用的通道是1110→101095贪婪选播算法的基本思想是向那些可达到最多剩余目的结点的维方向在扩充选播树时首先应该比较所有各维方向的可达性(reachability)然后选择某些维使剩余目的结点的集合最小如果两维之间有连线，那么选择其中任何一维都可以。因此，所生成的树不是唯一的已经证明贪婪选播算法所需的通道数与多次单播或广播树相比要少在虫蚀寻径网络中，实现选播操作时，每个结点的寻径器应有复制片缓冲区中数据的能力为了与选播树或广播树的增长同步，树中同一层的所有输出通道必须在传输向前推进一层之前处于就绪状态，否则中间结点需要增加缓冲区96在扩充选播树时96(1)单级网格网(Mash网)贪婪算法教材P426图7.36(a)指出总共有1个源结点S和5个目的结点图(b)指出从S出发，首先应向右邻结点发送数据，因为S的左方只有1个目的结点、上方有3个目的结点、右方有４个目的结点第二步从这2个拥有数据的结点出发，可以再向右发送(有3个目的结点)，也可以改向上发送(也有3个目的结点)，……只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都是相同的97(1)单级网格网(Mash网)贪婪算法教材P426图7.36教材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)所示，这时流量=2；如果先传bit1方向、再传bit0方向，如右图(b)所示，则流量=3(2)单级立方体网络贪婪算法98教材P426图7.37(a)指出广播算法的时间是4，流量是1教材P426图7.37(b)的例子。源结点编号的二进制形式0101在Cube0～Cube3位分别与5、5、4、5个目的结点的二进制形式不同，所以Cube2方向应该最后发送，其它3个方向的发送先后顺序则没有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=1099教材P426图7.37(b)的例子。源结点编号的二进制形式07.3互连网络实例着重研究下面几种多处理机的互连网络总线结构、环形互连、交叉开关、混洗交换互连等处理机系统采用哪种互连结构主要取决于系统的最大通信量反过来，系统的最大通信量受到互连结构的限制7.3互连网络实例着重研究下面几种多处理机的互连网络7.3.1总线互连目前，大部分处理机内部采用总线结构CPU与存储器之间有系统总线存储器与输入输出设备之间有I/O总线总线与总线之间通过总线桥连接总线的主要优点是结构简单，能够很方便实现广播通信总线的主要缺点是带宽低，发生总线冲突的可能性大总线冲突的解决办法有(1)设置静态优先级(2)在同步方式中采用时间片(3)采用动态优先级(如LRU法等)(4)先来先服务1017.3.1总线互连目前，大部分处理机内部采用总线结构101总线结构的多处理机102总线结构的多处理机102为了提高总线的通信带宽，有如下方法(1)采用多总线结构(2)层次总线结构(3)多维总线结构多总线西门子公司的SMS系统(StracturedMultiprocessorSystem)通过8条总线连接128个处理机层次总线卡内基梅隆大学的Cm*多处理机系统采用层次总线结构三级总线：群总线、Map总线、处理机总线每群14台处理机为了提高总线的通信带宽，有如下方法主机P1P2P16P17P18P32P113P114P128………………………………总线驱动器SMS多总线结构主机P1P2P16P17P18P32P113P114P128卡内基梅隆大学的Cm*层次总线结构CmCmCm…KmCmBCm…KmCmCmCm…Km…MIOP群间总线卡内基梅隆大学的Cm*层次总线结构CmCmCm…KmCmBC7.3.2环形互联一种互连方法，它既能具有总线型互连的简单性，又可以克服总线所固有的缺点信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止1067.3.2环形互联一种互连方法，它既能具有总线型互连的简单性IEEE802.5令牌环(TokenRing)IEEE802.5令牌环(TokenRing)标准是把环形看作逻辑总线的协议发送信息的处理机拥有一个唯一的令牌，在同一时刻只有一台处理机持有这个令牌当发送者发送信息时，这个环形网络的作用如同总线一样，其它处理机都处于接收信息的状态信息传送结束时，发送者播送一个令牌，这个令牌是在普通信息中不会出现的特定信号。每台处理机依次看到令牌如果某台处理机等待发送信息，那么它便接收这个令牌而不再传递给下一台处理机，这时这台处理机就可以通过环形网络发送信息了假如没有想发送信息的处理机，那么令牌就将在环形网络上不断循环，直到某台处理机需要发送信息为止107IEEE802.5令牌环(TokenRing)IEEE令牌环的优点是点点连接，而不是总线连接，其物理参数更容易控制令牌环形互连非常适于高带宽的光纤通信。N较小的总线互连系统很难采用光纤通信，N较大的系统也还未实现令牌环形互连的一个主要缺点是每个总线接口都有延迟通常是1位的延迟当互连处理机台数增加时，在环中的信息传输延迟将正比例地增加但是当系统负载很重时，系统的带宽却不会像总线互连系统那样下降108令牌环的优点是点点连接，而不是总线连接，其物理参数更容易控制7.3.3交叉开关互连交叉开关网络，它把N台处理机和N个存储器连接起来图中处理机台数与存储器个数相等，一般情况是存储器数目等于或是处理机数目的几倍网络中每个交叉点是一个允许任何一台处理器与任何一个存储器连接的开关7.3.3交叉开关互连交叉开关网络，它把N台处理机和N个系统允许N个存取操作并行执行任意两个存取操作不能涉及同一台处理机或同一个存储器如果两个或两个以上存取操作同时要访问某个存储器，那么争用现象就发生了如处理机P1和P2同时要访问存储器M1减少争用，在系统结构方面大有文章可做如果争用是由于多台处理机同时要访问同一存储模块中不同单元的数据而引起的，一种解决争用的方法是尽量使这些数据平均地分配到多个不同的存储模块中，而不要把它们集中在一个存储模块中把一个数据块中数据依次分配到相继的存储模块中同样，共享程序代码也应该这样分配这样，当两台或两台以上的处理机同时访问共享程序代码或数据时，争用只使其中一台处理机延迟一个周期只要两台处理机顺序地不断地访问，两者不会再发生冲突这种寻址技术也可用于流水线多处理机中，使各台处理机能彼此步调一致地存取向量数据110系统允许N个存取操作并行执行1107.3.4混洗交换互连和合并开关混洗交换网络能提供一种重要的功能，称为合并开关它使某些操作在网络一级并行地执行，从而减少争用现象否则这些需要访问存储器的操作只能串行地执行对那些需要互斥地访问共享变量的进程来说，这种方法很有潜力互斥地访问共享变量限制了大部分多处理机系统的性能当出现多个进程要存取某个共享变量时，无论系统再增加多少台处理机也不可能再提高其速度1117.3.4混洗交换互连和合并开关混洗交换网络能提供一种重要8台处理器和8个存储器通过混洗交换互连网络连接1128台处理器和8个存储器通过混洗交换互连网络连接1127.3.5Omega网络采用了全混洗函数和交换函数，又称为混洗交换网络Omega网已经用于伊利诺依大学的Cedar多处理机、IBM的RP3系统和纽约大学Ultracomputer中N个输入的Omega网络有log2N级每级有N/2个2×2的四功能交换开关每级的拓扑结构相同采用单元控制(每一级的控制信号均相同)能够实现任意一个输入端到任意一个输出端的连接不能同时实现多个输入端到多个输出端的连接通过检查二进制目的地址编码来控制数据路径目的地址编码从高位开始的第i位为0时，第i级的2×2开关的输入端与上输出端连接，否则输入端与下输出端连接1137.3.5Omega网络采用了全混洗函数和交换函数，又称为混8个输入端的Omega网络2路洗牌相当于8个输入端平均地分成2个子组，然后2个子组均匀地洗牌同时实现06和47有冲突冲突的还有：30和51，30和73，50和71等01230101011148个输入端的Omega网络0开关设置从输入端001到输出端011的路径。它使用了开关A、B、C目的地址编码011的最高位“0”，输入端001与开关A的上输出端(编号为2)连接,开关A设置成直送状态011的次高位是“1”，输入端4和下输出端连接，开关B设置成交换状态011的最低位是“1”，输入端4和下输出端连接，开关C设置成直送状态输入端101到输出端101的路径？115开关设置115116116如果采用级控制，是STARAN交换网的逆网如果采用部分级控制，是STARAN移数网的逆网因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况Omega网属于多级互连网当有N个输入端时，共有N^(N/2)个变换要同时实现任意一个输入端到任意一个输出端的连接，总共需要N!个变换8个输入端的Omega网络实际上只能实现全部变换的10%(8^4/8!=4096/40320=0.1016)，有90%的变换将引起阻塞Omega网络是一种阻塞网络，采用多次通过来解决冲突有N个输入端时，实现连接的通过次数最多为log2N117如果采用级控制，是STARAN交换网的逆网117Omega网能够实现从任意一个输入端到所有输出端的广播采用上播或下播开关设置118Omega网能够实现从任意一个输入端到所有输出端的广播采用上用4×4开关元件作为构成块的Omega网络用4×4开关元件作为构成块的Omega网络，级间是4路洗牌连接，而不是2路洗牌连接16个输入端的Omega网络的级数为log416=24路洗牌相当于16个输入端平均地分成4个子组，然后4个子组均匀地洗牌采用k×k开关元件时，可以定义k路洗牌函数来构造更大的级数为logkn的Omega网络012301230123119用4×4开关元件作为构成块的Omega网络用4×4开关元件作017017蝶式网络16个8×8交叉开关构成的两级64×64碟式网络

64个输入端的蝶式网络由2级(2=logkn=log864)8×8交叉开关组成开关数16=8+8=nlogkn/k=64*log864/8级间采用8路洗牌连接，64/8组(路)=8个结点/组第0个8×8模块的输出连至第1级的各个开关的第0个输入0输出连至第1级的第0个开关的第0个输入1输出连至第1级的第1个开关的第0个输入...7输出连至第1级的第7个开关的第0个输入第1个8×8模块的输出连至第1级的各个开关的第1个输入0输出连至第1级的第0个开关的第1个输入1输出连至第1级的第1个开关的第1个输入...7输出连至第1级的第7个开关的第1个输入...第7个8×8模块的输出连至第1级的各个开关的第7个输入0输出连至第1级的第0个开关的第7个输入1输出连至第1级的第1个开关的第7个输入...7输出连至第1级的第7个开关的第7个输入12000192个8×8交叉开关构成的三级512×512碟式网络512个输入端的蝶式网络级间采用64路洗牌连接(从第2级向左看，8个结点一组，512/8=64组(路))从第0,1级向右看，64个结点一组，512/64=8组(路)，8路洗牌，第2级8个8×8开关构成一个64个结点的组和第0,1级的8个组连接3级(3=logkn=log8512)8×8开关组成16个8×8开关构成的两级64×64碟式网络64×64碟式网络共8个第2级8个8×8交叉开关构成64路连接64路连接共512/64=8组用这种模块结构构造更大的蝶式网络只要增加级数即可开关数192=16x8+8x8=nlogkn/k=512x3/8蝶式网络不允许广播连接，所以蝶式网络是Omega网络的一个有限的子集每个64×64的方框相当于图7.45(a)中的两级蝶式网络00x81x817

x863121192个8×8交叉开关构成的三级512×512碟式网络512级间采用64路洗牌连接(从第2级向左看，8个结点一组，512/8=64组(路))从第0,1级向右看，64个结点一组，512/64=8组(路)，8路洗牌，第2级8个8×8开关构成一个64个结点的组和第0,1级的8个组连接第0个64×64模块的输出连至第2级的各个开关的第0个输入0输出连至第2级的第0个开关的第0个输入1输出连至第2级的第1个开关的第0个输入...63输出连至第2级的第63个开关的第0个输入第1个64×64模块的输出连至第2级的各个开关的第1个输入0输出连至第2级的第0个开关的第1个输入1输出连至第2级的第1个开关的第1个输入...63输出连至第2级的第63个开关的第1个输入...第63个64×64模块的输出连至第2级各个开关的第7个输入0输出连至第2级的第0个开关的第7个输入1输出连至第2级的第1个开关的第7个输入...63输出连至第2级的第63个开关的第7个输入122级间采用64路洗牌连接(从第2级向左看，8个结点一组，5127.3.6蝶形操作略1237.3.6蝶形操作略1237.3.7合并网络和取与加指令略1247.3.7合并网络和取与加指令略124计算机系统结构第一章基本概念第二章指令系统第三章存储系统第四章输入输出系统第五章标量处理机第六章向量处理机第七章互连网络第八章并行处理机第九章多处理机125计算机系统结构第一章基本概念1互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接第七章互连网络126互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网第七章互连网络互连网络的基本概念消息传递机制127第七章互连网络互连网络的基本概念37.1互连网络的基本概念互连网络的作用互连函数互连网络的特性和传输的性能参数互连网络的种类1287.1互连网络的基本概念互连网络的作用47.1.1互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。为并行处理系统的核心组成部分。对整个计算机系统的性能价格比有着决定性的影响。1297.1.1互连网络的作用用来实现计算机系统内部多个处理机或多具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构IPMN(处理机-存储器网络)PION(处理机-I/O网络)IPCN(处理机之间通信网络)P(处理机)C(高速缓冲存储器)SM(共享存储器)LM(本地存储器)磁盘SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)130具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般7.1.2互连函数互连函数将互连网的N个输入和N个输出端分别用整数(0,1,2,...,N-1)来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系表示方法：互连函数法，图形表示法,输入输出对应表示法函数表示法：x表示输入端号，常用n位二进制形式表示xn-1xn-2...x1x0f(x)表示互连函数，为：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称为该循环的长度012...N-1f(0)f(1)f(2)...f(N-1)1317.1.2互连函数互连函数012...常用的互连函数如下：1恒等置换：

I(xn-1xn-2...

x1x0)=xn-1xn-2...x1x0132常用的互连函数如下：1恒等置换：82交换置换Exchange实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。

E(xn-1xn-2...

x1x0)=xn-1xn-2...

x1x0其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换1332交换置换Exchange实现二进制地址编号中第0位位值不3、方体置换Cube当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。用交换函数构成的互连网络的结点度为n，网络直径也为n。1343、方体置换Cube10变化发生在0，1，2位分别是高2，1，0位相同的为一个组组内加/减1，2，4C0C2C1135变化发生在0，1，2位C0C2C1114、均匀洗牌置换Perfectshuffle把二进制结点循环左移一位。子混洗(subshuffle)S(k)最低k位循环左移一位超混洗牌(supershuffle)S(k)最高k位循环左移一位显然成立：逆混洗函数：教材P397L2,3,6错1364、均匀洗牌置换Perfectshuffle124、均匀洗牌置换Perfectshuffle子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2)分两组0，1，2，3；4，5，6，7只用均匀洗牌函数不能实现任意结点之间的互连通常用均匀洗牌函数与其他函数，如交换函数一起构成互连网络。均匀洗牌与逆均匀洗牌是两种十分有用的互连函数以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega(Ω)网络与逆Omega(Ω^-1)网络。

逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换1374、均匀洗牌置换Perfectshuffle135、蝶式置换Butterfly蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)最低k位的最高位与最低位互换位置超蝶式(superbutterfly)B(k)最高k位的最高位与最低位互换位置显然成立教材P398L1,2错1385、蝶式置换Butterfly蝶式函数的名称来自于FFT变换5、蝶式置换Butterfly与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。1395、蝶式置换Butterfly156、