第7章互连网络.ppt

第7章 互连网络7.1 互连网络的根本概念互连函数互连网络的特性和传输的性能参数互连网络的种类7.2 消息传递机制u 消息寻径方式u 死锁和虚拟通道7.3 互连网络实例7.3 互连网络实例7.3.1 总线互连7.3.2 环形互连7.3.3 穿插开关互连补充 多端口存储器补充 STARAN交换网和STARAN移数网7.3.5 Omega互连网7.3.1 总线互连总线的优点：构造简单，很方便实现播送总线的缺点：带宽低，发生冲突的可能性大总线冲突的解决方法有：(1) 设置静态优先级(2) 在同步方式中采用时间片(3) 采用动态优先级如LRU法等(4) 先来先效劳进步总线通信带宽的方法有：(1) 采用多总线构造(2) 层次总线构造(3) 多维总线构造总线构造的多处理机本地存储器本地存储器本地存储器全局存储器多总线构造：西门子公司的SMS系统 Stractured Multiprocessor System 通过8条总线连接128个处理机层次总线构造：卡内基梅隆大学的Cm*多处理机系统 三级总线：群总线、Map总线、处理机总线 每群14台处理机补充多端口存储器多个多端口存储器与多个CPU和IOP连接。

多端口存储器用于处理机个数不多的系统中把复杂的互连网络移到了存储器中7.3.2环形互联 既具有总线型互连的简单性，又可抑制总线所固有的缺点 信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止 7.3.3 穿插开关互连 穿插开关包含一组纵横开关阵列，把横向的m个处理机及i个I/O设备与纵向的n个存储器模块连接起来，如以以以下图所示7.4.3 STARAN交换网和移数网多级立方体网，应用在巨型机STARAN中有n=log2N级，每级N/2个开关，整个网络开关数(N/2)log2N采用22的2功能开关开关级号：K0,K1, ,Kn-1级间连接：C0恒等置换, C1-Cn-1子蝶式置换, Cn逆洗牌置换开关控制方式有2种：级控方式和组控方式采用级控制可以构成STARAN交换网采用部分级控制，可以构成STARAN移数网ABCDEFGHIJKL0123456701234567C C0 0输入端输出端C C1 1C C2 2C C3 3K K0 0K K1 1K K2 2N=8N=8的的STARANSTARAN网络网络多级立方体网络级控制信号（级控制信号（f f2 2f f1 1f f0 0）000000001001010010011011100100101101110110111111入入端端号号0 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 71 10 03 32 25 54 47 76 62 23 30 01 16 67 74 45 53 32 21 10 07 76 65 54 44 45 56 67 70 01 12 23 35 54 47 76 61 10 03 32 26 67 74 45 52 23 30 01 17 76 65 54 43 32 21 10 0执行的执行的交换函交换函数功能数功能恒等恒等4 4组组2 2元元4 4组组2 2元元+ +2 2组组4 4元元2 2组组4 4元元1 1组组8 8元元+ +2 2组组4 4元元4 4组组2 2元元+ +2 2组组4 4元元+ +1 1组组8 8元元4 4组组2 2元元+ +1 1组组8 8元元1 1组组8 8元元i iCubeCube0 0CubeCube1 1CubeCube0 0+ +CubeCube1 1CubeCube2 2CubeCube0 0+ +CubeCube2 2CubeCube1 1+ +CubeCube2 2CubeCube0 0+Cube+Cube1 1+Cube+Cube0 03级STARAN交换网络实现的入出端连接及执行的交换函数功能 除F=(000)实现恒等置换外，其他7种实现分组交换置换，如F=(101)实现的置换可表示为： 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 0 1 2 3 2 3 4 5 4 5 6 7 6 7 11 0 0 33 2 2 5 4 5 4 7 6 7 6 1 1 0 3 2 0 3 2 5 4 7 6 5 4 7 6 22 3 0 1 3 0 1 6 7 4 5 6 7 4 5 22 3 0 1 6 7 4 5 3 0 1 6 7 4 5 5 4 7 6 1 0 3 2 5 4 7 6 1 0 3 2入端排列：入端排列：分成分成4 4组：组：每组二元交换每组二元交换4G2E)4G2E)：分成二组：分成二组：每组四元交换每组四元交换2G4E) 2G4E) ：分成一组：分成一组：每组八元交换每组八元交换1G8E) 1G8E) ：01234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567F=(000)F=(000)F=(001)F=(001)F=(010)F=(010)F=(011)F=(011)F=(100)F=(100)F=(101)F=(101)F=(110)F=(110)F=(111)F=(111)3级STARAN移数网络实现的入出端连接及执行的移数函数功能组控制信号2级F23F22F21K,LJI0010111110000000000001级F12F11F,H E,G011100011100000级F0A,B,C,D1001010入端号0123456712345670234567014567012312305674230167451032547601234567执行的移数功能移1mod 8移2mod 8移4mod 8移1mod 4移2mod 4移1mod 2不移恒等0123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567恒等恒等移移1 1模模2 2移移1 1模模4 4移移2 2模模4 4移移1 1模模8 8移移2 2模模8 8移移4 4模模8 8题目：编号分别为0,1,2,F的16个处理器之间要求按以下配对通信：(B,1), (8,2), (7,D), (6,C), (E,4), (A,0), (9,3), (5,F)。

试选择互连网络类型、控制方式，并画出该互连网络的拓扑构造和各级交换开关状态图分析：要求配对通讯的处理器号用二进制表示如下：(B,1)是(1011,0001)(8,2)是(1000,0010)(7,D)是(0111,1101)(6,C)是(0110,1100)(E,4)是(1110,0100)(A,0)是(1010,0000)(9,3)是(1001,0011)(5,F)是(0101,1111)0123456789ABCDEF0123456789ABCDEFCube0Cube1Cube2Cube3直连直连交换交换入端出端题目：并行处理机有16个处理器，要实现相当于先4组4元交换，然后是两组8元交换，再次是一组16元交换的交换函数功能，请写出此时各处理器之间所实现之互连函数的一般式；画出相应多级网络拓扑构造图，标出各级交换开关的状态分析：输入端号为|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), (5,E), (6,D), (7,C)用二进制表示就是Cube(P3P2P1P0)= P3P2P1P07.3.5 Omega网络采用全混洗函数和交换函数，又称混洗交换网络。

1、N个输入的Omega网络有log2N级，每级有N/2个22的四功能交换开关2、每级的拓扑构造一样3、采用单元控制4、可以实现任意一个输入端到任意一个输出端的连接但不能同时实现多个输入端到多个输出端的连接 5、可以实现从任意一个输入端到所有输出端的播送N=8的多级混洗交换网络网络构造特点：采用22的4功能开关，4功能为直送、穿插、上播、下播网络各级开关的级号从网络输入端到输出端，依次为Kn-1，K1，K0，即按降序排列级间连接从网络输入端到输出端依次为Cn-1，C1，C0，其中Cn-1-C1都是均匀洗牌置换函数，C0为恒等置换因此网络输入端对输出端互连函数表达式为：=EEE=(E)n 其中E是开关级在开关控制方式下实现的交换置换函数，是级间连接形式实现的混洗函数多级混洗交换网络寻径算法路由算法目的：根据给定的输入/输出对应关系，确定各开关的状态名称：源-目的地址异或法操作：将任一个输入地址与它要到达的输出地址作异或运算，其结果的biti位控制数据到达的第i级开关，“0表示“直连，“1表示“交换例如给定传输101B011B C C3 3C C2 2C C1 1C C0 0题目：画出0-7号共8个处理器的三级混洗交换网络，在该图上标出实现将6号处理器数据播送给0-4号，同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。

分析： 假设采用级控制，是STARAN交换网的逆网 假设采用部分级控制，是STARAN移数网的逆网 因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况 Omega网属于多级互连网 当有N个输入端时，共有N(N/2)个变换 要同时实现任意一个输入端到任意一个输出端的连接，共需N!个变换 8个输入端的Omega网络实际上只能实现全部变换的10%(84/8! = 4096/40320=0.1016)，有90%的变换将引起阻塞 Omega网络是一种阻塞网络，采用屡次通过来解决冲突 有N个输入端时，实现连接的通过次数最多为log2N N=8的多级立方体网络和Omega网络的关系本章重点：1. 主要的互连函数2. 几种典型互连网络的构成方法及特点3. 寻径方式的原理及优缺点练习题:4，5，13 P446-447。