第7章互连网络.ppt

《第7章互连网络.ppt》由会员分享，可在线阅读，更多相关《第7章互连网络.ppt（27页珍藏版）》请在第壹文秘上搜索。

1、1第第7章章 互连网络互连网络7.1 互连网络的基本概念互连网络的基本概念u互连函数互连函数u互连网络的特性和传输的性能参数互连网络的特性和传输的性能参数u互连网络的种类互连网络的种类7.2 消息传递机制消息传递机制u 消息寻径方式消息寻径方式u 死锁和虚拟通道死锁和虚拟通道7.3 互连网络实例互连网络实例27.3 7.3 互连网络实例互连网络实例7.3.1 7.3.1 总线互连总线互连7.3.2 7.3.2 环形互连环形互连7.3.3 7.3.3 交叉开关互连交叉开关互连（补充）（补充）多端口存储器多端口存储器（补充）（补充）STARANSTARAN交换网和交换网和STARANSTARAN移

2、数网移数网7.3.5 Omega7.3.5 Omega互连网互连网37.3.1 7.3.1 总线互连总线互连总线的优点：结构简单，很方便实现广播。总线的缺点：带宽低，发生冲突的可能性大。总线冲突的解决办法有：(1)设置静态优先级(2)在同步方式中采用时间片(3)采用动态优先级（如LRU法等）(4)先来先服务提高总线通信带宽的方法有：(1)(1)采用多总线结构采用多总线结构(2)(2)层次总线结构层次总线结构(3)(3)多维总线结构多维总线结构4总线结构的多处理机总线结构的多处理机本地存储器本地存储器本地存储器全局存储器5多总线结构：多总线结构：西门子公司的SMS系统 （Stractured M

3、ultiprocessor System）通过8条总线连接128个处理机总 线 驱 动 器 SM S 多多 总总 线线 结结 构构主主 机机P1P2P16P17P18P32P113P114P1286层次总线结构：层次总线结构：卡内基梅隆大学的Cm*多处理机系统 三级总线：群总线、Map总线、处理机总线 每群14台处理机群 间 总 线 卡 内 基 梅 隆 大 学 的Cm*层 次 总 线 结 构KmCmCmCmKmCmCmKmCmCmCmPBMIO7（补充）多端口存储器（补充）多端口存储器多个多端口存储器与多个CPU和IOP连接。多端口存储器用于处理机个数不多的系统中。把复杂的互连网络移到了存储器

4、中。P1M1M2M3M4P2IOP1IOP287.3.27.3.2环形互联环形互联 既具有总线型互连的简单性，又可克服总线所固有的缺点 信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止 97.3.3 7.3.3 交叉开关互连交叉开关互连 交叉开关包含一组纵横开关阵列，把横向的交叉开关包含一组纵横开关阵列，把横向的m m个处理机及个处理机及i i个个I/OI/O设备与纵向的设备与纵向的n n个存储器模块连接起来，如下图所示。个存储器模块连接起来，如下图所示。107.4.3 STARAN7.4.3 STARAN交换网和移数网交换网和移数网多级立方

5、体网，应用在巨型机多级立方体网，应用在巨型机STARANSTARAN中中1)有n=log2N级，每级N/2个开关，整个网络开关数2)采用22的2功能开关3)开关级号：K0,K1,Kn-14)级间连接：C0恒等置换,C1-Cn-1子蝶式置换,Cn逆洗牌置换。5)开关控制方式有2种：级控方式和组控方式。采用级控制可以构成STARANSTARAN交换网交换网。采用部分级控制，可以构成STARANSTARAN移数网移数网。11ABCDEFGHIJKL0123456701234567输输入入端端输输出出端端多级立方体网络多级立方体网络123 3级级STARANSTARAN交换网络实现的入出端连接及执行的

6、交换函数功能交换网络实现的入出端连接及执行的交换函数功能13 除除F=(000)F=(000)实现恒等置换外，其他实现恒等置换外，其他7 7种实现分组交换置换，如种实现分组交换置换，如F=(101)F=(101)实现的置换可表示为：实现的置换可表示为：1401234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567153 3级级STARANSTARAN移数网络实现的入出端连接及执行的移数函数功能移数网

7、络实现的入出端连接及执行的移数函数功能组控制信号2级F23F22F21K,LJI0010111110000000000001级F12F11F,H E,G011100011100000级F0A,B,C,D1001010入端号0123456712345670234567014567012312305674230167451032547601234567执行的移数功能移1mod 8移2mod 8移4mod 8移1mod 4移2mod 4移1mod 2不移恒等160123456701234567012345670123456701234567012345670123456701234567012345

8、67012345670123456701234567012345670123456717题目：题目：编号分别为编号分别为0,1,2,0,1,2,F,F的的1616个处理器之间要求按下列配对个处理器之间要求按下列配对通信：通信：(B,1),(8,2),(7,D),(6,C),(E,4),(A,0),(9,3),(B,1),(8,2),(7,D),(6,C),(E,4),(A,0),(9,3),(5,F)(5,F)。试选择互连网络类型、控制方式，并画出该互连网络的。试选择互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级交换开关状态图。拓扑结构和各级交换开关状态图。分析分析：要求配对通讯的处

9、理器号用二进制表示如下：要求配对通讯的处理器号用二进制表示如下：(B,1)(B,1)是是(1011,0001)(1011,0001)(8,2)(8,2)是是(1000,0010)(1000,0010)(7,D)(7,D)是是(0111,1101)(0111,1101)(6,C)(6,C)是是(0110,1100)(0110,1100)(E,4)(E,4)是是(1110,0100)(1110,0100)(A,0)(A,0)是是(1010,0000)(1010,0000)(9,3)(9,3)是是(1001,0011)(1001,0011)(5,F)(5,F)是是(0101,1111(0101,11

10、11)180123456789ABCDEF0123456789ABCDEFCube0Cube1Cube2Cube3直连直连直连直连交换交换交换交换入端入端出端出端19题目：题目：并行处理机有并行处理机有1616个处理器，要实现相当于先个处理器，要实现相当于先4 4组组4 4元交换，元交换，然后是两组然后是两组8 8元交换，再次是一组元交换，再次是一组1616元交换的交换函数功能，请元交换的交换函数功能，请写出此时各处理器之间所实现之互连函数的一般式；画出相应多写出此时各处理器之间所实现之互连函数的一般式；画出相应多级网络拓扑结构图，标出各级交换开关的状态。级网络拓扑结构图，标出各级交换开关的状

11、态。分析分析：输入端号为输入端号为|0 1 2 3|4 5 6 7|8 9 A B|C D E F|经经4组组4元交换后为元交换后为|3 2 1 0|7 6 5 4|B A 9 8|F E D C|分成分成2组后为组后为|3 2 1 0 7 6 5 4|B A 9 8 F E D C|然后经然后经2组组8元交换后为元交换后为|4 5 6 7 0 1 2 3|C D E F 8 9 A B|再经再经1组组16元变换后为元变换后为|B A 9 8 F E D C 3 2 1 0 7 6 5 4|最后，可得出配对互连的是最后，可得出配对互连的是(0,B),(1,A),(2,9),(3,8),(4,F

12、),(5,E),(6,D),(7,C)用二进制表示就是用二进制表示就是Cube(P3P2P1P0)=P3P2P1P0207.3.5 Omega7.3.5 Omega网络网络采用全混洗函数全混洗函数和交换函数交换函数，又称混洗交换网络。1、N个输入的Omega网络有log2N级，每级有N/2个22的四功能交换开关2、每级的拓扑结构相同3、采用单元控制4、能够实现任意一个输入端到任意一个输出端的连接。但不能同时实现多个输入端到多个输出端的连接。5、能够实现从任意一个输入端到所有输出端的广播。210 01 12 23 34 45 56 67 7 k=2 k=1 k=0ABCDEFGHIJKLN=8N

13、=8的多级混洗交换网络的多级混洗交换网络22网络结构特点：网络结构特点：1)1)采用采用2 22 2的的4 4功能开关，功能开关，4 4功能为直送、交叉、上播、下播。功能为直送、交叉、上播、下播。2)2)网络各级开关的级号从网络输入端到输出端，依次为网络各级开关的级号从网络输入端到输出端，依次为K Kn-1n-1，K K1 1，K K0 0，即按降序排列。，即按降序排列。3)3)级间连接从网络输入端到输出端依次为级间连接从网络输入端到输出端依次为C Cn-1n-1，C C1 1，C C0 0，其中其中C Cn-1n-1-C-C1 1都是均匀洗牌置换函数，都是均匀洗牌置换函数，C C0 0为恒等

14、置换。因此为恒等置换。因此网络输入端对输出端互连函数表达式为：网络输入端对输出端互连函数表达式为：=EE=EEE=(E)E=(E)n n 其中其中E E是开关级在开关控制方式下实现的交换置换函数，是开关级在开关控制方式下实现的交换置换函数，是是级间连接模式实现的混洗函数。级间连接模式实现的混洗函数。23多级混洗多级混洗交换网络寻径算法（路由算法）交换网络寻径算法（路由算法）目的：根据给定的输入目的：根据给定的输入/输出对应关系，确定各开关的状态。输出对应关系，确定各开关的状态。名称：源名称：源-目的地址异或法目的地址异或法操作：将任一个输入地址与它要到达的输出地址作异或运算，操作：将任一个输入

15、地址与它要到达的输出地址作异或运算，其结果的其结果的bitbiti i位控制数据到达的第位控制数据到达的第i i级开关，级开关，“0”0”表示表示“直连直连”，“1”1”表示表示“交换交换”。（。（例如给定传输例如给定传输101B011B101B011B）0 01 12 23 34 45 56 67 7 k=2 k=1 k=0ABCDEFGHIJKL24题目：题目：画出画出0-70-7号共号共8 8个处理器的三级混洗交换网络，在该图上标个处理器的三级混洗交换网络，在该图上标出实现将出实现将6 6号处理器数据播送给号处理器数据播送给0-40-4号，同时将号，同时将3 3号处理器数据播号处理器数据

16、播送给其余送给其余3 3个处理器时的各有关交换开关的控制状态。个处理器时的各有关交换开关的控制状态。分析分析：0 01 12 23 34 45 56 67 7 k=2 k=1 k=0ABCDEFGHIJKL25 如果采用级控制，是STARAN交换网的逆网 如果采用部分级控制，是STARAN移数网的逆网因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况 Omega网属于多级互连网当有N个输入端时，共有N(N/2)个变换要同时实现任意一个输入端到任意一个输出端的连接，共需N!个变换 8个输入端的Omega网络实际上只能实现全部变换的10%(84/8!=4096/40320=0.1016)，有90%的变换将引起阻塞 Omega网络是一种阻塞网络，采用多次通过来解决冲突有N个输入端时，实现连接的通过次数最多为log2N26 N=8的多级立方体网络和Omega网络的关系27本章重点：本章重点：1.1.主要的互连函数主要的互连函数2.2.几种典型互连网络的构成方法及特点几种典型互连网络的构成方法及特点3.3.寻径方式的原理及优缺点寻径方式的原理及优缺点练习题练习题:4，5，13 （P