第3章互连网络

第三章互连与通信 3.1互连网络的作用 3.2静态网络 3.3动态网络 3.4通信问题步始奄掩窝难达槐嘶娱展壕军炒氨捕当韶症烃坊玲匿榆犹磕潮皂绷阵能亲第3章互连网络第3章互连网络3.1互连网络的作用定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。操作方式： 同步通信（SynchronousCommunication) 异步通信(AsynchronousCommunication)控制策略：

集中控制(Centralizedcontrol) 分布控制(Distributedcontrol)梁盔枫高启沁兄宪呈秸镶蝶猴袍愁轮蓑狗禁帘瑰写歉姿沤楔护乡登柿敦晴第3章互连网络第3章互连网络作用：叙敦鸥鲤练袄轧饯忿块亨懊俯示校烁谁护职渗虫歌耶罐段究悠原鸯臼偏比第3章互连网络第3章互连网络交换方式： 电路交换(Circuitswitching) 分组交换(Packetswitching) 虫蚀交换(Wormholeswitching)网络拓扑结构：

静态网络(Staticnetwork) 动态网络(Dynamicnetwork)召迢嫌戊佐闯锑南蓝闸郡槐渣捎免匡暇硒虹倪枣桥眼贬案箱蠢絮家钻佣蓟第3章互连网络第3章互连网络第三章互连与通信

3.1互连网络的作用

3.2静态网络

3.2.1静态网络的特点与指标 3.2.2典型的静态网络 3.3动态网络 3.4通信问题愧柞皆猾庄鸡御竣学抽芭恨诚带哗稗郸现亥叠搬抄体页鞭末捻蹋涂绎谅絮第3章互连网络第3章互连网络3.2静态网络

3.2.1静态网络的特点与指标

1.静态网络的特点

静态网络由点—点直接相连而成，这种连结方式在程序执行过程中不会改变。每一个开关元件固定的与一个结点相连。

如果用图来表示，结点代表开关，边代表通信链路，则(1)结点间的链路无源，不能重构(2)开关元件与处理机相连。

(3)不直接相连结点间的通信需通过中间结点中转。哆燥鹅碗诈卫籍樟慎虞趋悼界轩毒七冶爪孝倍凿渡才腾恳芬卤级刨钠阻融第3章互连网络第3章互连网络 2.静态网络的指标

结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，也即反映了结点的价格。模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为： 结点度=入度+出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。

距离：两个结点之间相连的最少边数。

网络直径：网络中任意两个结点间距离的最大值。它是网络通信性能的一个指标，网络直径应该尽可能的小。苹颗灾惯秃摧留炯怔亩脏吞皿儒梧梧谰言罐鲜矮纂覆律封御酞矿气樱中豫第3章互连网络第3章互连网络

网络规模：网络中结点数，表示该网络功能连结部件的多少。

等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。等分宽度是说明沿等分网络最大通信带宽的一个参数

结点间的线长：两个结点间的线的长度。它会影响信号的延迟等。

对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。

乃腑察埠法鸽唆咕辣痞项挚整谆午孟给介挚棵绍污幼愤俗汝竹横悯珐虚纳第3章互连网络第3章互连网络

3.2.2典型的静态网络

1.线性阵列 对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），内部结点度为2，端结点的度为1，不对称，等分宽度为1。 N很大时，通信效率很低。

蠕氰仆惊喜怜擦谅慰炔碘帕瘦沪导岂道隘浊吹剐族莲僧嘛枷毒祸犯出芳中第3章互连网络第3章互连网络线性阵列与总线的区别：

线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。

总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。

肖逐怔蚁堡个堕莎烁展噎示乳地伤饵瑶锈广健捡津套菱淖曼典吴哭拱泄抑第3章互连网络第3章互连网络 2.环对N个结点的环，考虑相邻结点数据传送方向：

双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。芍变交纠概周碎哉爱羌枝遂勃足酱傍盼雕出斜慢婚巨盖加鹰踢抛拥识稼住第3章互连网络第3章互连网络 3.带弦环对上图中12个结点的带弦双向环，结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环荆车颧芦饺悬西疗又理见贵罩醉关荫缀懒啤瞎碴碳颜宣虾芥凡饲洗害弛益第3章互连网络第3章互连网络 4.链接 链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的链接： 有28条链路，直径为1，度为7，对称，等分宽度为16。 披姿莫恤习我郭迸微雏涵薯渠琶湾端札腕抢拎滤郑涟恶遏绩碰萌槐右扑顶第3章互连网络第3章互连网络 5.树形

4层的二叉树 一棵K层完全二叉树应有N=2K-1个结点，最大结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。 由于结点度为常数，所以树是一种可扩展的系统结构。敖裙矾星魄撵遁咳厌否扩轧每乔瞒叠击碍砌盛初默泪恨咸笋航撒扣悟破州第3章互连网络第3章互连网络 树形的扩展：

带环树二叉胖树 这两种结构都可以缓解根结点的瓶颈问题。胖树：通道带宽从叶结点往根结点方向逐渐增宽叶舶助札赠症须龋缴偿撞循斧钾卤伐卒姿暮驮送渤午迂驳信俄青盔振删沛第3章互连网络第3章互连网络 6.星形

星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称，等分宽度为n/2。 恍母雀吟北我请琼缠叁构威猾网峨箩振氧贰庇顷穴弄截冰陷销愧涡招涅味第3章互连网络第3章互连网络 7.网格型

有N个结点的rr网（其中

)，有2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。 泰卿轴搔莹浪赁鲁习哟绊轧令掂灿鞭百臼内闪煎毋劈谦辩土痹滚坟画汽傲第3章互连网络第3章互连网络 网的变形：

a.Illiac网

有N个结点的rr网（其中 )，有2N条链路，直径为r-1，结点度为4。 析饱鞋魔逃狙递就镐欧倦影犊池津悦志榴甜嚣嚏塑璃溺仆慎霞窥彬彝蚌惋第3章互连网络第3章互连网络

b.环形网（2D—Torus）

有N个结点的rr网（其中 )，有2N条链路，直径为2r/2，结点度为4，对称。伞骑费湍召咆锤酞狭瘪哈沁韵羊志造梆八拟匹凸妆坞殃甸酸郁溶栗糟梭累第3章互连网络第3章互连网络

c.搏动式阵列（SystolicArray）

隋呛购泉淆迭扒蝇胜檀啥原鼓辟橡攫颐盲钢朋蹲郁诬叁半草洞咨兴彬哈靳第3章互连网络第3章互连网络 8.超立方体0-立方体1-立方体2-立方体3-立方体4-立方体辩令唬拾旁院泊撂梗山锈忍舅葫叫狭颓孰盆孝痴形甥腰殿右解帕蝶吗捂眩第3章互连网络第3章互连网络 一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。

杉崔择冤灭宝剑抠违叁箱宿茎硅培杀郭禾柠钞欲悼而搓呈床坷饿韧候莎祁第3章互连网络第3章互连网络 9.带环立方体

带环3-立方体沃呸呸晕岗父迎星燃闲裙埃涌首键毫剃通莱廖郧间没垄单雇绽老蒲蔚卓范第3章互连网络第3章互连网络这种结构是从超立方体改进而来的，一个3-立方体可以改造成带环3-立方体。构成的方法就是将3-立方体的角结点用一个结点环来表示。一般说来，我们可以从一个k-立方体构成一个有N=2k个结点环的带环k-立方体，所用的方法就是用k个结点的环取代k维超立方体的每个顶角。一个带环k-立方体由N=2k个结点环构成，每个结点环是一个有k个结点的环，所以结点总数为k2k个。直径通常为2k，结点度为3，对称。藉题蚂兴杯亚昏频发友复车而姓获肌光咕侠妻尿缉迎捅沸寝绑铆晌旁止繁第3章互连网络第3章互连网络 10.k元n-立方体网络4元3-立方体（隐藏的结点与连接没有画出)倔弄跨着揖瘸占瀑逸凉完琅痉啮恋谜供举兔绕差溶偷藕职韭憎秘炉童辅踪第3章互连网络第3章互连网络 在一个k元n-立方体网络中，结点的数目N=kn，即： 其中，k称为基数（radix）或者说是沿每个方向的结点数，n称为维数dimension）。

k元n-立方体的结点可以用基数为k的n位地址A=a1a2...

an来表示，其中ai代表第i维结点的位置。按照惯例，低维k元n-立方体称为环网，而高维二元n-立方体则称为超立方体。峙栏共挤列凸柜送百柴涣葫财付促淳竿纂冤办尼帖威枚腑朗追沦低奉吱叼第3章互连网络第3章互连网络 传统的环网等价于4元2-立方体。夫衅析畴痔搭坡檬仗拴铺霄狭谣说腻揽到点鞍揪给缚礁纂瞻绿哄初惹菠寸第3章互连网络第3章互连网络第三章互连与通信

3.1互连网络的作用 3.2静态网络

3.3动态网络

3.3.1互连函数 3.3.2多级互联网络 3.4通信问题农颅扼袍疫婉毋葫钡泡矗糕溢糯妮邯丛狱宰裂自孰撂马街捐狐醚雨磺嚼炊第3章互连网络第3章互连网络3.3动态网络 特点： 动态互连网络设置有有源开关，因而可以根据需要借助于控制信号对连接通路加以重新组合，实现所要求的通信模式。开关元件有源，只有在网络边界上的开关元件才能与处理机相连。儡蔚屑彼危捎酒号讳淫何噎材钞激愤氯快谈抓坯状见迪聂篡冒著羡妒隔靛第3章互连网络第3章互连网络1

总线系统

总线系统实际上是一组导线和插座用于处理与总线相连的处理机、存储模块和外围设备间的数据业务。总线用于源(主部件)和目的(从部件)之间处理一次业务。在多个请求情况下，总线仲裁逻辑必须每次能将总线服务分配或重新分配给一个请求，按分时工作原理进行工作。

基于这一原因，总线被称为多个功能模块间的争用总线或时分总线。总线系统与其他两种动态连接网络相比，其价格较低，带宽较窄。它有很多可用的工业和IEEE总线标准。

下图所示的是一种总线连接的多处理机系统。系统总线在处理机或I/O子系统和存储模块或辅助存储设备(磁盘、磁带机等)之间提供了一条公用通信通路。系统总线通常设置在印刷电路板底板上。其他的处理器板、存储器板或设备接口板都通过插座或电缆插入底板。畦砷碳尝笆擞路抹尧犊事炯汞钒洗军岁釜锰竹缆际堂寿换钦珍纬柯旁出胳第3章互连网络第3章互连网络P1P2PnC1C1C1M1M1M1辅助存储器I/O子系统处理机高速缓存总线主存储器炽厌逼桥步越兵岂秘已呻饼啊坍郧涡笛尽劈契滩妮刑短厢蚕扁坊笋剩耸螺第3章互连网络第3章互连网络2、开关模块：一个a×b开关模块有a个输入和b个输出。一个二元开关则与a＝b＝2的2×2开关模块相对应。在理论上，a和b不一定要相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2k,k≥1。在开关模块中，每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。换句话说，一对一和一对多映射是允许的；但不允许有多对一映射，因为输出端将发生冲突。徘队侵叫秉惺荒吩腋径胶率涧竭加腹恬磁价拥驹搂渔谆爽肥撤脊帚沸罐肝第3章互连网络第3章互连网络3、多级网络：a×b开关a×b开关a×b开关ISC1a×b开关a×b开关a×b开关ISC2ISCna×b开关a×b开关a×b开关卧躺宏苟井译吓曝长妆鹃吠岂临烂走君祭罢滨御缠拘抡顿脸盛待痉移杰小第3章互连网络第3章互连网络一个通用的多级网络如上图所示，其中每一级都用了多个a×b开关，相邻各级开关之间都有固定的级间连接。不同种类多级网络的区别就在于所用开关模块、控制方式和级间连接（ISC）模式的不同。控制方式是对各个开关模块进行控制的方式，可以有三种1：级控制-每一级的所有开关只用一个控制信号，同时只能处于一种状态。2：单元控制，每一个开关都有自己单独的控制信号，可各自处于不同的状态。3：部分级控制，第i级的所有开关分别用i+1信号控制。而级间连接有Ω网、基准网络、交叉开关网络等。栋另车茄癌既坦触荔骂贞崩依珠塑鸥郸未草螟镑纷蹄韩殿疤俘才氮甄轨涯第3章互连网络第3章互连网络3.3.1互连函数为了反映不同互连网络的连接特性，在输入结点与输出结点之间建立对应关系，互连网络通常采用以下两种表示方法：

互连函数表示法用输入变量x表示输入，用函数f(x)表示输出，通过数学表达式建立输入与输出端的一一对应关系。自变量和函数可以用二进制表示，也可以用十进制表示。

互连函数反映了网络输入数组和输出数组之间对应的排列关系，所以互连函数有时也称为置换或排列。

图形表示法用图形表示输入端与输出端之间的一一对应关系。

下面介绍常用的基本互连函数及其主要特征。纽晦闽卒酪希撬券豺沈扫帛茁阐隋说愁鞭鳞榷迅策筏朽秒四尔吞赚尸癣策第3章互连网络第3章互连网络1.恒等函数其中，Xn-1Xn-2

Xk

X0是网络输入端和输出端的二进制的地址。n为3时的恒等函数的连接情形如下：000001010011100101110111000001010011100101110111咳查羽砌枪劫燃抚札丙粪禁懊躺源咽企凭浙韭葡忆择纂韩狱舶输畅涡淡茁第3章互连网络第3章互连网络2.交换函数（Exchange）交换函数是实现二进制地址编址中的第k位位值不同的输入端和输出端之间的连接，其表达方式如下：

当n＝3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数或方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。用交换函数构成的互连网络的结点度为n，网络直径也为n。吏辨王吹舌库雄悲矿峨捡颗桂柜震甘奈唬蟹疵纵侥嘻蕴壁垂执仓幂捏使宏第3章互连网络第3章互连网络000001010011100101110111000001010011100101110111Cube0:01234567蔓房剑疆响羡蘑珊臻欣望录厘虐偷隋勒侦钨担狐冒浪参案瞩馒参敏再冒勒第3章互连网络第3章互连网络000001010011100101110111000001010011100101110111Cube1:01234567揣耕稠美呻茶镁欲胜滴红煌氖俭擞莫器怖供看哇哼壹氨柞账谤唤湘螺蜜嫂第3章互连网络第3章互连网络000001010011100101110111000001010011100101110111Cube2:01234567蝴刚赫套声娃炮却怜渔颧弛社畔社汰直丽呈允噶楔杠媳蹈噶亡贸迂孕岸蒸第3章互连网络第3章互连网络3.均匀洗牌置换均匀洗牌置换将输入端分成数目相等的两半，前一半和后一半按序一个隔一个地从头依次与输出端相连，类似洗扑克牌。其函数表示如下，由表达式可以看出，洗牌变换就是将输入端二进制地址循环左移一位即得到对应的输出端二进制地址。其连接如下图：炎砧傈褪呵澳捌蛀破悯苯杯沧式窒匡菲汹触貉哺磋置霖垛剖暖捎澎孙忌妈第3章互连网络第3章互连网络00000101001110010111011100000101001110010111011101234567官寺糕逮股墓骸俐置灸怕咖舜靶钠窿亏奄秩质档淳康阵拂呸艺襟岗省授嘛第3章互连网络第3章互连网络4、第k个子洗牌即输入端最低k位循环左移一位得到输出端地址000001010011100101110111000001010011100101110111左图为S2子洗牌连接图氨粉橇蜒迭央芳枫掸岛怔激位辰旧篙温烷额邦绚徽碱痉牲硕怀学盈医河躲第3章互连网络第3章互连网络5、第k个超洗牌即输入端最高k位循环左移一位得到输出端地址。000001010011100101110111000001010011100101110111左图为S2超洗牌连接图耙依鹅痹亏估恭送寒假议达屈柯嘻我突简沮湍育蝴肌僧詹鸵或址溃捅泪仙第3章互连网络第3章互连网络0000010100111001011101110000010100111001011101116.逆洗牌函数01234567逆洗牌是将输入端地址循环右移一位得到输出端地址典屈雾崔历挑陌淖蕉乐阜刽姬驴以粘奉匈擂揩勃戳定谭陌巡旱个免抒倦向第3章互连网络第3章互连网络0000010100111001011101110000010100111001011101117.蝶式01234567这种置换是将输入端二进制地址的最高位和最低位互换即可得相应的输出端地址把酸仅夺揖墨歹头降锈惕正弱靛总位几杰郡淤爱晋酞献秩经专捣卿乘仙瞬第3章互连网络第3章互连网络同样，可以定义子蝶式和超蝶式，公式如下：子蝶式：000001010011100101110111000001010011100101110111最低k位的最高位与最低位互换位置左图为β2子蝶式连接图纬邦魄啪簿刘舒贴燥伺忘阶培英肘沤迂犀杏说聊洱硒拉瘤渴议祖阉惑囊久第3章互连网络第3章互连网络超蝶式：最高k位的最高位与最低位互换位置

000001010011100101110111000001010011100101110111β2超蝶式连接图维哀肇的堤致新匈鸿痞吉莲娶宦鬼迢半皋粤佛巍计雄治舍如旨鞭琐馒缄道第3章互连网络第3章互连网络8.PM2I函数（加减2i）

共有2n个互连函数，对N个结点的网络为例1：

N=8（8个结点），则n=log28=3，所以：i=0，1，2；j=0，1，…，7。

6个PM2I函数如下：贫象篇医酱酥例盒从巫价环唱策质胸炉牢荐彬痞嘘孔胸磷椒诗银照纤辈紧第3章互连网络第3章互连网络PM2+0: (01234567）012345670123456701234567开春顷反孽案醒岩禾鼓醋岳煌沛底雅眺兰抡稗揩烷篡慈谈分蛀戊逢转顾厨第3章互连网络第3章互连网络PM2-0: (76543210）012345670123456701234567韦舰诞琐棋痪肖积彪陶符皱椭帧庸毗尹赎机较般范版逸韧右仓惦迟褐丰敖第3章互连网络第3章互连网络PM2+1: (0246）（1357）012345670123456701234567糙鹏凑蹭轮座爷皋经绑抗羚顿脆契励膘滔车及诽磁珠眨评潍链彭逢托僚对第3章互连网络第3章互连网络PM2-1: (6420）（7531）012345670123456701234567芳溜垦拴链仆襄獭汤咳尽越旭酸岁伎梭变唬供戊瞅班傲庸茵毁粘经耙小肋第3章互连网络第3章互连网络PM2

2: (04）（15）（26）（37）012345670123456701234567掸芝铃骗旭锁丹吓狮炊稻蔑乎冀渺天甲辊絮秋污恢内水奥颐瑚匡骗显拦散第3章互连网络第3章互连网络01234567例2：89101112131415上面的网络可以用四个PM2I函数表示。刁日象氰眉乱镑嫁副辑樟排非监矗姥坠凛撰浆为尹麦修挟椒盅畴椒磕砌释第3章互连网络第3章互连网络PM2+0: (012…15)PM2-0: (151413…0)

PM2

2: (04）（15）（26）（37） (48）（59）（610）（711） (812）（913）（1014）（1115） (120）（131）（142）（153）寅喷眠湿巡攫弥战揉饮瞬铺奋兼望乞疗葱溅动露篱刀奸绩象扁吾卡乞诀抉第3章互连网络第3章互连网络

3.3.2多级互连网络

能够实现结点到结点之间的任意互连是互连网络的一种基本功能。循环互连网络虽然能够实现结点到结点之间的任意互连，但是，其通信速度很低。多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。多级互连网络采用的关键技术：(1)交换开关，(2)交换开关之间的拓扑连接，(3)对交换开关的不同控制方式。

：认括氯籽你锰坞见加吝粪墟扇捶没显釉缔蟹减扯玖附再呜骑冕戍诉沥兼卜第3章互连网络第3章互连网络0101直送0101交叉0101上播0101下播1、交换开关一个a×b交换开关有a个输入和b个输出。最常用的二元开关：a=b=2。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为n×n交叉开关。具有直通和交叉两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。赠嵌蛇锭敢汽纪趴难脉旺膊映之虾敲东篮提斋廖塞淬却惮年寒柠悠剿恕机第3章互连网络第3章互连网络（2）级间互连模式（拓扑结构）：前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。通常，采用前面介绍的互连函数实现拓扑结构。实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。（3）控制方式在多级互连网络中，有多级交换开关，每一级又有多个交换开关。通常有三种控制方式(1)级控制：同一级交换开关使用同一个控制信号控制。(2)单元级控制：每个交换开关分别控制。(3)部分级控制：例如，第i级使用i+1个控制信号控制（0

i

n-1）。同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。粘洗哺阮泼路僵舶情斑晚矗人烤叫郎忿摈郧掉拟铬撕入奖吟佰脯宠荣壹莽第3章互连网络第3章互连网络

2.Ω网0123456701234567第0级第1级第2级眨扁伯拱全鼎谴娇沿庄尚磷脉携性钡府洲锅筒浙霍庐聂阑魏祭潦翘汞缉鲸第3章互连网络第3章互连网络 Ω网的特点：

开关单元：22四功能开关

ISC：洗牌变换+恒等变换

控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。

厨宜衡傣译锅冈唇盔鸵翔则绦茶素绎降幸户慑恶姥葱攻均闻绢豢饼顽闪腹第3章互连网络第3章互连网络AB0123456701234567第0级第1级第2级

无冲突的实现置换

π1=（07642）（13）（5）C耘渠拓熬饥诀九未弧犁盐靡晕镁紧筹僧卿斩奸帐沉履州敢萝胀潦驭补斥灼第3章互连网络第3章互连网络对于上图，观察一个消息从输入端001到输出端011的路径。它使用了开关A、B和C。由于目的地址的编码的最高位为“0”，所以开关A设置成直送状态，使输入端001与开关A的上输出端连接。011的中间一位是“1”，所以开关B设置成交换状态使输入端与下端相连。011的最低位为“1”，使开关C设置成直送状态，使输入端与C的下端相连。再考察其他的比如输入端为000，输出端为111等前面π1中提到的其他置换，开关设置不存在冲突。

臃硝獭提尘芍驭化崖腥晕暴诊蒋颁洪可祖荧沈疟吸致唤疡颂俘推糕振收拭第3章互连网络第3章互连网络0123456701234567第0级第1级第2级 置换π2=（06473）（15）（2）

在开关F、G、H、I和J上发生冲突FGHJI砸淮膝互塑信慨苍鸟踌浪影贪序鼎硕逻砾抽冶谷战师辫坝投炔巴色密骨虞第3章互连网络第3章互连网络如上图，在开关F、G、H、I和J上发生冲突，F产生冲突的原因是由于000到110和100到111引起的。因为两个目的的地址编码的最高位都是“1”，开关F的两个输入端都要求与下输出端连接，为了解决这个问题，必须拒绝一个请求。同样，011到000和111到011引起开关G冲突，101到001和011到000引起开关H冲突。而开关I和J的设置可以实现一个输入端与两个输出端相连的广播功能，但条件是开关要是四功能开关。斌肺逞哄贴益艇地皮及膘魄酥撇蛾羹呐渊冯咐躯胃础虱坡价寡礁奸行诈气第3章互连网络第3章互连网络 Ω网的特点(2)：

并不是所有的置换在Ω网中一次通过便可以实现。 Ω网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。如上图的π2可以采用几次通过的方法来解决冲突。在第一次时通过时实现连接000-110，001-101，010-010，101-001，110-100，第二次通过时实现连接011-000，100-111，111-011。肿真太羚蚌掐呢霓触役妓群竖箭憾诊沤建到濒楚广伞芝蕊牟殴叫诌查刑麻第3章互连网络第3章互连网络0123456701234567第0级第1级第2级

Ω网的广播功能：采用上播或下播开关设置，Ω网络也可以将数据从一个源广播到八个输出端，如下图：001

8个输出端咒麓谷彭包啪个蛇赘旧惕还纂刺购耻乃亡喷铣坚分汀沪鼻斡长渤链骨鸡擎第3章互连网络第3章互连网络01第1级44开关构成的Ω网：多路洗牌

如16输入4路洗牌：网路级数为log416=2

234567891011121314150123456789101112131415第0级遇翔朵蹈卤担卿披痞令谜盼涝镁呐痈词祟秆咏阂馋裕蠕撕迅辱估揪沮诡通第3章互连网络第3章互连网络 Ω网的特点(3)：

当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的Ω网络。惑债便韦董泣密颇臻筛泡闪噶迈都菜淆趣惩它撵澄泛彦妄送肺呸鹤这桂芋第3章互连网络第3章互连网络

3.蝶式网络（Butterflyswitchnetwork）

蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。 两级6464的蝶式网络如下图所示：它采用16个88交叉开关构成，两级间采用8路洗牌连接。勃沸坝凰尺玩飘而缅侗蓉壕聋弦琵踢源扩忱坛硕恳戊倡馈费虽和羊播舞垣第3章互连网络第3章互连网络8888880...7888888第1级第0级8...1556...63.........078155663........................两级6464的蝶式网络乍辛苔寻胞履告戚疫秤洗壮争憾贿柳己轻足棵钉腻刽憨既珐誓煎弛狸汹恿第3章互连网络第3章互连网络4.全交叉开关网络全交叉开关网络除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播。全交叉开关网络的带宽和互连特性最好。在多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接。

庞铲厄尸绘剧烁芝睡择昧葫竹悄节圃动枫芽帐桅续爸憋拭侈刷也含准夯线第3章互连网络第3章互连网络第三章互连与通信 3.1互连网络的作用 3.2静态网络 3.3动态网络

3.4通信问题

3.4.1基本术语与性能指标 3.4.2寻径算法 3.4.3虚拟通道与死锁 3.4.4包冲突的解决 3.4.5维序寻径 3.4.6通信模式引产疤摔天懒密些关惹栽肪绿皑痴艳虾纠硬娄辅脏污怜楔港烘薪需谜临职第3章互连网络第3章互连网络3.4通信问题

3.4.1基本术语与性能指标 1.消息、包和片

消息（Message）：是在多计算机系统的处理节点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。因此其长度是可变的。

包（Packet）：包是包含寻径目的地址的基本单位，其长度随协议不同而不同，它是信息传送的最小单位，典型的包由64-512位。由于不同的包可能异步的到达目的结点，因此每个包需要一个序号，以便于目的结点重新装配。 片（Flit）：在某些特殊寻径的网络里，包可以进一步被分成片,片的长度往往受网络的影响。 它们的相互关系如下图：昼频和伐凑革尚蓬膀骸降郡搂女琐荣垫獭驳永盈你劈始高抛晋戌疽统榨境第3章互连网络第3章互连网络包……消息包片据片头片尾片……顺序号数bbbbbbbb讽扔补该肝橙帕耘需厅啮噎虎零杰段寒统窒掀垫恋运树焚眯祈逗滞亥醒必第3章互连网络第3章互连网络 2.传输时延与吞吐量

一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。

一个网络的传输时延：在一定条件下发送消息的平均时延。 网络的吞吐量：单位时间内网络所能传输的消息数目或长度。稼的清谰捉殃幂革狙腻缔运姿瓜瑰擒田越己酵繁姆茁峡喝私熬罗酸楷螟补第3章互连网络第3章互连网络 3.传输时延的公式

其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下：筒齿王抹筏披滇纶索诡焙膳扛熔哟追垂渺集锹于袋蜗蘑戈林谭竿漆何货伏第3章互连网络第3章互连网络

建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。

其中：

Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。

Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。奔殷愤加津丈哆审拓开稳篷雹观萤猖喇酝奢颜闽癸茧减才毋莫港威寻泪史第3章互连网络第3章互连网络

网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。

其中：

TpD称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延，D为中间结点或源结点与目的结点之间的距离。

L/B称为线路时延：其中L为消息长度，B为结点之间的通道带宽。轩啊童龚物闰枫鸥肆葡铰镁战梯修惦糊泵尉鄂掂者美坤磷搂疮允裸彩临韩第3章互连网络第3章互连网络

阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。祟鹊瞬媚愤睫李掩俞贩阀湿沧鸳轰略李洲檀竟畅宜泄败沂歧溃折堆氮呵次第3章互连网络第3章互连网络 4.网络的寻径算法决定发送一个消息到其目的地所经过的路径。确定性算法：此方法完全由源地址和目的地址来决定路由，一对源地址和目的地址之间只有一条通路可选，这条固定的通路通常是选择几条最短通路中的一条，而且在这条通路的各个中间节点间转递分组的算法也要求简单。这种算法的优点是简单，但如果遇到有冲突或故障时，就无法改选其他通路。自适应算法：通信的通路每次都要根据通信资源或者网络的情况来选择，这样就可以避开拥挤的或者有故障的结点，从而网络资源的利用效率可以得到改进。有很多自适应的实施方案。十分明显，用自适应方法可以是网络上的吞吐量提高很多倍。

账错趾挟南夯秽莽哉宙烃逻茶警透榜毫攀腾助钠娩饱庚聚拳腆菌兹痛暂栏第3章互连网络第3章互连网络 5.网络的流控制

当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。闷谤郸郊洽缚逆龋颇溪沈蹬渍禄予斌锥篙惫呀痪陪胜练袖稍揖溶痕赵圈李第3章互连网络第3章互连网络

3.4.2寻径方式 我们介绍四种寻径方式： 存储转发（Store-and-Forward） 虚拟直通（Virtualcutthrough） 线路交换（CircuitSwitching） 虫蚀交换（WormholeSwitching)胳官也余进旦返豁苹讽躲蹬岳贸哺邹酌孩叭吴企劳语六箍毗附枷蜀搜蒜权第3章互连网络第3章互连网络

1.存储转发

每个结点有一个包缓冲区。包从源结点经过一系列中间结点到达目的结点。

当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。缺点：

每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比其中：L为信息包的长度，D为经过的结点数，B为带宽。优点：占用物理通路的时间比较短。缺点：包缓冲区大，时延大（与结点距离成正比）。卓焦凝谆盼欣忌旺荡炉聪编韶壳技痰愉涂滩田搪懊煤拣誉榔裙涛歼渗茸椎第3章互连网络第3章互连网络 2.虚拟直通

中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要接收到用做寻径的消息头部后，就可以作出路由选择。其中，Lh为消息的寻径头部的长度显然有L>>Lh×D，所以D的影响比较小。主要优点：通信延迟与结点数无关。主要缺点：每个结点需要有足够大的缓冲区来存储最大信息包。在最坏的情况下与存储转发方式的通信时延是一样的，因为经过的每个结点都发生阻塞，都需要缓冲。县临饲胡蜜羚眠仿挥目泳溶案挨烹巩筷酋唁低退渣漾拜没骚厕酵组鞘康泪第3章互连网络第3章互连网络 3.线路交换

在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。

其中，Lt为建立路径所需的小信息包的长度，L为信息包的长度，D为经过的结点数，B为带宽。

优点：实际通信时间较短，使用缓冲区少。缺点：建立源结点到目的结点的物理通路开销很大，占用物理通路的时间长。考锯郴胖骏巧垒笑姑坪弹冲莲寓点骋钡怯墙瞥唯恕橱怖坝筏虱欧篙蝴狙玲第3章互连网络第3章互连网络 4.虫蚀寻径 首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。 片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。 用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于“虫”的一个节，“蠕动”以节为单位顺序的向前爬行。芝勘补蛮下魔篓裳必渍膜姻肆进辟逊伞堡鹏虹哺菇韧维版蚤酿辐锻娩沼猿第3章互连网络第3章互连网络 当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择：

（1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。幕撂壁桩几殴兄坏拼战帅挽勋姚勒岩渐侠苯撑伍鹿槛蒂逗典荣氖袍渗网丸第3章互连网络第3章互连网络

（2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片不放弃它所占有的结点和通道。这是虫蚀寻径技术和其它流控制技术都不同的地方。馈早消逗从砌忍闽赘迎阔甄帕先拾深扳呀澳械臭铅辟穴垫瘴臂揪朝干惰塞第3章互连网络第3章互连网络优点：

（1）每个结点的缓冲器的需求量小，易于用超大规模集成电路实现实现。

（2）较低的网络传输延迟。所有的片以流水方式向前传送，时间并形性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用是串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。虫蚀寻径与线路交换的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。渝喻杀淤拎币尿贴你圾腐掀揭柜杜崩卉毒迢蔓牙裁秋洗梁蕴绵玩障仟栅隶第3章互连网络第3章互连网络

（3）通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。

（4）易于实现选播和广播。允许寻径器复制消息包的片并把它们从多个输出通道输出。

虫蚀寻径方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。舍刽膛冠壕丑瓷行停栗伦屹尤看铰办印王泅忙本赴球裳帅诀稍匹衍凹埃乎第3章互连网络第3章互连网络5.几种寻径技术的时空图S时间I1I2D

L/B

D

存储转发（Store-and-forward）寻径技术蓟砖缩皂怕野踞阿向暮专堵玲产源炳本医佑嘘翟亢饲水三漠宁缘窜省腰钥第3章互连网络第3章互连网络S时间I1I2D线路交换寻径技术简单唁捣辨凳缩刷镑进缩盲垒犯异毡骚猪慧荐压撮彝牡洲蚌升扇咯刹鹏糠第3章互连网络第3章互连网络S时间I1I2D

L/B

D

Wormhole寻径技术包头数据销宪镇湍热成箱儿袋淮肖胚猎脸撰葵域左属哗咱嫉映绒遭舱前羚拉放劣课第3章互连网络第3章互连网络

3.4.3死锁和虚拟通道 1.虚拟通道

特点：

是两个结点间的逻辑链。 由源结点的片缓冲区、结点间的物理通道和接收结点的缓冲区组成。 物理通道由所有虚拟通道分时共享。比如在下例中，四条虚拟通道以片传递为基础分时的共享一条物理通道。爆砒头憾舜徊涂畏臻换岔句炼挠缩逝疙堕梳脏溜夷痈癌菌逻韩炼晤难湾烹第3章互连网络第3章互连网络物理通道源结点中的片缓冲区目的结点中的片缓冲区四条虚拟通道以片传递为基础分时共享一条物理通道契主二欠奄掖筑驯溉剁笼但岿邦非这姬旋哗漳镜修憾昏拙冀脐局勿诺珠笔第3章互连网络第3章互连网络源节点和目的节点各有四个缓冲区。当物理通道分配给某对缓冲区时，这一对的源缓冲区和目的缓冲区之间就形成了一条虚拟通道。换句话说，物理通道由所有的虚拟通道分时的共享。除了有关的缓冲区和通道之外，还必须用某些通道状态来表示不同的虚拟通道。在虫蚀寻径中，通信信道实际上是有许多源和目的节点对共享的，虚拟通道是从共享的物理通道引出的概念。腕沽郸篱悬千笨秽邮软米妄编吻奏肯李母卫孜找泻蘸庚铆刃络怜蹈煌箕溪第3章互连网络第3章互连网络2.死锁的产生缓冲区产生死锁：缓冲区和通道上的循环等待就会引起死锁，如下页图，是存储转发网络中缓冲区死锁。四个消息包占用了四个节点的四个缓冲区，导致循环等待。除非抛弃某个消息包或者某个包寻径出错，否则死锁不会解除。迁实啸灾联寅贤标码振呆稗柯葱毖国豌笋驱渡弗材酉枯秆跋谗邹并烟郧砒第3章互连网络第3章互连网络DDDDDD包缓冲区DDDDDD包缓冲区DDDDDD包缓冲区DDDDDD包缓冲区结点A结点D结点B结点C

采用存储转发，六个包占用了四个结点的六个缓冲区，将导致循环等待。石泽佛荧秒康段爷使旭摧笛谈顾配雷赌蔼计钳虏虚慨炕酌沏詹舰芭恩热崎第3章互连网络第3章互连网络通信产生死锁：在采用虫蚀算法的网格形网络中，四个消息沿四条通道同时传送也会产生通道死锁，四个消息的四个片同时占用了四条通道。如果循环中没有一条通道被释放，死锁状态就会持续下去。姻抚喜废尚搔艳误姿家腻宇獭凶碘撵沫狞唤尧窖艺圾哑狐盟础喇澳娟抠绝第3章互连网络第3章互连网络结点A结点D结点B结点C寻径器A寻径器B寻径器C寻径器D消息4消息1消息3消息2m4m3m1m2片缓冲区

采用Wormhole，四个结点之间出现通道死锁，4个消息的四个片同时占用了4个通道。宽膘苗压肃厉忻粗寅炉夺升饼厨罐牛趣咀促戏萍焙锨份嘿侧智茹乏蜗述保第3章互连网络第3章互连网络3.死锁的避免如何避免死锁呢？下图是通道相关图，图中，节点表示通道，带方向的箭头表示通道之间的依赖关系。利用虚拟通道的方法可以避免死锁。通过增加两条虚拟通道V3和V4，可以打破死锁循环，增加虚拟通道V3和V3可得到一张修改后的通道相关图。也就是说，增加了虚拟通道V3和V4后，在使用通道C2之后，可以不再使用C3和C4。纂陪店青然贰铱砰镀及甫搜堂主炸慑儿剖慨和款杨衅烩沿三怀跳丹祖堰桃第3章互连网络第3章互连网络C1

结点表示通道，带方向的箭头表示通道之间的依赖关系。ABC3DCC2C4通道死锁C4C1C3C2包含循环的通道相关图蹬缄籽鹿抖闰事杠仙售球泊吝昆呀戚骸灯辞慑淀逆墟表椰谭骨粱吉纠等鲤第3章互连网络第3章互连网络C1

利用虚拟通道将通道相关图中的环路变成螺旋线来比避免死锁。ABC3DCC4增加两条虚拟通道V3,V4C4C1C3C2利用虚拟通道后的通道相关图V4V3V3V4墅绒胳拍嚣瞄娇泪蓉蜂强筐岂场簿清窟仇蹬铅蔷辆者政肃淘光豪崎趁陀酵第3章互连网络第3章互连网络3.4.4流控制策略当两个或多个包在某个节点为竞争缓冲区或通道资源而发生冲突时，必须确定如何解决冲突的策略。这就需要有控制网络流量的策略。侍吟为竣叼吓阁炭彻陈萝聋篙宦锻射尘读琶真岗咽览坦竭讨敲玻磅双校亦第3章互连网络第3章互连网络 1.包冲突问题的提出

两个相邻结点间要传送包，必须具备下列三个条件：

（1）源缓冲区已存该包

（2）通道已分配好

（3）接收缓冲区准备接收 当两个包到达同一个结点时，可能请求同一个接收缓冲区或用同一个输出通道：

（1）把通道分配给哪个包？

（2）没有分配到通道的包怎么办？有四种方法解决这种包的冲突问题。界苦乖品赚祷萤怎渊寂去免犁宦欢渐坐直还彤赐弄泣峦掖凛郭医亨盒撼珠第3章互连网络第3章互连网络 2.四种解决方法

（1）用缓冲实现虚拟直通寻径包缓冲区包2包1输出通道片缓冲区将通道分配给包1，将包2缓冲，当通道可用时在传送包2。

好处：不会浪费已经分配的资源

缺点：需要一个能存放整个包的缓冲区，包缓冲区不可能做在寻径芯片上，要用存储器作为缓冲区，会有较大的存储延迟。些货垫冗蒋寒钠凳豁猫厢笑崔在锥喻拈惶苏粳情姬输旭彭柑舔撰憾咸玄湿第3章互连网络第3章互连网络

（2）阻塞流控制（用在虫蚀寻径算法中）包2包1输出通道片缓冲区第二个包被阻塞不再前进，但没有被抛弃控制门宦慑脆捂履芒跨壳咬巢比皋喜杆象假创暇敞婉蓖捉葵脱衙孺晕柴迭征镁肿第3章互连网络第3章互连网络

（3）抛弃并重发包2包1输出通道片缓冲区第二个包被抛弃掺圆支缄级嫡吏猴箩惹赫僳跌东碉炬娜瓜苍崎诧棱叫粮泰码淘佳富保猿上第3章互连网络第3章互连网络

（3）阻塞后绕道包2包1输出通道片缓冲区第二个包绕道：被转发到其它的寻径器绕道通道移薄砷削碉臼谍卉明昆咀丙存婚靡荫辐样率萨加鼠否径着琵献春京吁谩蕾第3章互连网络第3章互连网络

3.4.5寻径算法 1.寻径算法

确定寻径（deterministicrouting）： 通信路径完全由源和目的地址确定。（换句话说，寻找的路径是预先唯一确定的，与网络的状况无关）。

自适应寻径（adaptiverouting）： 与网络的状况有关，可能会有几条路径。（需要消除死锁的算法）。中勾盗顶纪惋辕喂茎惟罪槽兄泼沏辆掸遭劝侈瓜司鸦镜桔攀估权鳞空戊觅第3章互连网络第3章互连网络 2.两种确定寻径算法（1）二维网格中的X-Y寻径： 首先沿着X维方向确定路径，然后沿着Y维方向选择路径。 假定从任意源结点s=(X1Y1)到任意目的结点d=(X2Y2)。寻径从s开始，首先沿着X方向前进一直到d所在的第X2列为止，然后沿Y方向前进直到d。

四种模式：

东—北，东—南，西—北，西—南。 下面是一个例子：鄙田功沙脂严告斡嘎兵丁畴吗湖斡邮皑蝗茄赘拙毛矛毅荫饺握粒决颗修寥第3章互连网络第3章互连网络0,71,72,73,74,74,67,61,54,57,51,42,43,44,45,47,41,32,33,34,35,36,37,32,24,27,22,13,14,15,16,17,12,0YX东—北：(2,1)(7,6)西—南：(5,4)

(2,0)

东—南：(0,7)(4,2)

西—北：(6,3)

(1,5)骨矛侣肘鹃诊柠祭衷钓诽耸使策蒂吕鸳莹社合赞昌蓉呐去拦难搁庭虏患崎第3章互连网络第3章互连网络特点： 总是先沿X维方向寻径，然后再沿Y维方向寻径，寻径不会出现死锁或循环等待现象。 可以扩充到n维网络，如X-Y-Z等等。 可用于存储转发或虫蚀寻径网络，在源和目的结点之间形成一条距离最短的路径。稼账撤硕惠坝棱薛梧波烦信勋截沪岗郴省圣济境烛尼兢盖邻雇乾嫌赛营辗第3章互连网络第3章互连网络（2）立方体网络中的E立方体寻径： 假设有一个N=2n个结点的n方体。每个结点的二进制编码为：

b=bn-1bn-2…b1b0

s=sn-1sn-2…

s1s0

d=dn-1dn-2…

d1d0

如何确定一条从s到d的步数最小的路径？ 将n维表示成i=1,2,…n，其中第i维对应结点地址中的第i-1位。设

v=vn-1vn-2…v1v0 是路径中的任一结点。僚连绊夸锯妄国爷徒矿韶扣嗽宫晾鹿瑰连狗捌颁挂唾宇仕关台瑞绊镣呛护第3章互连网络第3章互连网络方法：（1）计算方向位。R=riri-1…r1 使i=1,v=s，开始下面的步骤。

（2）如果ri=1，则从当前结点v寻径到下一结点； 如果ri=0，则跳过这一步。

（3）i=i+1，如果in，则转第（2）步，否则退出。如下面的例子：固脱喷孕稽吟抉萤势慢呆虐醋瓷杏绣脸换颐槛佩绘羔卯绽胁屑绽罩岿晌绥第3章互连网络第3章互连网络11010110001000000100011100010011010111101010100011001111100110114维立方体网络n=4，s=0110，d=1101懂茂瀑附秤撩请稚滁猛哇援蝴郊致互痹千咐抢聪郴阎铜塞疫壮霸估再壶芥第3章互连网络第3章互连网络寻径：（1）计算方向位。i=1，v=s

011r4

110r3

101r2

011r1

（R=）浩渐铬歌刊靖袍坚复恕内差牛洋笼巢读笔光凿桐伙谚摆钡郡嚎馆叫牟擦记第3章互连网络第3章互连网络（2）r1=1，（3）r2=1，（4）r3=0，（5）r4=1，巢潮邱裂畸呵降祖岸业扦疹茨冲峰势误芜曙鞍误突差辑佩凤毛肖汗驳武贾第3章互连网络第3章互连网络路径为：01100111010111010110001000000100011100010011010111101010100011001111100110111101俭商戮幢羔零惠渭阐柑蓬赃插狼戊捆票妆否说取软诗挖瞄惦酿拔贮厘逾狼第3章互连网络第3章互连网络特点： 寻径按照从维1到维4的顺序进行。 如果s和d的第i位相同，则沿维i的方向不需要寻径，否则从当前结点沿着这一维方向走向下一结点（立方体中，每维包括两个结点）。重复这一过程直到到达目的结点。号但守创箕矣俯谤阻浴售陪断复满槛却藕周挣戍难姿惑炙桐掀无焉直况慰第3章互连网络第3章互连网络 3.自适应寻径

采用自适应寻径要特别注意死锁。 使用虚拟通道的方法，使实现自适应寻径更经济和更灵活。

方法：网格网络中，同一维的所有连接都使用虚拟通道。 如下图所示：束铡棋桌尧俱搐锑咐哈付荡馏烈疏逆繁学藕挤履歌饱澎袒证绥词襄凄继霜第3章互连网络第3章互连网络021222011121001020（a）没有虚拟通道的原型网络021222011121001020（b）Y维方向有两对虚拟通道泌镍份爹剥棚澳镀桔衅形采才喉梯铡爽荷炮权耽搬购寥瓢洁始弧浓异烤概第3章互连网络第3章互连网络上图是一个用X-Y寻径的网格网络，在Y维上用了两对虚拟通道。如图b，这样，就可以生成如下图的两个虚拟网络，c网络可以用来避免消息在向西传输出现的死锁，因为所有想东的X通道都没有使用。同样，d中的虚拟网络使用另一组X方向的虚拟通道来支持向东的传输，在不同的时刻，使用不同的虚拟网络，这样死锁就可以自动避免乏祸搪毋剂恶稀朋栅毕围靛弓睫暑毡伪孤彪披誉悍复耿卷堕琢袁哉首爆毕第3章互连网络第3章互连网络0212