16_18_互连网络.ppt

1、计 算 机 系 统 结 构,第十六十八讲 互连网络与通信,2,主要内容,互连网络 静态网络 动态网络,3,互连网络的作用,基本功能,由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。,互连网络主要完成结点与结点间的连接，连接和控制方式不同，连接效果不同。,4,拓扑结构 静态网络：一维，二维，多维 动态网络：单级，多级 传递方式：单播，多点传播，广播 链路类型：共享链路，专用链路 操作方式：同步通信、异步通信 控制策略：集中控制、分布控制 交换方式：电路交换、分组交换,互连网络结构分类,5,互连网络的作用 静态网络 动态网络,6,静态网络,1.

2、静态网络的特点 静态网络由点点直接相连而成，这种连结方式在程序执行过程中不会改变。 如果用图来表示，结点代表开关，边代表通信链路，则： (1)结点间的链路无源，不能重构。 (2)开关元件与处理机相连。 (3)不直接相连结点间的通信需通过中间结点中转。,静态网络的特点与指标,7,2.静态网络的指标 网络规模：网络中结点数，表示该网络功能连结部件的多少。 结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为： 结点度 = 入度 + 出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。,8,距离：与两个

3、结点之间相连的最少边数。 网络直径：网络中任意两个结点间距离的最大值。 等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。 对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。,9,总线型网络,单总线结构： 度=1，分时使用。 优点：结构简单、成本低廉，容易实现。 缺点：使用冲突,1 2 3 n,典型的静态网络,10,多总线结构：度=总线数 多级总线结构：分级的多总线结构。,11,线性阵列,线性阵列与总线的区别： 线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。 总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据

4、。,内部结点度：2 端结点度：1 直径：N-1 等分宽度b=1,12,环,对N个结点的环，考虑相邻结点数据传送方向： 双向环： 链路数为N，直径N/2，度为2。 对称，等分宽度为2。,单向环 直径=N-1，结点度=2。 对称，等分宽度为2。 优点：寻径算法简单（i(i1) mod N）。可同时传送多个信息，吞吐率比单总线高。,13,带弦环,对上图中12个结点的带弦双向环， 结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。 结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。,度为3的带弦环,度为4的带弦环,14,链接是带弦环的一种特殊情

5、形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的链接：,度=N-1，直径=1 对称，等分宽度为16。 优点：结点间通信距离短。 缺点：成本高，实现困难。,全互连网络链接,15,树形,一棵K层完全二叉树应有N = 2K - 1个结点，对大结点度为3，直径为2(K-1)（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。 由于结点度为常数，所以树是一种可扩展的系统结构。,4层的二叉树,16,树形的扩展：,这两种结构都可以缓解根结点的瓶颈问题。,17,星形,星形实际上是一种二层树。有N个结点的星形网络，直径为2，最大结点度为N-1，非对称，等分宽度为1。,1

6、8,网,度=4，直径=2(n-1) 对分带宽 = n，链路总数=？ 优点：寻址简单，度不变 缺点：不对称，伸缩性差 绞带环、双绞螺面、带环网格(torus)和闭合螺面 网格的推广：网孔形、星形网络,19,网的变形： a. Illiac 网,有N个结点的rr网（其中 r= N1/2)，有2N条链路，直径为r-1，结点度为4。,20,b. 环形网,有N个结点的rr网（其中 r=N1/2)，有2N 条链路，直径为2r/2，结点度为4，对称。,21,c. 搏动式阵列（Systolic Array）,22,超立方体,0-立方体,1-立方体,2-立方体,3-立方体,4-立方体,23,一个n-立方体由N=2

7、n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。,二进制超立方体(binary hypercube)： 度为n，直径k=n=log2N。 优点：结点间的通信距离较短；寻径算法简单。 (anan-1aia2a1) (anan-1ia2a1) 缺点：可扩充性差，度随N的增加而增大。,24,带环立方体,一个带环n-立方体由N = 2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n 2n个。直径通常为2n，结点度为3，对称。,带环3-立方体,带环立方体网络 优点：度固定为3。直径较小。 缺点：环成为瓶

8、颈，寻径算法较复杂。,25,k元n-立方体网络,4元3-立方体,26,在一个k元n-立方体网络中，结点的数目N = kn，即：,其中，k称为基数（radix），n称为维数(dimension) k元n-立方体的结点可以用基数为k的n位地址A = a0 a1 a2 . an来表示，其中ai代表第i维结点的位置。,k=N1/n n=log k N,27,传统的环网等价于4元2-立方体。,28,互连网络的作用 静态网络 动态网络,29,动态网络,网络的开关元件有源，链路可通过设置这些开关的状态来重构。 只有在网络边界上的开关元件才能与处理机相连。,特点：,30,单级动态互连网络,一、网络的互连函数

9、互连函数：端口地址的一个一到一的(bijection)映射。 表示方法： (1) 函数表示法：用x表示输入端变量，用f(x)表示互连函数。 (2) 表格表示法：（适用于不规则连接） (3) 循环表示法：如(1 2)(3 4)(5 6)(7 8) (4) 图形表示法：用连线表示映射关系。,31,互连函数 排列：N个数的每一种有确定次序的放置方法叫做一个N排列。 置换：把一个N排列变成另一个N排列的变换叫做N阶置换。 在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。 一些常见的基本互连函数可以用下面的函数表示：,32,1. 恒等置换函数,其中

10、，Xn-1 Xn-2Xk X0是PU的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,(0)(1)(2)(3)(4)(5)(6)(7),7,6,5,4,3,2,1,0,7,6,5,4,3,2,1,0,33,2. 方体函数（cube0，cube1，cuben-1),),(,0,2,1,0,2,1,X,X,X,X,X,X,X,X,cube,k,n,n,k,n,n,k,-,-,-,-,=,方体函数是由n个互连函数组成，其中0kn-1。 如 n为3时，3-立方体各结

11、点地址如下：,交换功能-互连函数可逆； 互连函数个数=log28=3； 结点最大间距=log28=3。,34,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube0:,),(,0,1,2,0,1,2,0,X,X,X,X,X,X,cube,=,(0 1)(2 3)(4 5)(6 7),35,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube1:,),(,0,1,2,0,1,2,1,X,X,X,X,X,X,cube,=,(0 2)

12、(1 3)(4 6)(5 7),36,Cube2:,),(,0,1,2,0,1,2,2,X,X,X,X,X,X,cube,=,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,(0 4)(1 5)(2 6)(3 7),37,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,3.全混洗函数,（二混洗）,(0)(1 2 4)(3 6 5)(7),38,三混洗：,0000,0001,0010,0011,0100,0101,0110,0111,10

13、00,1001,1010,1011,0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,39,洗牌函数的变形： a.均匀洗牌（Shuffle-Exchange) 是洗牌函数与Cube0函数的组合。,全“0”或全“1”结点无法与其他结点连接，必须辅以交换互连函数，方可实现任意结点间连接。,Cube0 Sh(X2X1X0)= Cube0 X1X0X2= X1X0X2,混洗交换互连函数：,40,连接图：,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,1

14、00,101,110,111,41,b. 第k个子洗牌,最低k位循环左移一位。,子洗牌：将整组端口分成若干个组，对每个组完成均匀洗牌交换。,例：Sh2(X2X1X0)= X2X0X1 (0)(1 2)(3)(4)(5 6)(7),0,1,2,3,4,5,6,7,2,3,4,5,6,0,1,7,0kn-1,42,c. 第k个超洗牌,最高k位循环左移一位。,例：Sh2(X2X1X0)= X1X2X0 (0)(1)(2 4)(3 5)(6)(7),0kn-1,43,4. 逆洗牌函数,(0)(1 4 2)(3 5 6)(7),44,子逆洗牌：将整组端口分成若干个组，对每个组完成逆洗牌。,例： Sh-1

15、3 (X3X2X1X0) = X3X0X2X1 (0)(1 4 2)(3 5 6)(7)(8) (9 12 10)(11 13 14)(15),0kn-1,-1,45,5. 蝶式,(0)(2)(1 4) (3 6)(5)(7),46,子蝶式置换：将端口分组，组内蝶式置换。,(k)(xn-1xn-2xk+1xkxk-1x1x0) = xn-1xn-2xk+1xkx0 x1xk-1 例:(3) (x3x2x1x0) = x3x0 x1x2 (0)(1 4)(2)(3 6)(5)(7) (8)(9 12)(10)(11 14)(13)(15),47,超蝶式置换,(k)(xn-1xn-2xn-kxn-

16、k-1xn-k-2x1x0 ) = xn-k-1xn-2xn-kxn-1xn-k-2x1x0 例:(3)(x3x2x1x0) = x1x2x3x0 (0)(1)(2 8)(3 9)(4)(5)(6 12) (7 13)(10)(11)(14)(15),48,6、位序颠倒置换,(xn-1xn-2x1x0) = x0 x1xn-2xn-1 例(x3x2x1x0) = x0 x1x2x3 (0)(1 8)(2 4)(3 12)(5 10)(6) (7 14)(9)(11 13)(15) N=8时的位序颠倒置换与蝶式置换相同。 子位序颠倒置换：低位段倒置 超位序颠倒置换：高位段倒置,0,1,2,3,4

17、,5,6,7,2,3,4,5,6,0,8,1,7,9,10,11,8,9,10,11,12,13,14,15,12,13,14,15,49,7、移数置换,(x) = (x+k) mod N, 0 xN 例： (0 2 4 6)(1 3 5 7),0,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,50,8、 PM2I函数（加减2i）（循环移数网络）,N = 8（8个结点），则n = log28 = 3，所以：i = 0，1，2；j = 0，1，7。 6个PM2I函数如下：,出端编码与连接的入端结点编码相差2i。,PM2+i (j)= j+2 mod N PM2-i (J)= j-2

18、 mod N,i,i,51,PM2+0:( 0 1 2 3 4 5 6 7）,0,1,2,3,4,5,6,7,PM2-0:( 7 6 5 4 3 2 1 0）,0,1,2,3,4,5,6,7,52,PM2+1:( 0 2 4 6）（1 3 5 7）,0,1,2,3,4,5,6,7,PM2-1:( 6 4 2 0）（7 5 3 1）,0,1,2,3,4,5,6,7,53,PM22:( 0 4）（1 5）（2 6）（3 7）,0,1,2,3,4,5,6,7,54,0,1,2,3,4,5,6,7,例：,8,9,10,11,12,13,14,15,上面的网络可以用四个PM2I函数表示。,55,小结,(

19、1)单级互连网络特性,任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。,单级互连网络含义：某些连接方法或拓扑结构。,(2)单级互连网络应用,利用单级互连网络的特性作为实际IN的拓扑结构；,通过交换开关作为IN的可变因素；,通过交换开关多次控制实现IN的结点间任意互连。,56,练习：假设16个 处理机的编号分别是0，1，2，15，采用单级互连网络。互连函数分别为： （1）Cube3（2）PM2+3 （3）PM2-0（4）Shuffle （5）Bufferfly（6）Reversal 计算12号处理机与哪个处理机相连。,57,1. 多级网络的三要素 （1）开

20、关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有22、44、88等。 根据开关单元功能的多少， 2 2又可以分为两功能和四功能开关。如下图所示：,多级互连网络,58,0,1,0,1,直送,0,1,0,1,交叉,0,1,0,1,上播,0,1,0,1,下播,59,（2）级间互连模式（InterStage Connection）： 均匀洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（Cross Switch)及立方体连结等。 （3）控制方式 级控制： 每级只有一个控制信号 单元控制： 每个开关一个控制信号 部分级控制：

21、几个开关合用一个控制信号,60,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,ISC,61,分类：根据拓扑结构进行分类,多级立方体网络 多级混洗交换网络 多级PM2I网络,62,一、多级立方体网络,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级,0,1,2,输入,输出,STARAN网络，间接二进制n方体网络,63,开关单元：二功能开关（直通和交换） ISC：级间子蝶式+蝶式+输出逆洗牌 控制方式： STARAN网络 间接二进制n方体网络,级控制,部分级控制,单元控制,以STARAN网络

22、为例介绍,多级立方体网络的特点：,64,(1)交换功能,控制：级控制(开关为1时交换功能，0为直通),65,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级,0,1,2,输入,输出,级控制信号（k2k1k0）=010,级控制信号 0 1 0,0 1 2 3 4 5 6 7,2 3 0 1 6 7 4 5,1 0 3 2 5 4 7 6,66,0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111,010 2 011 3 000 0 001 1 110 6 111 7 100 4 101 5,二进制,二进制,十进制,十进制,f(X2X1X

23、0)=X2X1X0 =cube1,67,(2)移位功能,控制：部分级控制（第i级有i+1种控制信号）,功能：控制信号不同，功能不同。,应用：,不同的Mod，可用作不同的分组操作。,移数功能很适合于累加求和算法实现；,68,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,输入,输出,0 1 2 3 4 5 6 7,2 3 4 5 6 7 0 1,移2 Mod 8,输入,输出,69,(3)带宽问题,STARAN可同时多对结点连接，尚不能同时任意组合。,(4)例题,例：编号0-F的PE间，要实现下列通信配对： (7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(

24、1,B),(0,A)。 画出互连网络结构图，写出控制方式级各开关状态。,答：因需实现双向交换功能，选择STARAN的交换网络(级控制方式）可满足要求。,因共有16个结点，编码需要4位，所以开关共4级。,网络结构图如下页：,70,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,级,k0,k2,k3,k1,拓扑结构：不同级完成地址不同位取反功能。 注意：有交换开关的拓扑结构的实现。,71,1 0 1 0 A 1 0 1 1 B 1 0 0 0 8 1 0 0 1 9 1 1 1 0 E 1 1 1 1 F 1 1 0

25、0 C 1 1 0 1 D 0 0 1 0 2 0 0 1 1 3 0 0 0 0 0 0 0 0 1 1 0 1 1 0 6 0 1 1 1 7 0 1 0 0 4 0 1 0 1 5,二进制,二进制,十进制,十进制,f(X3X2X1X0)=X3X2X1X0,= cube1 +cube3,0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 0 1 1 1 1 0 0 0 9 1 0 0 1 A 1 0 1 0 B 1 0 1 1 C 1 1 0 0 D 1 1 0 1 E 1 1 1 0 F 1 1 1

26、1,72,0 1 2 3 4 5 6 7 8 9 A B C D E F,1组16元交换后：,F E D C B A 9 8 7 6 5 4 3 2 1 0,2组8元交换后：,8 9 A B C D E F 0 1 2 3 4 5 6 7,4组4元交换后：,A B 8 9 E F C D 2 3 0 1 6 7 4 5,8组2元交换后：,B A 9 8 F E D C 3 2 1 0 7 6 5 4,(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A),73,相加 Cube1+ Cube3,各级开关状态：k3k2k1k0=(1010),1组16元交换

27、Cube0+Cube1+Cube2+Cube3 2组8元交换 Cube0+Cube1+Cube2 4组4元交换 Cube0+Cube1 8组2元交换 Cube0,74,例：并行处理机有16个PE，实现相当于4组4元交换，然后2组8元交换，再1组16元交换功能。写出互连函数一般式、各级交换开关状态。,答：因需实现交换功能，故选择STARAN的交换网络(级控制方式）。,相加 Cube0+Cube1 +Cube3,各级开关状态：k3k2k1k0=(1011),互连函数：f(b3b2b1b0)= b3b2b1b0,75,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第0级,第1级,第2级,二、多级混洗交换网络（ 网络）,76,网的特点： 开关单元：22四功能开关 ISC：全混洗变换 控制方式：采用单元控制方式,功能：,1、当控制方式为：级控制且开关为二功能： 是STARAN交换网