第7章互连网络.ppt
1,第7章 互连网络,7.1 互连网络的基本概念互连函数互连网络的特性和传输的性能参数互连网络的种类,7.2 消息传递机制 消息寻径方式 死锁和虚拟通道,7.3 互连网络实例,2,7.3 互连网络实例,7.3.1 总线互连7.3.2 环形互连7.3.3 交叉开关互连（补充）多端口存储器（补充）STARAN交换网和STARAN移数网7.3.5 Omega互连网,3,7.3.1 总线互连,总线的优点：结构简单，很方便实现广播。总线的缺点：带宽低，发生冲突的可能性大。总线冲突的解决办法有：(1)设置静态优先级(2)在同步方式中采用时间片(3)采用动态优先级（如LRU法等）(4)先来先服务提高总线通信带宽的方法有：(1)采用多总线结构(2)层次总线结构(3)多维总线结构,4,总线结构的多处理机,5,多总线结构：西门子公司的SMS系统（Stractured Multiprocessor System）通过8条总线连接128个处理机,6,层次总线结构：卡内基梅隆大学的Cm*多处理机系统 三级总线：群总线、Map总线、处理机总线 每群14台处理机,7,（补充）多端口存储器,多个多端口存储器与多个CPU和IOP连接。多端口存储器用于处理机个数不多的系统中。把复杂的互连网络移到了存储器中。,8,7.3.2环形互联,既具有总线型互连的简单性，又可克服总线所固有的缺点信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止,9,7.3.3 交叉开关互连,交叉开关包含一组纵横开关阵列，把横向的m个处理机及i个I/O设备与纵向的n个存储器模块连接起来，如下图所示。,10,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移数网。,11,多级立方体网络,12,3级STARAN交换网络实现的入出端连接及执行的交换函数功能,13,除F=(000)实现恒等置换外，其他7种实现分组交换置换，如F=(101)实现的置换可表示为：,0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 2 3 0 1 6 7 4 5 5 4 7 6 1 0 3 2,入端排列：分成4组：每组二元交换（4G2E)：分成二组：每组四元交换（2G4E)：分成一组：每组八元交换（1G8E)：,14,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,F=(000),F=(001),F=(010),F=(011),F=(100),F=(101),F=(110),F=(111),15,3级STARAN移数网络实现的入出端连接及执行的移数函数功能,16,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,恒等,移1模2,移1模4,移2模4,移1模8,移2模8,移4模8,17,题目：编号分别为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),18,01,23,45,67,89,AB,CD,EF,01,23,45,67,89,AB,CD,EF,Cube0,Cube1,Cube2,Cube3,直连,直连,交换,交换,入端,出端,19,题目：并行处理机有16个处理器，要实现相当于先4组4元交换，然后是两组8元交换，再次是一组16元交换的交换函数功能，请写出此时各处理器之间所实现之互连函数的一般式；画出相应多级网络拓扑结构图，标出各级交换开关的状态。,20,7.3.5 Omega网络,采用全混洗函数和交换函数，又称混洗交换网络。1、N个输入的Omega网络有log2N级，每级有N/2个22的四功能交换开关2、每级的拓扑结构相同3、采用单元控制4、能够实现任意一个输入端到任意一个输出端的连接。但不能同时实现多个输入端到多个输出端的连接。5、能够实现从任意一个输入端到所有输出端的广播。,21,N=8的多级混洗交换网络,22,网络结构特点：采用22的4功能开关，4功能为直送、交叉、上播、下播。网络各级开关的级号从网络输入端到输出端，依次为Kn-1，K1，K0，即按降序排列。级间连接从网络输入端到输出端依次为Cn-1，C1，C0，其中Cn-1-C1都是均匀洗牌置换函数，C0为恒等置换。因此网络输入端对输出端互连函数表达式为：=EEE=(E)n 其中E是开关级在开关控制方式下实现的交换置换函数，是级间连接模式实现的混洗函数。,23,多级混洗交换网络寻径算法（路由算法）,目的：根据给定的输入/输出对应关系，确定各开关的状态。名称：源-目的地址异或法操作：将任一个输入地址与它要到达的输出地址作异或运算，其结果的biti位控制数据到达的第i级开关，“0”表示“直连”，“1”表示“交换”。（例如给定传输101B011B）,C3,C2,C1,C0,24,题目：画出0-7号共8个处理器的三级混洗交换网络，在该图上标出实现将6号处理器数据播送给0-4号，同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。,分析：,25,如果采用级控制，是STARAN交换网的逆网如果采用部分级控制，是STARAN移数网的逆网因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况Omega网属于多级互连网当有N个输入端时，共有N(N/2)个变换要同时实现任意一个输入端到任意一个输出端的连接，共需N!个变换8个输入端的Omega网络实际上只能实现全部变换的10%(84/8!=4096/40320=0.1016)，有90%的变换将引起阻塞Omega网络是一种阻塞网络，采用多次通过来解决冲突有N个输入端时，实现连接的通过次数最多为log2N,26,N=8的多级立方体网络和Omega网络的关系,27,本章重点：1.主要的互连函数2.几种典型互连网络的构成方法及特点3.寻径方式的原理及优缺点练习题:4，5，13（P446-447）,
