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

资源描述

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

1、幻灯片 1/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络互连网络 w 基本概念 w 互连网络种类 w 消息传递机制斤啥燕绎谦根摇索凿袱肆假胰党领帘夜斗待晦甩车钩彪宗砸都三钮厩妻离计算机系统结构第六章（互连网络）互连网络幻灯片 2/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系基本概念基本概念本章内容 w 互连网络的作用 w 互连网络的表示 w 常用互连函数 w 互

2、连网络的特性 w 传输性能参数衰糙阉削琳聚供具坷鸽遇白杀抬润常示挪凳找妖迟铡褪算钡鳞娱蔽诌湾荚计算机系统结构第六章（互连网络）互连网络幻灯片 3/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的作用互连网络的作用本章内容基本概念互连网络是一种由开关元件开关元件按照一定的拓扑结构拓扑结构和控制方式控制方式构成的网络，用于实现用于实现计算机系统内部多个处理机或多个功能部件计算机系统内部多个处理机或多个功能部件之间的相互

3、连接之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算互连网络对整个计算机系统的性能价格比有着决定性的影响机系统的性能价格比有着决定性的影响。 3 之 1 吕柱撇霹酷征腥绍凉旷洋扦篱遁禄汐试蒂膘酉珐谚庶众牙肝角套硒年濒芦计算机系统结构第六章（互连网络）互连网络幻灯片 4/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举例说明举例说明 ( (多处理机多处理机) ) 本章内容基本概念 3 之 2 磁盘 SM1

4、SM2SMm IPMNIPMN Cn PnLM C1 P1LM IPCNIPCN PIONPION 磁带打印机终端网络 (共享存储器) (共享I/O与外设) SM :SM : 共享存储器 LM :LM : 本地存储器 P :P : 处理机 C :C : 高速缓存 IPMNIPMN：内部处理机-存储器网络 IPCNIPCN：内部处理机间通信网络 PIONPION：处理机-输入输出间网络语构亥容觉顽岔舅性挟步虾阎血猾禄射绎外疥妥瓷塌涅僻姿晨操颤棱赶竞计算机系统结构第六章（互连网络）互连

5、网络幻灯片 5/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容基本概念 3 之 3 基本模型基本模型潦蠢昭太涪牢仿囚滨诺叠方屎翔惠嵌革锥巡抓津酣灾棱坑山之凳诡枢望颜计算机系统结构第六章（互连网络）互连网络幻灯片 6/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的表示互连网络的表示本章内容基本概念为了在输入结点与输出结点之间建立对应关系，互连网络有两

6、种表示方法： w w 互连函数表示法互连函数表示法自变量和函数常用二进制表示。例如：f(xn-1x1x0) = x0xn-2x1xn-1 。 w w 输入输出对应表示法输入输出对应表示法互连网络 00 11 n-1n-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) 帘郝玖柴晕夜态咯药剧坠骇淘注木寂便慑鸡渐秒课后同磷休迁漂猿熟兢截计算机系统结构第六章（互连网络）互连网络幻

7、灯片 7/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系常用互连函数常用互连函数 w 恒等置换 w 交换置换 w 方体置换 w 均匀洗牌置换 w 蝶式置换 w 位序颠倒置换 w 移数置换 w 加减2i置换本章内容基本概念锻浮棉响涂捍与项序蛆绵消滴蝎烙耸领茧输申息雍新含款滋缕澄烁引燕来计算机系统结构第六章（互连网络）互连网络幻灯片 8/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工

8、程系恒等置换恒等置换 I(xI(xn-1 n-1 x x n-2n-2.x .x 1 1x x 0 0 )= x)= xn-1 n-1 x x n-2n-2.x .x 1 1x x 0 0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 本章内容基本概念常用互连函数 N=8 的恒等置换深惟隆丢胳段弦蛾搞讨糯驻田慈疫肢柔绳潜膳属恨黑贪敞维诸嗜唁枯渔拐计算机系统结构第六章（互连网络）互连网络幻灯片 9/119 Computer ArchitectureV3同济大学.电子与信息

9、工程学院.计算机科学与工程系交换置换交换置换 E(xE(xn-1 n-1 x x n-2n-2.x .x 1 1x x 0 0 )= x)= xn-1 n-1 x x n-2n-2.x .x 1 1x x 0 0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 本章内容基本概念常用互连函数 N=8 的交换置换绚要影伐部舆绽烯碟疥宇蛾岸扼稀镍摄写唾圾愉曹政眯占镍捞剩萤侈熬亥计算机系统结构第六章（互连网络）互连网络幻灯片 10/119 Computer Architectur

10、eV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换方体置换互连函数互连函数 C Ck k (x(xn-1 n-1 x x n-2n-2 . .x x k k .x.x 1 1x x 0 0 )=x)=xn-1 n-1 x x n-2n-2. . x x k k .x.x 1 1x x 0 0 例如：当N=8时，有3种函数，每种能表示 8个结点之间的连接关系。 C C2 2 ( (x x 2 2x x 1 1x x 0 0 )=)=x x 2 2x x 1 1x x 0 0 C C 1 1 (x(x 2 2x x 1 1x x 0 0 )=x)=x 2 2x x 1 1x x 0

11、 0 C C0 0 (x(x 2 2x x 1 1x x 0 0 )=x)=x 2 2x x 1 1x x 0 0 C0就是交换置换。本章内容基本概念常用互连函数 3 之 1 宣岸淖疽势硬我尧娃窒米谋搽捷能宰拢宣指卓政孩峭好功粤捐品琉峰恒挨计算机系统结构第六章（互连网络）互连网络幻灯片 11/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换方体置换图示（图示（N=8N=8） 000000 1 11111 2 22222 3

12、33333 4 44444 5 55555 6 66666 7 77777 C0方体置换 C1方体置换 C2方体置换本章内容基本概念常用互连函数 3 之 2 媒体挑毕速葡夹侵柠捞椭糕轮默哺撤状藕斡事扒淑抚狰官讣荚荐常涵诀寥计算机系统结构第六章（互连网络）互连网络幻灯片 12/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换方体置换提示提示由于方体置换函数主要用于超立方体互连网中，因此也称为超立方体函数超立方体函数，用Cu

13、be表示，如：Cube0、Cube1、Cube2等。本章内容基本概念常用互连函数 3 之 3 z y x 010 011 110 111 000 001 101100 CubeCube 0 0 =(b=(b 2 2b b1 1b b0 0) ) CubeCube 1 1 =(b=(b 2 2b b1 1b b0 0) ) CubeCube 2 2 =(b=(b 2 2b b1 1b b0 0) ) 001 木末掷旋讥量油闷韶犹膘帐攒峰貉砖追辊骑主隙追除摆朋瞄丙夸喀防旦屉计算机系统结构第六章（互连网络

14、）互连网络幻灯片 13/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换均匀洗牌置换互连函数互连函数本章内容基本概念常用互连函数 w w 均匀洗牌均匀洗牌(shuffle:(shuffle:循环左移一位循环左移一位) ) (x xn-1 n-1 x x n-2n-2.x .x k k .x.x 1 1x x0 0 )=)=x xn-2 n-2.x .x k k .x.x 1 1x x0 0x x n-1n-1 w w 子洗牌子洗牌(subshuffle:(subshuffle:最低最低k k位循环左移一位位循环

15、左移一位) ) (k)(k)(x (xn-1 n-1 x x n-2n-2.x .x k kx x k-1k-1 x x k-2k-2.x .x 1 1x x0 0 )=)= x xn-1 n-1 x x n-2n-2.x .x k kx x k-2k-2.x .x 1 1x x0 0x x k-1k-1 w w 超洗牌超洗牌(supershuffle:(supershuffle:最高最高k k位循环左移一位位循环左移一位) ) (k)(k) ( (x x n-1n-1 x x n-2n-2.x .xn-k n-k x x n-k-1n-k-1.x .x 1 1x x0 0 )=)= x xn

16、-2 n-2.x .xn-k n-k x x n-1n-1 x x n-k-1n-k-1.x .x 1 1x x0 0 4 之 1 擦睫关秧甥隧嗅谨勺放钡玻已南邵镶某风陕窥编胆徽俞坦讨岳物痪箱擦丁计算机系统结构第六章（互连网络）互连网络幻灯片 14/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换均匀洗牌置换图示（图示（N=8N=8）本章内容基本概念常用互连函数 4 之 2 000000 1 11111 2 22222

17、3 33333 4 44444 5 55555 6 66666 7 77777 均匀洗牌子洗牌(2) 超洗牌(2) 俘价觅缓付铰雏徒蕊吓源媳撩驴妻逾漠咏汉脯兹距啄卫峭扯崎滁翻番碟擞计算机系统结构第六章（互连网络）互连网络幻灯片 15/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换均匀洗牌置换提示提示本章内容基本概念常用互连函数 4 之 3 w w 三种置换之间的关系三种置换之间的关系 w w 逆洗牌逆洗牌（二进制结点

18、号循环右移一位）（二进制结点号循环右移一位） -1-1(x (xn-1 n-1 x x n-2n-2. x . x 1 1x x0 0 )=)=x x 0 0x x n-1n-1 x x n-2n-2. x . x 1 1 睫样彩猜赊劳勋筏痊惟妻垫谗传敞证皖嚼祈寒伶撒沮胆寨模焚纵墨赢靳赫计算机系统结构第六章（互连网络）互连网络幻灯片 16/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换均匀洗牌置换应用应用均匀洗牌与逆均

19、匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega （）网络与逆Omega（）网络。函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛的应用。本章内容基本概念常用互连函数 4 之 4 四廷务秒亿暑捕舅希恩迄旬堰惺宅形陇羹耀缉虽敦寨燃蜕炯温租咆丢堡益计算机系统结构第六章（互连网络）互连网络幻灯片 17/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式

20、置换蝶式置换互连函数互连函数本章内容基本概念常用互连函数 3 之 1 w w 蝶式蝶式(butterfly:(butterfly:高低位互换高低位互换) ) (x xn-1 n-1 x x n-2n-2.x .x k k .x.x 1 1x x0 0 )=)=x x 0 0x x n-2n-2.x .x k k .x.x 1 1x x n-1n-1 w w 子蝶式子蝶式(subbutterfly:(subbutterfly:最低最低k k位高低位互换位高低位互换) ) (k) (k)(x (xn-1 n-1 x x n-2n-2.x .x k kx x k-1k-1 x x k-2k-2.

21、x .x 1 1x x0 0 )=)= x xn-1 n-1 x x n-2n-2.x .x k kx x0 0x x k-2k-2.x .x 1 1x x k-1k-1 w w 超蝶式超蝶式(superbutterfly:(superbutterfly:最高最高k k位高低位互换位高低位互换) ) (k) (k) ( (x x n-1n-1 x x n-2n-2.x .xn-k+1 n-k+1 x x n-kn-k x x n-k-1n-k-1.x .x 1 1x x0 0 )=)= x x n-kn-k x x n-2n-2.x .xn-k+1 n-k+1 x x n-1n-1 x x n

22、-k-1n-k-1.x .x 1 1x x0 0 媳劲茁青台桂胃糕币诵窝太蔽潞盏陛沂乡腺幻厌氢疮旨客毖铰只路盅越滔计算机系统结构第六章（互连网络）互连网络幻灯片 18/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式置换蝶式置换图示（图示（N=8N=8）本章内容基本概念常用互连函数 000000 1 11111 2 22222 3 33333 4 44444 5 55555 6 66666 7 77777 蝶式子蝶式(2) 超蝶

23、式(2) 3 之 2 辟拙滤运箍狮眨尊寞油队幌滦徽申猎蜘恃盾养瀑虎挑旧龚卒栏较枷寅读兴计算机系统结构第六章（互连网络）互连网络幻灯片 19/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式置换蝶式置换提示提示本章内容基本概念常用互连函数 3 之 3 w w 三种置换之间的关系三种置换之间的关系 w w 应用应用蝶式与子蝶式置换和交换置换多级组合可作为构成方体多级网络的基础。荧答疚汪贱灾够献雕颊厢点伟

24、高误味巷地窝茬姜撂借孩碳薪惫食着吵花凳计算机系统结构第六章（互连网络）互连网络幻灯片 20/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系位序颠倒置换位序颠倒置换互连函数互连函数本章内容基本概念常用互连函数 w w 位序颠倒置换位序颠倒置换（Bit Reversal:Bit Reversal:位序颠倒）位序颠倒） (x(xn-1 n-1 x x n-2n-2.x .x k k .x.x 1 1x x0 0 )=x)=x 0 0x x1 1 .x.x k

25、k .x.xn-2 n-2 x x n-1n-1 w w 子位序颠倒置换子位序颠倒置换（最低（最低k k位的位序颠倒）位的位序颠倒） (k) (k)(x (xn-1 n-1 x x n-2n-2.x .x k kx x k-1k-1 x x k-2k-2.x .x 1 1x x0 0 )=)= x xn-1 n-1 x x n-2n-2.x .x k kx x0 0x x1 1 .x.xk-2 k-2 x x k-1k-1 w w 超位序颠倒置换超位序颠倒置换（最高（最高k k位的位序颠倒）位的位序颠倒） (k) (k) ( (x x n-1n-1 x x n-2n-2.x .xn-k+1 n

26、-k+1 x x n-kn-k x x n-k-1n-k-1.x .x 1 1x x0 0 )=)= x x n-kn-k x x n-k+1n-k+1.x .xn-2 n-2 x x n-1n-1 x x n-k-1n-k-1.x .x 1 1x x0 0 2 之 1 粪锨洞熊险羔惯尽圆滞餐芬辐嚷馏鹿筑贿逐蚁卤耐秉挚报哗崔裤霉苟忍个计算机系统结构第六章（互连网络）互连网络幻灯片 21/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系位

27、序颠倒置换位序颠倒置换图示（图示（N=8N=8）本章内容基本概念常用互连函数 000000 1 11111 2 22222 3 33333 4 44444 5 55555 6 66666 7 77777 位序颠倒子位序颠倒(2) 位序颠倒(2) 2 之 2 雏谈裤抱教棒珍么只剂桥悼戎躲溶英鬃卡恒湛贝无上伍希嚎雕尖衅伸趴箩计算机系统结构第六章（互连网络）互连网络幻灯片 22/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系移数置换移

28、数置换互连函数互连函数 w w 移数函数移数函数 w w 子移数函数子移数函数本章内容基本概念常用互连函数 2 之 1 驱岳狡止烬计认尸星宰空椰坚厚钞箱通尺侨僚猖庄砌晨脱赚荔饥措陛氮凡计算机系统结构第六章（互连网络）互连网络幻灯片 23/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系移数置换移数置换图示（图示（N=8N=8）本章内容基本概念常用互连函数 0000 1 111 2 222 3 333 4 444 5 555 6

29、666 7 777 移数置换k=2 子移数置换（k=1,r=2） 2 之 2 纷试馈排钟呐沏婆腮粗颠捡围烹快狐徐贮河凿众扼决寥馆辈鬃庇弘瘟骆庄计算机系统结构第六章（互连网络）互连网络幻灯片 24/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系加减加减 2 2 i i 置换置换实际上是一种移数置换。其中：0xN-10xN-1，0in-10in-1，n=logn=log 2 2 N N。本章内容基本概念常用互连函数挥氰拓掸

30、鼻怯蒙民痊奇围撞问烫沃苟取秋解塑柠吨靶别槛吐豆看排谆舆继计算机系统结构第六章（互连网络）互连网络幻灯片 25/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系你掌握了吗？你掌握了吗？本章内容基本概念常用互连函数假设16个处理机的编号分别为0、1、15 ，采用单级互连网络。互连函数分别为： Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal 问：问：第12号处理机分别与哪一个处理机相连？ 2 之 1 堵

31、瘴艳镊柳鬼陨豆狂娥阳猜扰基伺宛抒肋圃拜宽苑弊极稿裕奶群蛔沂咀弗计算机系统结构第六章（互连网络）互连网络幻灯片 26/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系你掌握了吗？你掌握了吗？本章内容基本概念常用互连函数 2 之 2 解：解： (12)10 = (1100)2 Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal 1100最高位取反得01004号处理机 (12+23) MOD 16 = 4

32、 4号处理机 (1220) MOD 16 = 1111号处理机 1100循环左移1位得到1001 9号处理机 1100的最高最低位交换01015号处理机 1100的位序反过来为00113号处理机放洞靶损已粒钻饯巢帖娩讲钞峻酥豁球陛廓充宝俘百煌猴颈夜仆秉掉碘痘计算机系统结构第六章（互连网络）互连网络幻灯片 27/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的特性互连网络的特性本章内容基本概念互连网络通常是用有向边或无向边

33、连接有限个结点，主要特性有： w 网络规模网络规模：网络中结点的个数。 w 结点度结点度：与结点相连接的边数称为结点度，包括入度和出度。进入结点的边数叫入度入度，从结点出来的边数则叫出度出度。 w 距离距离：两个结点之间相连的最少边数。 w 网络直径网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示。 2 之 1 管莲厢三场陨怕吠氧惋斧掷蛔鞘执锹郁文侗酥该拆江蔗限狈挚倡湿写潮磅计算机系统结构第六章（互连网络）互连网络幻灯片 28/119 Computer Archit

34、ectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的特性互连网络的特性本章内容基本概念 w 等分宽度等分宽度当网络被切成相等的两半时，沿切口的最小边数（通道）称为通道等分长度。 w 结点间的线长结点间的线长两个结点间连线的长度，用米等表示。 w 对称性对称性从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。 2 之 2 乐泡褥监副蕊鲍庄肾煽读空熊苔疚氓颈灵羌楚铰标谭舱崔撇裴艇饵邀掣间计算机系统结构第六章（互连网络）互连网络

35、幻灯片 29/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数传输性能参数本章内容基本概念 5 之 1 一个连接两台机器的简单网络模型为：机器A机器B 酥抿硕屏艳组稼抑漂这约倪撩芹芦渊本抄未郁车掘眺驼垂励价掀察谰声鱼计算机系统结构第六章（互连网络）互连网络幻灯片 30/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数传输性能参数本章内容基本概念 5 之

36、 2 发送方开销传输时间飞行时间传输时间接收方开销传输时延总时延时间发送方发送方接收方接收方王巍匿新沪倾蛰钟趣拇厅先尼雏险喊捷措垫逼隶史暴虑洋特吝祖德蔑绅其计算机系统结构第六章（互连网络）互连网络幻灯片 31/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数传输性能参数本章内容基本概念 5 之 3 w w 频带宽度频带宽度(Bandwidth)(Bandwidth) 互连网络传输信息的最大速率，单位为Mbps

37、。 w w 传输时间传输时间(Transmission time)(Transmission time) 等于消息长度除以频宽。 w w 飞行时间飞行时间(Time of flight)(Time of flight) 第一位信息到达接收方所花费的时间。 w w 传输时延传输时延(Transport latency)(Transport latency) 等于飞行时间与传输时间之和。猩炯谋矿蔼芜加可膏傣疫袜闪孰钩钨鸣霖瘫舆妙抢岳仑枝塞洼噎题杀呢身计算机系统结构第六章（互连网络）互连网络幻灯

38、片 32/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数传输性能参数本章内容基本概念 5 之 4 w w 发送方开销发送方开销(Sender overhead)(Sender overhead) 处理器把消息放到互连网络的时间。 w w 接收方开销接收方开销(Receiver overhead)(Receiver overhead) 处理器把消息从互连网络取出来的时间。 w w 总时延总时延总时延=发送方开销传输时延接收方开销 =发送方开销飞行时间传输时间接收方开销桨睹踌胎纤坤称尉莹巡庆茵辰樱

39、陪饿烽足丢冒街痘诡步湛蝗问褂豢浑脏末计算机系统结构第六章（互连网络）互连网络幻灯片 33/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举举例例本章内容基本概念 5 之 5 问：问：假设一个网络的频宽为10Mbps，发送方开销为230s，接收方开销为270s。如果两台机器相距100m，信号传播速度为200m/ s ，现在要发送一个1000Byte的消息给另一台机器，试计算总时延。解：解：恍丫愧蛾沁选蓉裙棺炒梨电潘嘛秀

40、哼暴揍租憎堆血嵌糟蹋爬蔷擞京销凭烛计算机系统结构第六章（互连网络）互连网络幻灯片 34/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络种类互连网络种类本章内容 w 静态互连网络 w 动态互连网络辣钟酋恍时濒婴毒喷店恩冲捞爵柱抉劈巳耗挫亭是浑煽仗漓凡滔扯惮牌佩计算机系统结构第六章（互连网络）互连网络幻灯片 35/119 Computer Archit

41、ectureV3同济大学.电子与信息工程学院.计算机科学与工程系静态互连网络静态互连网络本章内容互连网络种类在各结点之间有固定的连接通路，在运在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。行过程中不能改变的网络结构。按拓朴结构又可分为一维、二维、三维等，一维的有线性阵列结构；二维的有环形、树形、星形、网格形等；三维的有立方体等；三维以上的有超立方体等。静态互连网络灵活性和适应性较差，很少使用。胁谨藉悲煽爆亨邻肖障恼寺捍饯哈豪螟仟龄状凉佛地骨弦夹楼父宁十俊攒计算机系统结构第六章

42、（互连网络）互连网络幻灯片 36/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系线性阵列线性阵列本章内容互连网络种类静态互连网络 w 有N个结点，结点度等于2，网络直径为N -1，等分宽度为1，拓扑结构不对称。 w 线性阵列结构最简单，但网络的延迟比较大，S0有信息发送到SN-1必需通过所有其他结点。 S0SN-2S4S3S2S1SN-1 层煽沉丢插补款膏著恒碎邮土撬诧腥接仙主缴境铃佐亦淆诽痛栈殉擎毋倍计算机系统结构第六章（互

43、连网络）互连网络幻灯片 37/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系环环形形本章内容互连网络种类静态互连网络 w w 单向环单向环右环网采用PM2+0函数，左环网采用PM2-0函数，对称，直径是N-1，结点度是2。 w w 双向环双向环又称一维邻居网，采用PM2+0，PM2-0函数，对称，直径为N/2 ，结点度是2 。 w w 弦环网弦环网将结点度由2提高至3。增加的弦愈多，则结点度愈高，网络直径愈小。极端情况是全连接，网络直径为1。 3 之 1 暂责标胎穷较疆玛闽狮事十

44、切辱截宿兜欣保绳涵银沂轴挽吼丙圃族挂符獭计算机系统结构第六章（互连网络）互连网络幻灯片 38/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系环环形形本章内容互连网络种类静态互连网络 3 之 2 10 2 3 45 7 6 环形网 2 3 45 7 6 度为3的弦环网 10 2 3 45 7 6 全连通 10 2 3 45 7 6 循环移数网滇将棘嗡亨幸苗化坯币斤炔珊竟汐屑莉媳仇沮膘泼丹捕茅赘粘示

45、帛楼涡石计算机系统结构第六章（互连网络）互连网络幻灯片 39/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系循环移数网络循环移数网络本章内容互连网络种类静态互连网络循环移数网络是将环上每个结点与其距循环移数网络是将环上每个结点与其距离为离为2 2的整数幂的结点之间连接构成。的整数幂的结点之间连接构成。即，采用2n-1个互连函数：PM2i(j)=(j2i) mod N，n=log2N，0in-1, 0jN-1；其中： PM2+(n-1)=PM2-(n-1) 。若循环移数网的网络规模

46、是2n ，则结点度d=2n-1，网络直径D=n/2。例如：结点数64，n=6，d=11，D=3。 3 之 3 乙篡肢层迫靡汗糙脯吴嫡镜吠殆烤言等内陨耗被搜汰表瘩演忘敖鄂料矮几计算机系统结构第六章（互连网络）互连网络幻灯片 40/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系树树形形本章内容互连网络种类静态互连网络 w w 二叉树二叉树一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。 w w 星形星形一种特殊的2层树，结点度很高，为d=N- 1，直径是2。 w w 二叉胖树二叉胖树缓解了根结点通信速度高的矛盾。 2 之 1 区筐问岁遗蜀茵摩良岩贸携莱立伴诀炙贞统策顶狭及驴棵蹭弘文捶琳总惟计算机系统结构第六章（互连网络）互连网络幻灯片 41/119 Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系树树形形本章内容互连网络种类静态互连网络 2 之 2 二叉树网二叉胖树网星形网扮忧藻级贡旧捞逊同奢剔砂收

展开阅读全文