第7章互连网络

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