第9章-互连网络-PPT.ppt

《第9章-互连网络-PPT.ppt》由会员分享，可在线阅读，更多相关《第9章-互连网络-PPT.ppt（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9章 互连网络9.1互连函数9.2互连网络的结构参数与性能指标9.3静态互连网络9.4动态互连网络9.5消息传递机制2 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其它设备。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。SIMD计算机和MIMD计算机的关键组成部分。3大要素：互连结构，开关元件，控制方式。3 变量x：输入（设x=0，1，N1）函数f(x)：输出 通过数学表达式建立输入端号与输出端号的连接关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数

2、组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）（有时也称为置换函数或排列函数）9.1.1 互连函数9.1 互连函数49.1 互连函数互连函数f(x)有时可以采用循环表示 即：（x0 x1 x2 xj-1）表示：f(x0)=x1，f(x1)=x2，f(xj-1)=x0 j称为该循环的长度。设n=log2N，则可以用n位二进制来表示N个输入端和输出端的二进制地址，互连函数表示为：f（xn-1xn-2x1x0）59.1 互连函数介绍几种常用的基本互连函数及其主要特征。恒等函数 恒等函数：实现同号输入端和输出端之间的连接。I（xn-1xn-2x1x0）=xn-1xn-2x1x0 交换

3、函数 交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。9.1.2 几种基本的互连函数69.1 互连函数主要用于构造立方体互连网络和各种超立方体互连网络。它共有nlog2N种互连函数。（N N为结点个数）为结点个数）当N8时，n3，可得到常用的立方体互连函数：79.1 互连函数q变换图形变换图形N=8 N=8 的立方体交换函数的立方体交换函数 8大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点99.1 互连函数立方体网络立方体网络109.1 互连函数均匀洗牌函数均匀

4、洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。q也称为混洗函数（置换）也称为混洗函数（置换）q函数关系函数关系 即把输入端的二进制编号循环左移一位。即把输入端的二进制编号循环左移一位。119.1 互连函数互连函数（设为s）的第k个子函数：把s作用于输入端的二进制编号的低k位。互连函数（设为s）的第k个超函数：把s作用于输入端的二进制编号的高k位。例如：对于均匀洗牌函数例如：对于均匀洗牌函数第第k k个子函数：个子函数：(k)(k)(x(xn-1n-1 x xk kxxk-1k-1x xk-2k-2 x x0 0)x

5、xn-1n-1xxk kxxk-2k-2xx0 0 x xk-1k-1 即把输入端的二进制编号中的低即把输入端的二进制编号中的低k k位循环左移一位。位循环左移一位。第第k个超函数：个超函数：(k)(xn-1xn-2 xn-k xn-k-1 x1x0)xn-2xn-k xn-1 xn-k-1x1x0 即把输入端的二进制编号中的高即把输入端的二进制编号中的高k位循环左移一位。位循环左移一位。129.1 互连函数 下列等式成立：下列等式成立：(n)(X)(n)(X)(X)(1)(X)(1)(X)X对于任意一种函数f(x)，如果存在g(x)，使得 f(x)g(x)=I(x)则称g(x)是f(x)的逆

6、函数，记为f-1(x)。f-1(x)=g(x)逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。139.1 互连函数q互连函数互连函数p逆均匀洗牌是均匀洗牌的逆函数逆均匀洗牌是均匀洗牌的逆函数 当N=8时，有：(x2x1x0)x1x0 x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0 -1(x2x1x0)x0 x2x1149.1 互连函数qN=8 N=8 的均匀洗牌和逆均匀洗牌函数的均匀洗牌和逆均匀洗牌函数 N=8 N=8 的均匀洗牌函数的均匀洗牌函数159.1 互连函数碟式函数 蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，

7、便得到了输出端的编号。第k个子函数 (k)(xn-1xkxk-1xk-2x1x0)xn-1xkx0 xk-2x1xk-1 把输入端的二进制编号的低把输入端的二进制编号的低k k位中的最高位与最低位互换。位中的最高位与最低位互换。第k个超函数 (k)(xn-1xn-2xn-k+1xn-kxn-k-1x1x0)xn-kxn-2xn-k+1xn-1xn-k-1x1x0 把输入端的二进制编号的高把输入端的二进制编号的高k k位中的最高位与最低位互换。位中的最高位与最低位互换。169.1 互连函数下列等式成立 (n)(X)(n)(X)(X)(1)(X)(1)(X)X当N=8时，有：(x2x1x0)x0

8、x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0蝶式变换与交换变换的多级组合可作为构成方体多级网络的基础。179.1 互连函数N=8 N=8 的蝶式函数和反位序函数的蝶式函数和反位序函数 189.1 互连函数反位序函数 反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。q互连函数互连函数 第k个子函数 (k)(xn-1xkxk-1xk-2x1x0)xn-1xkx0 x1xk-2xk-1即把输入端的二进制编号的低即把输入端的二进制编号的低k位中各位的次序颠倒过来。位中各位的次序颠倒过来。199.1 互连函数第k个超函数 (k)(xn-1xn-2x

9、n-k+1xn-kxn-k-1x1x0)xn-kxn-k+1xn-2xn-1xn-k-1x1x0即把输入端的二进制编号的高即把输入端的二进制编号的高k位中各位的次序颠倒过来。位中各位的次序颠倒过来。下列等式成立 (n)(X)(n)(X)(X)(1)(X)(1)(X)X当N=8时，有：(x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x020移数函数移数函数：将各输入端都错开一定的位置（模N）后连到输出端。q函数式函数式 (x)=（xk）mod N 1xN-1，1kN-1 219.1 互连函数1.PM2I函数 P和M分别表示加和减，2I表示2i。

10、q该函数又称为该函数又称为“加减加减2i”函数。函数。PM2I函数：一种移数函数，将各输入端都错开一定的位置（模N）后连到输出端。互连函数 PM2+i(x)x2i mod N PM2-i(x)x2i mod N 其中：其中：0 xN0 xN1 1，0in0in1 1，n nloglog2 2N N，N N为结点数。为结点数。PM2I互连网络共有2n个互连函数。229.1 互连函数当N8时，有6个PM2I函数：qPM2PM2+0+0 ：（：（0 1 2 3 4 5 6 70 1 2 3 4 5 6 7）qPM2PM2-0-0 ：（：（7 6 5 4 3 2 1 07 6 5 4 3 2 1 0）

11、qPM2PM2+1+1 ：（：（0 2 4 6 0 2 4 6）（）（1 3 5 71 3 5 7）qPM2PM2-1-1 ：（：（6 4 2 06 4 2 0）（）（7 5 3 17 5 3 1）qPM2PM2+2+2：（：（0 40 4）（）（1 51 5）（）（2 62 6）（）（3 73 7）qPM2PM2-2-2：（：（4 04 0）（）（5 15 1）（）（6 26 2）（）（7 37 3）239.1 互连函数N=8 N=8 的的PM2IPM2I函数函数24阵列计算机ILLIAC 采用采用PM2PM200和和PM2PM2n/2n/2构成其互连网络，实现各构成其互连网络，实现各处理单

12、元之间的上下左右互连处理单元之间的上下左右互连 。用移数函数构成用移数函数构成ILLIAC ILLIAC 阵列机的互连网络阵列机的互连网络259.1 互连函数 例例9.1 9.1 现有现有1616个处理器，编号分别为个处理器，编号分别为0 0，1 1，1515，用一个，用一个N=16N=16的互连网络互连。处理器的互连网络互连。处理器i i的输出通道连接互连网络的输入端的输出通道连接互连网络的输入端i i，处理器，处理器i i的输入通道连接互连网络的输出端的输入通道连接互连网络的输出端i i。当该互连网络实现。当该互连网络实现的互连函数分别为：的互连函数分别为：（1 1）CubeCube3 3

13、 （2 2）PM2PM2+3+3 （3 3）PM2PM2-0-0 （4 4）（5 5）()()时，分别给出与第时，分别给出与第1313号处理器所连接的处理器号。号处理器所连接的处理器号。269.1 互连函数 解：（解：（1）由）由 ，得得Cube3（1101）=0101，即处理器，即处理器13连接到处理器连接到处理器5。令令Cube3（x3x2x1x0）=1101，得，得x3x2x1x0=0101，故与处理器，故与处理器13相连的相连的是处理器是处理器5。所以处理器所以处理器13与处理器与处理器5双向互连。双向互连。（2）由）由PM2+3=j+23 mod 16，得，得PM2+3（13）=13

14、+23=5，即处理器即处理器13连接到处理器连接到处理器5。令令PM2+3（j）=j+23 mod 16=13，得，得j=5，故与处理器，故与处理器13相连的是处理器相连的是处理器5。所以处理器所以处理器13与处理器与处理器5双向互连。双向互连。（3）由）由PM2-0（j）=j-20 mod 16，得，得PM2-0（13）=13-20=12，即处理器，即处理器13连接到处理器连接到处理器12。令令PM2-0（j）=j-20 mod 16=13，得，得j=14，故与处理器，故与处理器13相连的是处理器相连的是处理器14。所以处理器所以处理器13连至处理器连至处理器12，而处理器，而处理器14连至

15、处理器连至处理器13。279.1 互连函数 （4）由）由(x3x2x1x0)=x2x1x0 x3，得，得(1101)=1011，即处理器，即处理器13连连接到处理器接到处理器11。令令(x3x2x1x0)=1101，得，得x3x2x1x0=1110，故与处理器，故与处理器13相连的相连的是处理器是处理器14。所以处理器所以处理器13连至处理器连至处理器11，而处理器，而处理器14连至处理器连至处理器13。（5）由）由(x3x2x1x0)=x1x0 x3x2，得，得(1101)=0111，即处理，即处理器器13连接到处理器连接到处理器7。令令(x3x2x1x0)=1101，得，得x3x2x1x0

16、=0111，故与处理器，故与处理器13相连相连的是处理器的是处理器7。所以处理器所以处理器13与处理器与处理器7双向互连。双向互连。281.网络通常是用有向边或无向边连接有限个结点的图来表示。2.互连网络的主要特性参数有：网络规模N：网络中结点的个数。表示该网络所能连接的部件的数量。表示该网络所能连接的部件的数量。结点度d：与结点相连接的边数（通道数），包括入度和出度。9.2 互连网络的结构参数与性能指标9.2.1 互连网络的结构参数299.2 互连网络的结构参数与性能指标q进入结点的边数叫入度。进入结点的边数叫入度。q从结点出来的边数叫出度。从结点出来的边数叫出度。结点距离：对于网络中的任意

17、两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径D：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。网络直径应当尽可能地小。等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。309.2 互连网络的结构参数与性能指标q线等分宽度：线等分宽度：B Bbwbwn其中：其中：w w为通道宽度（用位表示）为通道宽度（用位表示）n该参数主要反映了网络最大流量。该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。对称网络比较容易实现，编程也比较容

18、易。319.2 互连网络的结构参数与性能指标评估互连网络性能的两个基本指标：时延和带宽1.通信时延 指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成：软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间。q主要取决于两端端结点处理消息的软件内核。主要取决于两端端结点处理消息的软件内核。通道时延：通过通道传送消息所花的时间。p通路时延通路时延=消息长度消息长度/通道带宽通道带宽p通常由瓶颈链路的通道带宽决定。通常由瓶颈链路的通道带宽决定。9.2.2 互连网络的性能指标329.2 互连网络的结构参数与性能指标选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。q与

19、传送路径上的结点数成正比。与传送路径上的结点数成正比。竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。q很难预测，它取决于网络的传输状态。很难预测，它取决于网络的传输状态。1.网络时延 通道时延与选路时延的和。q它是由网络硬件特征决定的，与程序行为和网络传输它是由网络硬件特征决定的，与程序行为和网络传输状态无关。状态无关。339.2 互连网络的结构参数与性能指标1.端口带宽对于互连网络中的任意一个端口来说，其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。q在对称网络中，端口带宽与端口位置无关。网络的端在对称网络中，端口带宽

20、与端口位置无关。网络的端口带宽与各端口的端口带宽相同。口带宽与各端口的端口带宽相同。q非对称网络的端口带宽则是指所有端口带宽的最小值。非对称网络的端口带宽则是指所有端口带宽的最小值。2.聚集带宽 网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。349.2 互连网络的结构参数与性能指标 例如，例如，HPS是一种对称网络是一种对称网络 网络规模网络规模N的上限：的上限：512 端口带宽：端口带宽：40MB/s HPS的聚集带宽：（的聚集带宽：（40MB/s512）/210.24GB/s 1.等分带宽 与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量。35互连网络通常可

21、以分为两大类：静态互连网络 各结点之间有固定的连接通路、且在运行中不能各结点之间有固定的连接通路、且在运行中不能改变的网络。改变的网络。动态互连网络 由交换开关构成、可按运行程序的要求动态地改由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。变连接状态的网络。下面介绍几种静态互连网络。（其中：（其中：N N表示结点的个数）表示结点的个数）9.3 静态互连网络369.3 静态互连网络1.线性阵列 一种一维的线性网络，其中N个结点用N-1个链路连成一行。q端结点的度：端结点的度：1 1q其余结点的度：其余结点的度：2 2q直径：直径：N N1 1q等分宽度等分宽度b=1 b=1 379.

22、3 静态互连网络389.3 静态互连网络q对称对称q结点的度：结点的度：2 2q双向环的直径：双向环的直径：N/2N/2q单向环的直径：单向环的直径：N N q环的等分宽度环的等分宽度b=2 1.环和带弦环 环 用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。399.3 静态互连网络带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。409.3 静态互连网络全连接网络 q结点度：结点度：1515q直径最短，为直径最短，为1 1。411.循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。N=16N=16q结点度：结点度：7

23、7q直径：直径：2 2 429.3 静态互连网络一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），则结点i与结点j连接。q结点度：结点度：2n2n1 1q直径：直径：n/2n/2q网络规模网络规模N=2n439.3 静态互连网络1.树形和星形 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。q最大结点度：最大结点度：3 3q直径：直径：2(k-1)2(k-1)q等分宽度等分宽度b=1 星形 q结点度较高，为结点度较高，为N N1 1。q直径较小，是一常数直径较小，是一常数2 2。等分宽度等分宽度b=N/2 q可靠性比较差，只要中心结点出故障

24、，整个系统就会可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。瘫痪。449.3 静态互连网络459.3 静态互连网络1.胖树形 469.3 静态互连网络1.网格形和环网形 网格形q一个一个3333的网格形网络的网格形网络q一个规模为一个规模为N=nn的的2维网格形网络维网格形网络n内部结点的度内部结点的度d=4n边结点的度边结点的度d=3n角角结点的度结点的度d=2n网络直径网络直径D=2（n-1）n等分宽度等分宽度b=nq一个由一个由N=nk 个结点构成的个结点构成的k维网格形网络（每维维网格形网络（每维n个结个结点）的内部结点度点）的内部结点度d=2k，网络直径，网络直径D=k(n-1

25、)。479.3 静态互连网络Illiac网络 q名称来源于采用了这种网络的名称来源于采用了这种网络的Illiac 计算机计算机 q把把2维网格形网络的每一列的两个端结点连接起来，维网格形网络的每一列的两个端结点连接起来，再把每一行的尾结点与下一行的头结点连接起来，并再把每一行的尾结点与下一行的头结点连接起来，并把最后一行的尾结点与第一行的头结点连接起来。把最后一行的尾结点与第一行的头结点连接起来。q一个规模为一个规模为nn的的Illiac网络网络n所有结点的度所有结点的度d=4n网络直径网络直径D=n-1 Illiac网络的直径只有纯网格形网络直径的一半。网络的直径只有纯网格形网络直径的一半。

26、n等分宽度：等分宽度：2n489.3 静态互连网络环网形q可看作是直径更短的另一种网格。可看作是直径更短的另一种网格。q把把2维网格形网络的每一行的两个端结点连接起来，维网格形网络的每一行的两个端结点连接起来，把每一列的两个端结点也连接起来。把每一列的两个端结点也连接起来。q将环形和网格形组合在一起，并能向高维扩展。将环形和网格形组合在一起，并能向高维扩展。q一个一个nnnn的的环网形网环网形网 n结点度：结点度：4 4n网络直径：网络直径：22 n/2n/2 n等分宽度等分宽度b=2n 499.3 静态互连网络（a a）网格形）网格形（b b）IlliacIlliac网网（c c）环网形）环

27、网形509.3 静态互连网络1.超立方体 一种二元n-立方体结构一般来说，一个二元n-立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。例例 8 8个结点的个结点的3 3维立方体维立方体 4 4维立方体维立方体为实现一个n-立方体，只要把两个（n1）立方体中相对应的结点用链路连接起来即可。共需要2n-1条链路。n-立方体中结点的度都是n，直径也是n，等分宽度为b=N/2。519.3 静态互连网络529.3 静态互连网络1.带环立方体（简称3-CCC）把3-立方体的每个结点换成一个由3个结点构成的环而形成的。带环k-立方体（简称k-CCC）qk-立方体的变形，它是通过用立方体的变形

28、，它是通过用k个结点构成的环取代个结点构成的环取代k-立方体中的每个结点而形成的。立方体中的每个结点而形成的。q网络规模为网络规模为N=k2kq网络直径为网络直径为D=2k-1+k/2 n比比k-立方体的直径大一倍立方体的直径大一倍q等分宽度为等分宽度为b=N/（2k）539.3 静态互连网络1234 k k-15 k k-112345(b)(b)将将k-k-立立方方体体的的每每个个结结点点用用由由k k个个结结点点的的环来代替，组成带环环来代替，组成带环k-k-立方体组成立方体组成549.3 静态互连网络1.k元n-立方体网络环形、网格、环网形、二元n-立方体（超立方体）和Omega网络都是

29、k元n-立方体网络系列的拓扑同构体。在k元n-立方体网络中，参数n是立方体的维数，k是基数，即每一维上的结点个数。N=kn，（，（，n=logkN）k元n-立方体的结点可以用基数为k的n位地址A=a1a2an来表示。q其中其中ai表示该结点在第表示该结点在第i维上的位置维上的位置通常把低维k元n-立方体称为环网，而把高维k元n-立方体称为超立方体。559.3 静态互连网络4元元3-立方体网络立方体网络 56静态互连网络特征一览表静态互连网络特征一览表 579.3 静态互连网络 例例9.2 已知有已知有16台个处理器用台个处理器用Illiac网络互连，写出网络互连，写出Illiac网络的网络的互

30、连函数，给出表示任何一个处理器互连函数，给出表示任何一个处理器PUi（0i15）与其他处理器）与其他处理器直接互连的一般表达式。直接互连的一般表达式。解：解：Illiac网络连接的结点数网络连接的结点数N=16，组成，组成44的阵列。每一列的的阵列。每一列的4个处理器互连为一个双向环，第个处理器互连为一个双向环，第1列第列第4列的双向环可分别用循环列的双向环可分别用循环互连函数表示为：互连函数表示为：（0 4 8 12）（12 8 4 0）（1 5 9 13）（13 9 5 1）（2 6 10 14）（14 10 6 2）（3 7 11 15）（15 11 7 3）其中，传送方向为顺时针的其中

31、，传送方向为顺时针的4个单向环的循环互连函数可表示为：个单向环的循环互连函数可表示为：PM2+2（X）=（X+22）mod N=（X+4）mod 16589.3 静态互连网络 传送方向为逆时针的传送方向为逆时针的4个单向环的循环互连函数可表示为：个单向环的循环互连函数可表示为：PM2-2（X）=（X-22）mod N=（X 4）mod 16 16个处理器由个处理器由Illiac网络的水平螺线互连为一个双向环，用循环网络的水平螺线互连为一个双向环，用循环互连函数表示为：互连函数表示为：（0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15）（15 14 13 12 11 1

32、0 9 8 7 6 5 4 3 2 1 0）其中，传送方向为顺时针的单向环的循环互连函数可表示为：其中，传送方向为顺时针的单向环的循环互连函数可表示为：PM2+0（X）=（X+20）mod N=（X+1）mod 16 传送方向为逆时针的单向环的循环互连函数可表示为：传送方向为逆时针的单向环的循环互连函数可表示为：PM2-0（X）=（X 20）mod N=（X 1）mod 16所以，所以，N=16的的Illiac网络的互连函数有网络的互连函数有4个：个：PM20（X）和）和PM22（X）599.3 静态互连网络由互连函数可得任何一个处理器由互连函数可得任何一个处理器i直接与下述直接与下述4个处理

33、器双向互连：个处理器双向互连：i1 mod 16 i4 mod 16601.由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。多个功能模块之间的争用总线或时分总线 特点q结构简单、实现成本低、带宽较窄结构简单、实现成本低、带宽较窄9.4.1 总线网络9.4 动态互连网络619.4 动态互连网络1.一种由总线连接的多处理机系统 629.4 动态互连网络q系统总线在处理机、系统总线在处理机、I/O子系统、主存储器以及辅助子系统、主存储器以及辅助存储设备（磁盘、磁带机等）之间提供了一

34、条公用通存储设备（磁盘、磁带机等）之间提供了一条公用通路。路。q系统总线通常设置在印刷电路板底板上。处理器板、系统总线通常设置在印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板。存储器板和设备接口板都通过插座或电缆插入底板。1.解决总线带宽较窄问题：采用多总线或多层次的总线多总线是设置多条总线有两种做法：有两种做法：q为不同的功能设置专门的总线为不同的功能设置专门的总线q重复设置相同功能的总线重复设置相同功能的总线多层次的总线是按层次的架构设置速度不同的总线，使得不同速度的模块有比较适合的总线连接。639.4 动态互连网络1.单级开关网络 交叉点开关能在对偶（源、目的）

35、之间形成动态连接，同时实现多个对偶之间的无阻塞连接。带宽和互连特性最好。一个nn的交叉开关网络，可以无阻塞地实现n!种置换。对一个nn的交叉开关网络来说，需要n2套交叉点开关以及大量的连线。q当当n很大时，交叉开关网络所需要的硬件数量非常巨很大时，交叉开关网络所需要的硬件数量非常巨大。大。9.4.2 交叉开关网络649.4 动态互连网络1.C.mmp多处理机的互连结构 用1616的交叉开关网络把16台PDP-11处理机与16个存储模块连在一起最多可同时实现16台处理机对16个不同存储模块的并行访问q每个存储模块一次只能满足一台处理机的请求每个存储模块一次只能满足一台处理机的请求q当多个请求要同

36、时访问同一存储模块时，交叉开关就当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点必须分解所发生的冲突，每一列只能接通一个交叉点开关。开关。q为了支持并行（或交叉）存储器访问，可以在同一行为了支持并行（或交叉）存储器访问，可以在同一行中接通几个交叉点开关。中接通几个交叉点开关。659.4 动态互连网络669.4 动态互连网络1.Fujitsu公司制造的向量并行处理机VPP500所采用的大型交换开关网络（224224）PE：带存储器的处理机CP：控制处理机 每一行和每一列只能接通一个交叉点开关679.4 动态互连网络PE220发送发送PE222CP001

37、断开断开CP002PE001PE219PE221PE222PE221PE220PE219PE001CP002CP001接通接通接收接收689.4 动态互连网络1.多级互连网络的构成 MIMD和SIMD计算机都采用多级互连网络MIN（Multistage Interconnection Network）一种通用的多级互连网络 q由由abab开关模块和级间连接构成的通用多级互连网络结构开关模块和级间连接构成的通用多级互连网络结构q每一级都用了多个每一级都用了多个abab开关开关na a个输入和个输入和b b个输出个输出n在理论上，在理论上，a a和和b b不一定相等，然而实际上不一定相等，然而实际

38、上a a和和b b经常经常选为选为2 2的整数幂，即的整数幂，即a ab b2 2k k，k1k1。q相邻各级开关之间都有固定的级间连接相邻各级开关之间都有固定的级间连接9.4.3 多级互连网络699.4 动态互连网络709.4 动态互连网络几种常用的开关模块 719.4 动态互连网络最简单的开关模块：22开关 22开关的4种连接方式 729.4 动态互连网络各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。q控制方式：对各个开关模块进行控制的方式。控制方式：对各个开关模块进行控制的方式。n级控制：每一级的所有开关只用一个控制信号级控制：每一级的所有开关只用一个控制信号控制

39、，只能同时处于同一种状态。控制，只能同时处于同一种状态。n单元控制：每一个开关都有一个独立的控制信单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。号，可各自处于不同的状态。n部分级控制：第部分级控制：第i i级的所有开关分别用级的所有开关分别用i i1 1个信个信号控制，号控制，0in0in1 1，n n为级数。为级数。q常用的级间互连模式：常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等 739.4 动态互连网络1.多级立方体网络多级立方体网络包括STARAN网络和间接二进制n方体网络等。q两者仅在控制方式

40、上不同，在其他方面都是一样的。两者仅在控制方式上不同，在其他方面都是一样的。q都采用二功能（直送和交换）的都采用二功能（直送和交换）的22开关。开关。q当第当第i级（级（0in-1）交换开关处于交换状态时，实现）交换开关处于交换状态时，实现的是的是Cubei互连函数。互连函数。一个N输入的多级立方体网络有log2N级，每级用N/2个22开关模块，共需要log2NN/2个开关。一个8个入端的多级立方体网络749.4 动态互连网络多级立方体网络多级立方体网络 759.4 动态互连网络STARAN网络采用级控制和部分级控制。q采用级控制时，所实现的是交换功能；采用级控制时，所实现的是交换功能；q采用

41、部分级控制时，则能实现移数功能。采用部分级控制时，则能实现移数功能。间接二进制n方体网络则采用单元控制。q具有更大的灵活性。具有更大的灵活性。交换q将有序的一组元素头尾对称地进行交换。将有序的一组元素头尾对称地进行交换。例如：对于由例如：对于由8 8个元素构成的组，各种基本交换的图形：个元素构成的组，各种基本交换的图形：769.4 动态互连网络8 8个元素的基本交换图形个元素的基本交换图形 779.4 动态互连网络3级STARAN网络在各种级控制信号的情况下所实现的入出端连接以及所实现的交换函数和功能。其中：其中：qK2k1k0：控制信号，：控制信号，ki（i=0，1，2）为第）为第i级的级控

42、级的级控制信号。制信号。q从表中可以看出从表中可以看出 下面的下面的4行中每一行所实现的功能可以从级控制行中每一行所实现的功能可以从级控制信号为其反码的一行中所实现的功能加上信号为其反码的一行中所实现的功能加上1组组8元变元变换来获得。换来获得。例如：例如：级控制信号为级控制信号为110所实现的功能是其反码所实现的功能是其反码001所实所实现的现的4组组2元交换再加上元交换再加上1组组8元交换来获得。元交换来获得。7879当STARAN网络用作移数网络时，采用部分级控制，控制信号的分组和控制结果。80Omega网络 一个88的Omega网络q每级由每级由4个个4功能的功能的22开关构成开关构成

43、q级间互连采用均匀洗牌连接方式级间互连采用均匀洗牌连接方式 819.4 动态互连网络一个N输入的Omega网络q有有log2N级，每级用级，每级用N/2个个22开关模块，共需要开关模块，共需要Nlog2N/2个开关。个开关。q每个开关模块均采用单元控制方式。每个开关模块均采用单元控制方式。q不同的开关状态组合可实现各种置换、广播或从输不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。入到输出的其它连接。N=8的多级立方体互连网络的另一种画法 829.4 动态互连网络0011223344556677ABCDEGFHIJKL级级0级级1级级2839.4 动态互连网络9.4.4 动态互

44、连网络的比较84 当源结点和目的结点之间没有直接的连接时，消息需要经过中间的结点进行传递。寻径就是用来实现这种传递的通信方法和算法。有的称之为路由。9.5 消息传递机制1.消息的格式 消息：结点之间进行通信的逻辑单位 q由若干个由若干个“包包”组成组成q包的长度是固定的，一条消息中所包含的包的个数是包的长度是固定的，一条消息中所包含的包的个数是可变的，消息的长度是不定长的。可变的，消息的长度是不定长的。9.5.1 消息寻径方案859.5 消息传递机制消息、包和片的格式消息、包和片的格式 869.5 消息传递机制包：包含寻径所需目的地址的基本单位。q一条消息中的各个包都依次被分配一个序号一条消息

45、中的各个包都依次被分配一个序号以便这些包到达目的结点后能重新组装出消息。以便这些包到达目的结点后能重新组装出消息。q包可以进一步分成一些更小的固定长度的单位，称包可以进一步分成一些更小的固定长度的单位，称为为“片片”。q寻径信息和包序列号形成头片，其余的是数据片。寻径信息和包序列号形成头片，其余的是数据片。q包的长度主要是由寻径方案和网络的具体实现所决包的长度主要是由寻径方案和网络的具体实现所决定的定的n典型的长度是典型的长度是64512位不等位不等q片的长度经常是受网络大小的影响片的长度经常是受网络大小的影响879.5 消息传递机制1.四种寻径方式 线路交换：在线路交换方式下，在传递一个信息

46、之前，需要先建立一条从源结点到目的结点的物理通路，然后再传递信息。q传输时延传输时延T 其中：其中：nL：信息包的长度（位数）：信息包的长度（位数）nLt：建立路径所需的小信息包的长度：建立路径所需的小信息包的长度nD：经过的中间结点个数：经过的中间结点个数nB：带宽：带宽 889.5 消息传递机制q优点：传输带宽较大，平均传输时延较小，而且使优点：传输带宽较大，平均传输时延较小，而且使用的缓冲区小。用的缓冲区小。n适合于具有动态和突发性的大规模并行处理数适合于具有动态和突发性的大规模并行处理数据的传送。据的传送。q缺点：需要频繁地建立源结点到目的结点的物理通缺点：需要频繁地建立源结点到目的结

47、点的物理通路，时间开销会很大。路，时间开销会很大。存储转发：最简单的分组交换方式。q包是信息传递的基本单位。包从源结点经过一系列包是信息传递的基本单位。包从源结点经过一系列中间结点到达目的结点。中间结点到达目的结点。q要求：所经过的每个中间结点都要设置一个包缓冲要求：所经过的每个中间结点都要设置一个包缓冲器，用于保存所传递的包。当一个包到达某个中间器，用于保存所传递的包。当一个包到达某个中间结点时，该结点先把这个包全部存储起来，然后在结点时，该结点先把这个包全部存储起来，然后在出口链路可用、而且下一个结点的包缓冲器也可用出口链路可用、而且下一个结点的包缓冲器也可用的情况下，传递给下一个结点。的

48、情况下，传递给下一个结点。899.5 消息传递机制源结点源结点目的结点目的结点包缓冲包缓冲中间结点中间结点（a）存储转发）存储转发源结点源结点片缓冲片缓冲中间结点中间结点目的结点目的结点（b）虫蚀方式）虫蚀方式909.5 消息传递机制q网络的时延与源和目的地之间的距离（跳数）成正比网络的时延与源和目的地之间的距离（跳数）成正比 q缺点缺点n 包缓冲区大，不利于包缓冲区大，不利于VLSI实现；实现；n 网络时延大，与结点距离成正比。网络时延大，与结点距离成正比。虚拟直通：对存储转发方式的一种改进，减少了网络时延。p基本思想基本思想：没有必要等到信息包全部放入缓冲器后再：没有必要等到信息包全部放入

49、缓冲器后再作路由选择，只要接收到用作寻径的包头，就可作出作路由选择，只要接收到用作寻径的包头，就可作出判断。判断。919.5 消息传递机制n如果结点的输出链路空闲，信息包可以不必存如果结点的输出链路空闲，信息包可以不必存储在该结点的缓冲器中，而是立即传送到下一储在该结点的缓冲器中，而是立即传送到下一个结点。个结点。n如果整条链路都空闲，包就可以立即直达目的如果整条链路都空闲，包就可以立即直达目的结点。结点。n在输出链路不空闲时，要用缓冲器进行存储。在输出链路不空闲时，要用缓冲器进行存储。q通信时延通信时延 nLh：信息包寻径头部的长度：信息包寻径头部的长度 n一般来说，一般来说，LLh（D+1

50、），所以），所以TL/B。929.5 消息传递机制q当出现寻径阻塞时，虚拟直通方式需要将整个信息包当出现寻径阻塞时，虚拟直通方式需要将整个信息包全部存储在寻径结点中，要求每个结点都有足够大的全部存储在寻径结点中，要求每个结点都有足够大的缓冲区。缓冲区。（不利于（不利于VLSI的实现的实现）虫蚀方式：把信息包“切割”成更小的单位“片”，而且使信息包中各片的传送按流水方式进行。q可以减少结点中缓冲器的容量，缩短传送延迟时间。可以减少结点中缓冲器的容量，缩短传送延迟时间。q在新型的多计算机系统中得到了广泛的应用。在新型的多计算机系统中得到了广泛的应用。q处理的最小信息单位是处理的最小信息单位是“片片