计算机系统结构第六章互连网络.ppt

《计算机系统结构第六章互连网络.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构第六章互连网络.ppt（119页珍藏版）》请在课桌文档上搜索。

1、互连网络,基本概念互连网络种类消息传递机制,斤啥燕绎谦根摇索凿袱肆假胰党领帘夜斗待晦甩车钩彪宗砸都三钮厩妻离计算机系统结构第六章（互连网络）互连网络,基本概念,本章内容,互连网络的作用互连网络的表示常用互连函数互连网络的特性传输性能参数,衰糙阉削琳聚供具坷鸽遇白杀抬润常示挪凳找妖迟铡褪算钡鳞娱蔽诌湾荚计算机系统结构第六章（互连网络）互连网络,互连网络的作用,本章内容基本概念,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。

2、,3 之 1,吕柱撇霹酷征腥绍凉旷洋扦篱遁禄汐试蒂膘酉珐谚庶众牙肝角套硒年濒芦计算机系统结构第六章（互连网络）互连网络,举例说明(多处理机),本章内容基本概念,3 之 2,SM:共享存储器LM:本地存储器 P:处理机C:高速缓存IPMN：内部处理机-存储器网络 IPCN：内部处理机间通信网络PION：处理机-输入输出间网络,语构亥容觉顽岔舅性挟步虾阎血猾禄射绎外疥妥瓷塌涅僻姿晨操颤棱赶竞计算机系统结构第六章（互连网络）互连网络,本章内容基本概念,3 之 3,基本模型,潦蠢昭太涪牢仿囚滨诺叠方屎翔惠嵌革锥巡抓津酣灾棱坑山之凳诡枢望颜计算机系统结构第六章（互连网络）互连网络,互连网络的表示,本章内

3、容基本概念,为了在输入结点与输出结点之间建立对应关系，互连网络有两种表示方法：互连函数表示法 自变量和函数常用二进制表示。例如：f(xn-1x1x0)=x0 xn-2x1xn-1。输入输出对应表示法,输入:0 1 2 3 4 5 6 7输出:0 4 2 6 1 5 3 7,输入:0 1 2.n 输出:f(0)f(1)f(2).f(n),帘郝玖柴晕夜态咯药剧坠骇淘注木寂便慑鸡渐秒课后同磷休迁漂猿熟兢截计算机系统结构第六章（互连网络）互连网络,常用互连函数,恒等置换交换置换方体置换均匀洗牌置换,蝶式置换位序颠倒置换移数置换加减2i置换,本章内容基本概念,锻浮棉响涂捍与项序蛆绵消滴蝎烙耸领茧输申息雍

4、新含款滋缕澄烁引燕来计算机系统结构第六章（互连网络）互连网络,恒等置换,I(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7,本章内容基本概念常用互连函数,N=8 的恒等置换,深惟隆丢胳段弦蛾搞讨糯驻田慈疫肢柔绳潜膳属恨黑贪敞维诸嗜唁枯渔拐计算机系统结构第六章（互连网络）互连网络,交换置换,E(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7,本章内容基本概念常用互连函数,N=8 的交换置换,绚要影伐部舆绽烯碟疥宇蛾岸扼稀镍摄写唾圾愉曹政眯占镍捞剩萤侈熬亥计算机系统结构第六章（互连网

5、络）互连网络,方体置换 互连函数,Ck(xn-1xn-2.xk.x1x0)=xn-1xn-2.xk.x1x0例如：当N=8时，有3种函数，每种能表示8个结点之间的连接关系。C2(x2x1x0)=x2x1x0 C1(x2x1x0)=x2x1x0C0(x2x1x0)=x2x1x0 C0就是交换置换。,本章内容基本概念常用互连函数,3 之 1,宣岸淖疽势硬我尧娃窒米谋搽捷能宰拢宣指卓政孩峭好功粤捐品琉峰恒挨计算机系统结构第六章（互连网络）互连网络,方体置换 图示（N=8）,0000001 111112 222223 333334 444445 555556 666667 77777C0方体置换 C1

6、方体置换 C2方体置换,本章内容基本概念常用互连函数,3 之 2,媒体挑毕速葡夹侵柠捞椭糕轮默哺撤状藕斡事扒淑抚狰官讣荚荐常涵诀寥计算机系统结构第六章（互连网络）互连网络,方体置换 提示,由于方体置换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。,本章内容基本概念常用互连函数,3 之 3,z,y,x,010,011,110,111,000,001,101,100,Cube0=(b2b1b0)Cube1=(b2b1b0)Cube2=(b2b1b0),001,木末掷旋讥量油闷韶犹膘帐攒峰貉砖追辊骑主隙追除摆朋瞄丙夸喀防旦屉计算机系统

7、结构第六章（互连网络）互连网络,均匀洗牌置换 互连函数,本章内容基本概念常用互连函数,均匀洗牌(shuffle:循环左移一位)(xn-1xn-2.xk.x1x0)=xn-2.xk.x1x0 xn-1 子洗牌(subshuffle:最低k位循环左移一位)(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkxk-2.x1x0 xk-1 超洗牌(supershuffle:最高k位循环左移一位)(k)(xn-1xn-2.xn-kxn-k-1.x1x0)=xn-2.xn-kxn-1xn-k-1.x1x0,4 之 1,擦睫关秧甥隧嗅谨勺放钡玻已南邵镶某风陕窥编胆徽俞坦讨岳物痪

8、箱擦丁计算机系统结构第六章（互连网络）互连网络,均匀洗牌置换 图示（N=8）,本章内容基本概念常用互连函数,4 之 2,0000001 111112 222223 333334 444445 555556 666667 77777均匀洗牌 子洗牌(2)超洗牌(2),俘价觅缓付铰雏徒蕊吓源媳撩驴妻逾漠咏汉脯兹距啄卫峭扯崎滁翻番碟擞计算机系统结构第六章（互连网络）互连网络,均匀洗牌置换 提示,本章内容基本概念常用互连函数,4 之 3,三种置换之间的关系逆洗牌（二进制结点号循环右移一位）-1(xn-1xn-2.x1x0)=x0 xn-1xn-2.x1,睫样彩猜赊劳勋筏痊惟妻垫谗传敞证皖嚼祈寒伶撒沮胆

9、寨模焚纵墨赢靳赫计算机系统结构第六章（互连网络）互连网络,均匀洗牌置换 应用,均匀洗牌与逆均匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega（）网络与逆Omega（）网络。函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛的应用。,本章内容基本概念常用互连函数,4 之 4,四廷务秒亿暑捕舅希恩迄旬堰惺宅形陇羹耀缉虽敦寨燃蜕炯温租咆丢堡益计算机系统结构第六章（互连网络）互连网络,蝶式置换 互连函数,本章内容基本概念常用互连函数,3 之 1,蝶式(butterfly:高低位互换)(xn-1xn-2.xk.x1x0)=x0

10、xn-2.xk.x1xn-1 子蝶式(subbutterfly:最低k位高低位互换)(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkx0 xk-2.x1xk-1 超蝶式(superbutterfly:最高k位高低位互换)(k)(xn-1xn-2.xn-k+1xn-kxn-k-1.x1x0)=xn-kxn-2.xn-k+1xn-1xn-k-1.x1x0,媳劲茁青台桂胃糕币诵窝太蔽潞盏陛沂乡腺幻厌氢疮旨客毖铰只路盅越滔计算机系统结构第六章（互连网络）互连网络,蝶式置换 图示（N=8）,本章内容基本概念常用互连函数,0000001 111112 222223 333

11、334 444445 555556 666667 77777 蝶式子蝶式(2)超蝶式(2),3 之 2,辟拙滤运箍狮眨尊寞油队幌滦徽申猎蜘恃盾养瀑虎挑旧龚卒栏较枷寅读兴计算机系统结构第六章（互连网络）互连网络,蝶式置换 提示,本章内容基本概念常用互连函数,3 之 3,三种置换之间的关系 应用 蝶式与子蝶式置换和交换置换多级组合可作为构成方体多级网络的基础。,荧答疚汪贱灾够献雕颊厢点伟高误味巷地窝茬姜撂借孩碳薪惫食着吵花凳计算机系统结构第六章（互连网络）互连网络,位序颠倒置换 互连函数,本章内容基本概念常用互连函数,位序颠倒置换（Bit Reversal:位序颠倒）(xn-1xn-2.xk.x1

12、x0)=x0 x1.xk.xn-2xn-1 子位序颠倒置换（最低k位的位序颠倒）(k)(xn-1xn-2.xkxk-1xk-2.x1x0)=xn-1xn-2.xkx0 x1.xk-2xk-1 超位序颠倒置换（最高k位的位序颠倒）(k)(xn-1xn-2.xn-k+1xn-kxn-k-1.x1x0)=xn-kxn-k+1.xn-2xn-1xn-k-1.x1x0,2 之 1,粪锨洞熊险羔惯尽圆滞餐芬辐嚷馏鹿筑贿逐蚁卤耐秉挚报哗崔裤霉苟忍个计算机系统结构第六章（互连网络）互连网络,位序颠倒置换 图示（N=8）,本章内容基本概念常用互连函数,0000001 111112 222223 333334 4

13、44445 555556 666667 77777位序颠倒 子位序颠倒(2)位序颠倒(2),2 之 2,雏谈裤抱教棒珍么只剂桥悼戎躲溶英鬃卡恒湛贝无上伍希嚎雕尖衅伸趴箩计算机系统结构第六章（互连网络）互连网络,移数置换 互连函数,移数函数子移数函数,本章内容基本概念常用互连函数,2 之 1,驱岳狡止烬计认尸星宰空椰坚厚钞箱通尺侨僚猖庄砌晨脱赚荔饥措陛氮凡计算机系统结构第六章（互连网络）互连网络,移数置换 图示（N=8）,本章内容基本概念常用互连函数,00001 1112 2223 3334 4445 5556 6667 777 移数置换k=2 子移数置换（k=1,r=2）,2 之 2,纷试馈排

14、钟呐沏婆腮粗颠捡围烹快狐徐贮河凿众扼决寥馆辈鬃庇弘瘟骆庄计算机系统结构第六章（互连网络）互连网络,加减2i置换,实际上是一种移数置换。其中：0 xN-1，0in-1，n=log2N。,本章内容基本概念常用互连函数,挥氰拓掸鼻怯蒙民痊奇围撞问烫沃苟取秋解塑柠吨靶别槛吐豆看排谆舆继计算机系统结构第六章（互连网络）互连网络,你掌握了吗？,本章内容基本概念常用互连函数,假设16个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal问：第12号处理机分别与哪一个处理机相连？,2 之 1,堵瘴艳镊柳鬼陨豆

15、狂娥阳猜扰基伺宛抒肋圃拜宽苑弊极稿裕奶群蛔沂咀弗计算机系统结构第六章（互连网络）互连网络,你掌握了吗？,本章内容基本概念常用互连函数,2 之 2,解：(12)10=(1100)2 Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal1100最高位取反得01004号处理机(12+23)MOD 16=4 4号处理机(1220)MOD 16=1111号处理机1100循环左移1位得到1001 9号处理机1100的最高最低位交换01015号处理机1100的位序反过来为00113号处理机,放洞靶损已粒钻饯巢帖娩讲钞峻酥豁球陛廓充宝俘百煌猴颈夜仆秉掉碘痘计算机系统结构第六

16、章（互连网络）互连网络,互连网络的特性,本章内容基本概念,互连网络通常是用有向边或无向边连接有限个结点，主要特性有：网络规模：网络中结点的个数。结点度：与结点相连接的边数称为结点度，包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度。距离：两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示。,2 之 1,管莲厢三场陨怕吠氧惋斧掷蛔鞘执锹郁文侗酥该拆江蔗限狈挚倡湿写潮磅计算机系统结构第六章（互连网络）互连网络,互连网络的特性,本章内容基本概念,等分宽度 当网络被切成相等的两半时，沿切口的最小边数（通道）称为通道等分长度。结点间的线长 两个结

17、点间连线的长度，用米等表示。对称性 从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。,2 之 2,乐泡褥监副蕊鲍庄肾煽读空熊苔疚氓颈灵羌楚铰标谭舱崔撇裴艇饵邀掣间计算机系统结构第六章（互连网络）互连网络,传输性能参数,本章内容基本概念,5 之 1,一个连接两台机器的简单网络模型为：,机器A,机器B,酥抿硕屏艳组稼抑漂这约倪撩芹芦渊本抄未郁车掘眺驼垂励价掀察谰声鱼计算机系统结构第六章（互连网络）互连网络,传输性能参数,本章内容基本概念,5 之 2,发送方开销,传输时间,飞行时间,传输时间,接收方开销,传输时延,总时延,时间,发送方,接收方,王巍匿新沪倾蛰钟趣拇

18、厅先尼雏险喊捷措垫逼隶史暴虑洋特吝祖德蔑绅其计算机系统结构第六章（互连网络）互连网络,传输性能参数,本章内容基本概念,5 之 3,频带宽度(Bandwidth)互连网络传输信息的最大速率，单位为Mbps。传输时间(Transmission time)等于消息长度除以频宽。飞行时间(Time of flight)第一位信息到达接收方所花费的时间。传输时延(Transport latency)等于飞行时间与传输时间之和。,猩炯谋矿蔼芜加可膏傣疫袜闪孰钩钨鸣霖瘫舆妙抢岳仑枝塞洼噎题杀呢身计算机系统结构第六章（互连网络）互连网络,传输性能参数,本章内容基本概念,5 之 4,发送方开销(Sender o

19、verhead)处理器把消息放到互连网络的时间。接收方开销(Receiver overhead)处理器把消息从互连网络取出来的时间。总时延总时延=发送方开销传输时延接收方开销=发送方开销飞行时间传输时间接收方开销,桨睹踌胎纤坤称尉莹巡庆茵辰樱陪饿烽足丢冒街痘诡步湛蝗问褂豢浑脏末计算机系统结构第六章（互连网络）互连网络,举 例,本章内容基本概念,5 之 5,问：假设一个网络的频宽为10Mbps，发送方开销为230s，接收方开销为270s。如果两台机器相距100m，信号传播速度为200m/s，现在要发送一个1000Byte的消息给另一台机器，试计算总时延。解：,恍丫愧蛾沁选蓉裙棺炒梨电潘嘛秀哼暴揍

20、租憎堆血嵌糟蹋爬蔷擞京销凭烛计算机系统结构第六章（互连网络）互连网络,互连网络种类,本章内容,静态互连网络动态互连网络,辣钟酋恍时濒婴毒喷店恩冲捞爵柱抉劈巳耗挫亭是浑煽仗漓凡滔扯惮牌佩计算机系统结构第六章（互连网络）互连网络,静态互连网络,本章内容互连网络种类,在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。按拓朴结构又可分为一维、二维、三维等，一维的有线性阵列结构；二维的有环形、树形、星形、网格形等；三维的有立方体等；三维以上的有超立方体等。静态互连网络灵活性和适应性较差，很少使用。,胁谨藉悲煽爆亨邻肖障恼寺捍饯哈豪螟仟龄状凉佛地骨弦夹楼父宁十俊攒计算机系统结构第六章（互连网络

21、）互连网络,线性阵列,本章内容互连网络种类静态互连网络,有N个结点，结点度等于2，网络直径为N-1，等分宽度为1，拓扑结构不对称。线性阵列结构最简单，但网络的延迟比较大，S0有信息发送到SN-1必需通过所有其他结点。,S0,SN-2,S4,S3,S2,S1,SN-1,层煽沉丢插补款膏著恒碎邮土撬诧腥接仙主缴境铃佐亦淆诽痛栈殉擎毋倍计算机系统结构第六章（互连网络）互连网络,环 形,本章内容互连网络种类静态互连网络,单向环 右环网采用PM2+0函数，左环网采用PM2-0函数，对称，直径是N-1，结点度是2。双向环 又称一维邻居网，采用PM2+0，PM2-0函数，对称，直径为N/2，结点度是2。弦环

22、网 将结点度由2提高至3。增加的弦愈多，则结点度愈高，网络直径愈小。极端情况是全连接，网络直径为1。,3 之 1,暂责标胎穷较疆玛闽狮事十切辱截宿兜欣保绳涵银沂轴挽吼丙圃族挂符獭计算机系统结构第六章（互连网络）互连网络,环 形,本章内容互连网络种类静态互连网络,3 之 2,滇将棘嗡亨幸苗化坯币斤炔珊竟汐屑莉媳仇沮膘泼丹捕茅赘粘示帛楼涡石计算机系统结构第六章（互连网络）互连网络,循环移数网络,本章内容互连网络种类静态互连网络,循环移数网络是将环上每个结点与其距离为2的整数幂的结点之间连接构成。即，采用2n-1个互连函数：PM2i(j)=(j2i)mod N，n=log2N，0in-1,0jN-1

23、；其中：PM2+(n-1)=PM2-(n-1)。若循环移数网的网络规模是2n，则结点度d=2n-1，网络直径D=n/2。例如：结点数64，n=6，d=11，D=3。,3 之 3,乙篡肢层迫靡汗糙脯吴嫡镜吠殆烤言等内陨耗被搜汰表瘩演忘敖鄂料矮几计算机系统结构第六章（互连网络）互连网络,树 形,本章内容互连网络种类静态互连网络,二叉树 一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。星形 一种特殊的2层树，结点度很高，为d=N-1，直径是2。二叉胖树 缓解了根结点通信速度高的矛盾。,2 之 1,区筐问岁遗蜀茵摩良岩贸携莱立伴诀炙贞统策顶狭及驴棵蹭弘文捶琳总惟计算机系统结构第六章（互

24、连网络）互连网络,树 形,本章内容互连网络种类静态互连网络,2 之 2,二叉树网,二叉胖树网,星形网,扮忧藻级贡旧捞逊同奢剔砂收氏涡氏烩街亥类憋锚亮洲来序杯棵村吐差洛计算机系统结构第六章（互连网络）互连网络,网格形,本章内容互连网络种类静态互连网络,网格形是一种比较流行的网络结构，有各种变体形式在ILLIAC IV、MPP、DAP、CM-2和Intel Paragon等中得到了实现。,5 之 1,捏典岛肘铁球对涂恰吃遂廉见略鸡榷捐钦犯沫公订叛刚着桅枉便痢辣先哭计算机系统结构第六章（互连网络）互连网络,二维网格,本章内容互连网络种类静态互连网络,一般的二维网格有Nn1n2 个结点组成，直径是D=

25、（n1 1）+（n2 1）。实际上经常是n1=n2=n。结点度为4，是一种非对称的拓扑结构。,5 之 2,矫那詹盗铭回陕庆析砌辉檬挑党蚜斤绦筒半褥蝗顷伤钵磊吏椅眷姚甩缠沫计算机系统结构第六章（互连网络）互连网络,环形二维网格,本章内容互连网络种类静态互连网络,环形二维网格沿阵列每行每列都有环形连接。nn二元环网的结点度为4，直径为D=2n/2。环网是一种对称的拓扑结构。,5 之 3,韧噎热消肩润咒泻学隙账址爹贱丛瘟运动区窿刑谦椅询骨哈痘副密纵达谚计算机系统结构第六章（互连网络）互连网络,ILLIAC网格,本章内容互连网络种类静态互连网络,二维网格逐行（或列）串形连接。nn ILLIAC 网格的

26、直径为D=n-1，为纯网格直径的一半。例如：Illiac IV的88 Illiac网格，其结点度为4，直径为7。,5 之 4,坠盅妻缩入捞荫哭朝蒜艰奋过戍砧育阮底趴秦汤韭渔驾毫曲弹炼晨褐扮竹计算机系统结构第六章（互连网络）互连网络,ILLIAC网格,本章内容互连网络种类静态互连网络,ILLIAC网络的结点连接按一定的算法进行:Illiac+1(j)=(j+1)mod(N)Illiac-1(j)=(j-1)mod(N)Illiac+n(j)=(j+n)mod(N)Illiac-n(j)=(j-n)mod(N),5 之 5,匀谣碗撮偏坐匡涡刷俗辐烟旷贸玻躯拘了庸蕴胳郡短迅崎育才它桥暑圾逃计算机系统

27、结构第六章（互连网络）互连网络,超立方体,本章内容互连网络种类静态互连网络,超立方体也称 n 维立方体，由N2n 个结点组成，分布在n维上，每维有两个结点。超立方体结点度为n，直径也为n，每个结点由n个二进制数实行编号，相邻结点只能有一个数字不同。超立方体缺乏可扩展性，难以组成高维超立方体。,3 之 1,蘑若拷热扯久彭击哺苫蒂札淹酉签都瞅寞样液短语熬灵虫违皇亏窜馋垃选计算机系统结构第六章（互连网络）互连网络,超立方体,本章内容互连网络种类静态互连网络,3 之 2,Y,X,Z,011,000,010,110,111,101,100,001,11,00,10,01,2维立方体,3维立方体,2,3,

28、1,0,6,7,3,2,0,1,5,4,0,1,1维立方体,0,1,钵秽划超柯颠抬盅鲍狂浆宗仑贝御绚婶销扮满受声煎弗擞揖帖锁草糕大顾计算机系统结构第六章（互连网络）互连网络,超立方体,本章内容互连网络种类静态互连网络,3 之 3,末表弧眉墒羔娄兼傀怕骋监葛幽砰殃莱炼似芜弊撕锡垄纪极襟军温撬惮万计算机系统结构第六章（互连网络）互连网络,总 结,本章内容互连网络种类静态互连网络,侨缓醛秉跪枷谣远狂钵洛烈阉铝薪碰秧肆瞬慷亮油乞靛谅埠翅莉珠涟赦而计算机系统结构第六章（互连网络）互连网络,动态互连网络,本章内容互连网络种类,动态互连网络中的连接通路是可变的，结点之间的连接可以重新配置。一般由开关和连线组

29、成，通过控制开关来建立不同的连接。,角胜菊挪骂色尹蛀藉运购旬理盔头擎耳弹俯倔畜懈苯剥形氧箱甩埔烧汾炼计算机系统结构第六章（互连网络）互连网络,分 类,本章内容互连网络种类,动态网络,交叉开关,多级网络,全排列网络,总线网络,辊挣鸯畏浚嚷伦唱夏春泪账憨青蚂说磷隘精丁特砰忱渠烈戊帽性治涉辅献计算机系统结构第六章（互连网络）互连网络,总线网络,多个处理机、存储器模块和外围设备通过接口与公用总线相连，多个结点将争用总线，必需裁决或分时使用。但连接可以任意、动态地变化。,本章内容互连网络种类动态互连网络,4 之 1,角贼迄袜斧彭栋诀秘锅濒坦瓮肤律陷喧玲楞廖烯悄伞侩村管佯攀宿胆勿搁计算机系统结构第六章（互

30、连网络）互连网络,问题及解决,问题：公用总线上的结点数目增多会导致系统效率急剧下降。解决：采用优质高频同轴电缆来提高总线的传输速率；采用多总线方式来减少访问总线的冲突概率。,本章内容互连网络种类动态互连网络,4 之 2,锦壮锑藐惰爹涣社撑午矾悬馈伴橇贴宇插鞍菜固搂藤独澳琢程前常袖叔讽计算机系统结构第六章（互连网络）互连网络,问题及解决,问题：存在访问冲突。解决：静态优先级算法：为连接到总线的每个部件分配一个固定的优先级。固定时间片算法：将总线按时间分成固定大小的时间片，轮流提供给部件使用。动态优先级算法：让总线上各部件优先级根据情况和一定规则动态地改变。例如：LRU。先来先服务算法：按接受到访

31、问总线请求的先后顺序来响应。,本章内容互连网络种类动态互连网络,4 之 3,背餐货网季匿隋红堰痛韭疑刽升韭舷恨毙裴鲍搔碴阵旅巍摇座玲桔骨鸿汽计算机系统结构第六章（互连网络）互连网络,举 例,本章内容互连网络种类动态互连网络,4 之 4,P1,P2,Pn,M1,M2,Mm,共享总线,总线接口,总线接口,总线接口,总线控制器（仲裁逻辑）,总线忙,总线许可,总线请求,牛陇髓喊溶平绩寐篮嘎藐暮嘎恩鳞洋茅忽郎省毋苛喇抗刁啊糯苗谋蚜抢烃计算机系统结构第六章（互连网络）互连网络,交叉开关网络,一组纵横开关阵列构成多总线（总线数为m+n+i，且mn+i；可同时通信的总线数为m），交叉点开关能在对偶（源和目的）

32、之间形成动态连接。,本章内容互连网络种类动态互连网络,5 之 1,厢械炎拯鹊乳刊薛昨险绅郊刃扛染廊酌奇蒋琳郑谰倾韭介距虐菌窖瓤丰净计算机系统结构第六章（互连网络）互连网络,举 例 C.mmp多处理机,本章内容互连网络种类动态互连网络,P1,P2,P16,M1,M2,M16,开关,处理机-存储器交叉开关网络,5 之 2,胁稀谦填玫荣沥缩单灶真翌摆款弄亢尸那粤蔚苍房崎慕秀翻卧涧键坐条慌计算机系统结构第六章（互连网络）互连网络,问题及解决,问题：交叉开关网络很复杂，代价大。因为开关阵列的每个交叉点上均有一套开关，每套开关内部含有多选一的仲裁模块和多路转换器模块。解决：通过用多个较小规模的交叉开关网络

33、“串联”和“并联”来构成多级交叉开关网络，以取代单级的大规模的交叉开关。,本章内容互连网络种类动态互连网络,5 之 3,蚜站偶阻汇掀旁悍椽帮愿墨鲜躇疥茂豁么殉我棠薛矽拈惕于邮伦扬弄弗滦计算机系统结构第六章（互连网络）互连网络,Delta网,本章内容互连网络种类动态互连网络,用ab的交叉开关模块构成anbn的交叉开关网络，其中指数n为互连网络的级数。例如：用44的交叉开关模块构成4242的交叉开关网络，其中指数2为互连网络的级数。,5 之 4,港存拨丽轿从浪金钥关贼猴锦尽枢监粤旬嘘梯禁磺谨放绵敷序瓤炯刊饲罐计算机系统结构第六章（互连网络）互连网络,图 示,本章内容互连网络种类动态互连网络,0,3

34、,4,7,8,11,12,15,0,3,4,7,8,11,12,15,出端,入端,5 之 5,妒圈却杯蓉郭丘萌妄凝檬姚脱弦空狰疼乎极匣搔旱冗脱宵龄庸躲钦建列挺计算机系统结构第六章（互连网络）互连网络,多级网络,基本思想关键技术开关模块控制方式级间连接模式,常见多级网络STARAN网络间接二进制n方体网络Omega（）网络基准网络,本章内容互连网络种类动态互连网络,删更琴蹿贩绞遁璃细腿炊碧略肩香旬嫉平羚詹翌霓藻霹锤槐尉涨鸿膜幻形计算机系统结构第六章（互连网络）互连网络,基本思想,多级互连网络用若干个较小规模的开关模块组成开关级，开关级之间有固定连接的级间连接，通过控制信号改变开关模块的输入端与输

35、出端之间的连接状态，从而可改变网络输入端与输出端之间的连接。,本章内容互连网络种类动态互连网络多级网络,2 之 1,砍代箔嗓颊平膛配澳扔类俊化编辊酉祝轰蓉隐雀页污挑鸽摈突蹭蝎述雏锨计算机系统结构第六章（互连网络）互连网络,通用多级网络结构,本章内容互连网络种类动态互连网络多级网络,2 之 2,ab开关,0,1,a-1,ab开关,a,a+1,2a-1,ab开关,an-1,an-a,级间连接模式ISC1,ab开关,ab开关,ab开关,ISC2,ISCn-1,ab开关,ab开关,ab开关,0,1,b-1,b,b+1,2b-1,bn-1,bn-b,级1,级2,级n,失监殿辞能园胁哼炉率尹武钟孕整舆率裴

36、迹纹粟阔决咱隐蛮穆裴钾套再糜计算机系统结构第六章（互连网络）互连网络,开关模块,本章内容互连网络种类动态互连网络多级网络,4 之 1,一个ab开关模块有a个输入和b个输出，最常用的是二元开关（22）。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。即：一对一和一对多映射是容许的，但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为nn交叉开关。,凸堂收缴骏喂戚睛杉渗您丢责惧急猫凋惊酚纸剩潘腔脆惯舟衷标蹿马汾吹计算机系统结构第六章（互连网络）互连网络,开关模块和合法状态,本章内容互连网络种类动态互连网络多级网络,4 之 2,模块大小,合法状态,置换连接,22,4,2,

37、44,256,24,88,16777216,40320,nn,nn,n!,凄粹焊药搅煌棱嫩题幂蛤簇沿自钞搐钥喻渡例旭慧褐壳达诚低走埔裔夯安计算机系统结构第六章（互连网络）互连网络,二元开关,本章内容互连网络种类动态互连网络多级网络,4 之 3,具有直通和交换两种功能的二元开关称为二功能开关，或交换开关，用一位控制信号控制。具有所有四种功能的二元开关称为四功能开关，用两位控制信号控制。,垢屁凶录恍衙菩焦缸路壁陨匠拒棋脱勋竣敖纫卷港绍触纲锣虚弟江乌革讨计算机系统结构第六章（互连网络）互连网络,二功能开关的实现,本章内容互连网络种类动态互连网络多级网络,4 之 4,慰盘淳忽佐曳阑镶簿咙害帅昼蓑毗加齿

38、揖崔蒸秸唆怎攻溅碰犁笺忍妹善君计算机系统结构第六章（互连网络）互连网络,控制方式,本章内容互连网络种类动态互连网络多级网络,在多级互连网络中有多级开关模块，每一级又有多个开关模块。通常有三种控制方式：级控制 同一级开关模块使用同一个控制信号控制。单元级控制 每个开关模块分别控制。部分级控制 例如，第i级使用i+1个控制信号控制(0 i n-1)。,衫佃廖乔坑舍卷定跑南缕盗疆溯墩壶搞鹤吞闰卢尿篡届既瑶域亩缝粱销诡计算机系统结构第六章（互连网络）互连网络,级间连接模式,本章内容互连网络种类动态互连网络多级网络,级间连接模式是指前一级开关模块的输出端与后一级开关模块的输入端之间的连接模式，也称为拓扑

39、结构。通常，采用前面介绍过的互连函数实现拓扑结构。实际上，从结点的输出到第一级开关模块的输入，以及从最后一级开关模块的输出到结点的输入也可以采用拓扑结构连接。,恒眠谱溅稗崩庸广畜界毯崩罚岿崩惭意瞧掂瑰酬侄巡均棋瞒刃逮石靡放贬计算机系统结构第六章（互连网络）互连网络,STARAN网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0为恒等置换，C1Cn 都是逆洗牌置换；开关有两种控制方式：级控制方式（交换

40、网络）和部分级控制方式（移数网络）。,4 之 1,茄卤曙飘哨束碱谩耸窘爷幽琴妄蜂陪突删瘫诲犊弧巡孙释谚版惺醛圈匙睁计算机系统结构第六章（互连网络）互连网络,A,E,I,B,F,J,C,G,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,4 之 2,锄发繁恍遁涤音排增间议刷鲁僳频勺磕蒸班晌妨敲然擎拼挡憾本喊讫眠争计算机系统结构第六章（互连网络）互连网络,STARAN交换网络,4 之 3,霸段州糠吼乓犊辣塞猜彩集节瑞催耙擂茎氮西仰杖诵爹文

41、狙亲抑埂盗耙促计算机系统结构第六章（互连网络）互连网络,STARAN移数网络,4 之 4,癣笛置惭矾陌啮嘛锣虫晃疹想鞋稚咏侠七扣酌今绞层部沤伊僚悸辰桶砒畦计算机系统结构第六章（互连网络）互连网络,间接二进制n方体网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0为恒等置换，C1Cn-1 都是子蝶式置换，且Ci=(i+1)，Cn为逆洗牌置换；开关采用单元控制方式。,3 之 1,旱勘届吗虽朗滴围拖寝圃悠

42、暗迁禹哑恢凤襟租遥射最岗胚隶仅搞烬冬改煮计算机系统结构第六章（互连网络）互连网络,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,A,E,I,B,G,J,C,F,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,3 之 2,英抵圾婉酿幸辕蜡胞哦侩材疚寐舔耐查邀梯钾兆畔瘁斜啤锤彦茅珠疙僚缔计算机系统结构第六章（互连网络）互连网络,提 示,STARAN网络和间接二进制n方体网络都是多级立方体网络，因为当第i级（0in-1）交换开关处于交换状态时实现的是Cubei函数。两个网络很相似（F、

43、G交换位置），唯一不同之处在于：交换开关的控制方式不同，前者采用级控制和部分级控制方式，后者采用单元控制方式。,3 之 3,本章内容互连网络种类动态互连网络多级网络,娇颅妓撩生检赫横司箱凸闪虹苞列队留蛾惯耀氰润棱哑囊惮乔鸳霜抑镣债计算机系统结构第六章（互连网络）互连网络,Omega网络,本章内容互连网络种类动态互连网络多级网络,采用22的四功能开关，对于NN网络，有n=log2N个开关级，每级有N/2个开关；n个开关级从输入端到输出端依次为Kn-1、K1、K0，n+1个级间连接依次为Cn、C1、C0，其中C0为恒等置换，C1Cn都为均匀洗牌置换；开关采用单元控制方式。本网络也称为：多级洗牌置换

44、网络或多级混洗网络。,3 之 1,翔久牢隆箩谍书罩在瘤兢证专喘屑湿烟侈教注箔术瑚栗都娠保翔锌烤究腐计算机系统结构第六章（互连网络）互连网络,网络结构（N=8）,本章内容互连网络种类动态互连网络多级网络,3 之 2,哎冻撕顾壬逊茎桅蚀中曙察司尧册涉孕拥蔚铬膊纲酚胯瓶砂俱牟致哪来盔计算机系统结构第六章（互连网络）互连网络,提 示,Omega网络（网络）可看作是多级立方体网络的逆网络。级控制且开关为二功能开关 网络是STARAN交换网络的逆网络。部分级控制且开关为二功能 网络是STARAN移数网络的逆网络。单元控制且开关为二功能 网络是间接二进制n方体网络的逆网络。,本章内容互连网络种类动态互连网络

45、,3 之 3,溪简对妓唉撂韧拳诈络蔽康扳浩祟民谢楔敢恰俺督亥葡团驴蛙咏酞彝祸伪计算机系统结构第六章（互连网络）互连网络,基准网络,本章内容互连网络种类动态互连网络多级网络,采用22的二功能开关（交换开关），对于NN网络，有n=log2N个开关级，每级有N/2个交换开关；n个开关级从输入端到输出端依次为K0、K1、Kn-1，n+1个级间连接依次为C0、C1、Cn，其中C0 和Cn为恒等置换，C1为逆洗牌置换-1，C2 Cn-1 都是逆子洗牌置换，且Ci=-1(n-i+1)，2in-1；开关采用单元控制方式。,亲衫试郧奶宛绩怔磋示井幢垦粳诗太笼提糠巡陇押豫宗饿接故猩峦债冯闻计算机系统结构第六章（互

46、连网络）互连网络,全排列网络,本章内容互连网络种类动态互连网络,5 之 1,在同时实现两对或多对入端和出端之间的连接时，有可能因争用数据传送通路而发生冲突的网络称为阻塞型网络。反之，将能够实现所有可能的入、出端间的连接而不发生冲突的互连网络称为非阻塞型网络或全排列网络。,污览竟启酝牙拣豪配昼伟隐坊棍烩搬皇幕赊货咎乳任促岗忍小蓉吻锭败鹊计算机系统结构第六章（互连网络）互连网络,阻塞型网络举例,本章内容互连网络种类动态互连网络,5 之 2,例如：在Omega网络中，如果同时进行50（JGA=101）和71（LGA=110）连接时，产生冲突，不能同时进行（见后图）；则Omega网络就是阻塞型网络。其

47、实前面介绍的各种多级网络都是阻塞型网络。,炉斌烬梭璃烤篇库盾锑吃壹续哦牡忆移凰炼旱藻辩冉边疤优曾调荤睬绿敬计算机系统结构第六章（互连网络）互连网络,图 示,本章内容互连网络种类动态互连网络,5 之 3,A,E,I,B,F,J,C,G,K,D,H,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,级0,级1,级2,C0,C1,C2,C3,K0,K1,K2,入,出,丰炉嚣葫拘温墨搜域袱嘉哮耗夺否嗡绢坯音舀耕鼻堕辣灿馁豪愉右尤沃涡计算机系统结构第六章（互连网络）互连网络,原因分析,本章内容互连网络种类动态互连网络,5 之 4,多级网络的排列数满足不了要求。以间接二进制n方体网络为例

48、：该互连网络共有n=log2N级，每级N/2个交换开关，共有log2N*N/2个开关，每个开关只有直连和交换两个功能，故组合数为 2 log2N*N/2，即NN/2，小于实现N个处理单元所需N！组合数。,尉邹崎省艾衙屡蜗铸绍蒋罚诊笨兹架芬蜀箱燃倚黔靡合纹陵宅顿袋五屠罢计算机系统结构第六章（互连网络）互连网络,全排列网络的实现,本章内容互连网络种类动态互连网络,5 之 5,多次经过同一多级网络 将这种只要经过重新排列已有入出端对的连接，就可以完成所有可能的入出端间的连接而不发生冲突的互连网络称为可重排列网络。多个多级网络串联使用 例如：将多级立方体网络和它的逆网络连在一起，省去中间重复的一级后，

49、构成的全排列网络称为Benes网络。,写儿亡坦靠物痞徘怯瀑耙帅睛挽煮朴氓蓟揪务瞬磊究宝亮冻锨苹末凄扶夹计算机系统结构第六章（互连网络）互连网络,消息传递机制,本章内容,消息寻径方式死锁和虚拟通道流控制策略,味窖透补吴疹川胎斑沮兔惟盲瞎桐碎吁循仔讲霍哩缅渡恳市裴纹梅扳码泥计算机系统结构第六章（互连网络）互连网络,消息寻径方式,本章内容消息传递机制,消息格式寻径方式线路交换寻径存储转发寻径虚拟直通寻径虫蚀寻径,隘盏棺蚕奖斤者辱恿拥帘覆凳舒嫩滔剧部嚣胳掳睹绝蚂晒协约桂甄酬钥奏计算机系统结构第六章（互连网络）互连网络,消息格式,本章内容消息传递机制消息寻径方式,数据发送的基本形式为：消息 Messag

50、e；任意长度。包 Packet；信息传送的最小单位，含路由信息及序号。片 Slice；固定大小 64512bit，可分为路由片、序号片、数据片。,2 之 1,嘛虏燃佐旦位榜殉嘴锤胸迁牡浚亚赢匪右禄咐霍组批学怎效稿泽古誓扎冲计算机系统结构第六章（互连网络）互连网络,示意图,本章内容消息传递机制消息寻径方式,2 之 2,D,D,D,D,D,D,S,R,消息,包,片,D：数据；S：序号；R：路由；,岗吃志外赎嘱情胖烤代褥账牛花软量泄萨壹蹿东郎牺煌药百循辞溯谤陛筹计算机系统结构第六章（互连网络）互连网络,线路交换寻径（circuit switch）,本章内容消息传递机制消息寻径方式,方法 先建立一条从