（计算机系统结构专业论文）多级互连网上无阻塞会议通信的研究.pdf

摘要 摘要 近年来，随着高性能并行计算的迅速发展，多级互连网作为现代并行计算 机和交换系统的核心连接网络，需要更好的支持在并行分布计算机系统里多个 要求协作的处理器之间的通信会议组通信。在多级互连网上无阻塞并发实 现会议组通信受到越来越广泛的关注，成为重要的研究课题。本文主要研究多 级互连网络上各种模式下的通信特点，并基于典型的互连网络结构构造具有良 好通信能力和最优硬件代价的无阻塞会议网络。具体研究内容如下： 论文首先研究了全连接交叉开关和c l o s 网络等两种结构上无阻塞支持会 议通信的实现，给出了c l o s 网络上会议通信的实现策略和无阻塞条件，得到小 规模情况下低延迟无阻塞实现的会议网络结构。 接着为了得到更小硬件代价的会议网络结构，结合o m e g a 复制网受限多播 可以无阻塞并发的性质，讨论了o m e g a 。1 汇集网的结构及其上的自适应路由规约 通信策略，进而得到o m e g a 。1 汇集网受限多对一规约连接无阻塞并发的结论。通 过串接o m e g a l 汇集网和o m e g a 复制网提出新的2 - o m e g a 结构的会议功能网络结 构( g b c c n ) ，并证明了其上受限多会议可以无阻塞的并发实现。 进而按照会议网络三明治策略“置换网+ 会议功能网络+ 置换网 构造出新 的会议网络。新的会议网络中位于两端的置换网采用o m e g a + o m e g a 重排结构， 位于中间的会议功能网络采用本文提出的2 - o m e g a 结构的g b c c n ，从而得到一 个6 - o m e g a 的会议网络。该网络可以实现会议成员任意分布的多会议无阻塞并 发通信，硬件复杂度为3 n l o g n ，传输延迟为6 1 0 9 n ，路由时间为o ( n l o g n ) ， 均达到已有无阻塞网络的最优量级。新构造的6 - o m e g a 会议网络具有更好的整 体对称性，可以折叠为3 - o e m g a 的会议网络，进一步降低硬件代价。 论文提出的6 - o m e g a 会议网络的构造无论在方法上还是在结果上与现有研 究成果相比，都具有一定的优势和创新。由于在设计与实现上具有很好的通用 性，因此对于进一步研究多级互连网上实现各种通信尤其是会议组通信具有积 极的意义。 关键词：多级互连网，o m e g a 网，会议，路由，会议网络 a b s t r a c t m i n s ( m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k s ) 。a si m p o r t a n te l e m e n t si np a r a ll e l c o m p u t i n gc o m p u t e ra n ds w i t c h i n gs y s t e m ，n e e dt oe f f e c t i v e l ys o p p o r tc o n f e r e n c e c o m m u n i c a t i o nw i t h i nac l u s t e ro fp r o c e s s o r sc o l l a b o r a t i n g f o rd e c a d e s ，r e a l i z i n g c o n c u r r e n tm u l t i p ec o n f e r e n c e sn o n b l o c k i n g l yo nt h em i n sb e c o m e sa ni m p o r t a n t i s s u e t h i st h e s i sf o c u s e so nh o wt oc r e a t ean e wc o n f e r e n c en e t w o r kw i t hb e t t e r p e r f o r m a n c e a n dl o w e s t c o s t i n gw h i c h c a nr e a l i z ec o n c u r r e n tc o n f e r e n c e s n o n b l o c k i n g l y t h es p e c i f i cs t u d i e sa r ea sf o l l o w s ： f i r s t l y , t h i st h e s i sa n a l y s e st h es t r a t e g ya n dn o n b l o c k i n gc o n d i t i o n so fc o n f e r e n c e c o m m u n i c a t i o no nc l o sn e t w o r k o nc l o sn e t w o r kw ec a n e a s i l yd e s i g n n o n b l o c k i n gc o n f e r e n c en e t w o r kw i t hr e l a t i v e l yl o w e rl a t e n c y s e c o n d l y , f o rg e t t i n gal o w e rh a r d w a r ec o s t , t h i st h e s i se x t e n d st h eb a s i so n o m e g ar e p l i c a t i n gn e t w o r kt oo m e g a m e r g i n gn e t w o r k i tc o m e st ot h e c o n c l u s i o nt h a t o m e g a 1 i s n o n b l o c k i n gm e r g i n gn e t w o r k f o rc o n s t r a i n e d c o n c u r r e n tm a n y t o o n e c o n n e c t i o n s t h e n ，b yc o n c a t e n a t i n go m e g a 1m e r g i n g n e t w o r ka n do m e g ar e p l i c a t i n gn e t w o r k ，w ep r o p o s ean o v e l2 - o m e g as t r u c t u r e n a m e dg b c c n ( g a t h e r i n g & b r o a d c a s t i n gc o n f e r e n c e c o m p o n e n tn e t w o r k ) ，a n d p r o v et h a tm u l t i p l ec o n s t r a i n e dc o n f e r e n c e sc a nb en o n b l o c k i n g l yr e a li s e d o n g b c c n f i n a l l y , a c c o r d i n gt ot h es a n d w i c hs t r a t e g yo fc o n f e r e n c en e t w o r k ，b yu s i n g r e a r r a n g e a b l eo m e g a + o m e g a a sr e p l a c i n gn e t w o r ka n dg b c c na st h ec o n f e r e n c e c o m p o n e n tn e t w o r k ，a6 - o m e g ac o n f e ：r e n c en e t w o r ki sd e s i g n e d ，w h i c hi sb a s e d u p o na n a l y s i n gh o wt h es t r u t u r eo f5 - o m e g ar e a l i s e sa r b i t r a r ym u l t i c a s t i tc a n r e a l i z ec o n c u r r e n tm u l t i p l ed i s j o i n tc o n f e r e n c e sd i s t r i b u t e da r b i t r a r i l y t h e n ，i th a s 3 n l o g nh a r d w a r ec a s t ，6 1 0 9 nc o m m u n i c a t i o nd e l a y ，o o q l o g n ) r o u t i n gt i m e m o r e o v e r , t h e6 - o m e g as t r u c t u r eh a sb e t t e ri n t e g r a t e ds y m m e t r yt ob ef o l d e di n t o 3 - o e m g a ，w h i c hf u r t h e rr e d u c e st h ec o s to fh a r d w a r e t h en e wc o n f e r e n c en e t w o r ki ss u p e r i o r 幻e x i s t i n gd e s i g n s ，h a sa d v a n t a g e sa n d i n n o v a t i o n si nt h ew a y sa n ds t r u c t u r e s i tc o n t r i b u t e st of u r t h e rs t u d y i n go nm i n s k e yw o r d ：m i n s ；o m e g an e t w o r k ；c o n f e r e n c e ；r o u t i n g ；c o n f e r e n c en e t w o r k s i l 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 导师妣盈垒丝查 签字日期：删签字日期：甲 第一章绪论 第一章绪论 多播i lj ，或一对多通信，是一种主要的群集通信操作。在处理机技术、存储 技术、i o 技术等方面，为了高效地进行数据传输和信息通讯，解决大规模并行 处理机系统性能的瓶颈，也需要并发多播技术。组播通信【2 】，是从一个或多个发 送者到多个接收者的通信，已经广泛地应用于很多场合，比如：音频( 或视频) 会 议，远程教育，信息网络的视频点播服务，矩阵乘法，分布式数据库的记录更新 等。目前对互连网络中的多播和组播有很多相关研究 3 - - 9 。 会议通信1 2 j ，是网络中的一组节点彼此间的通信，是一种重要的组播通信模 型。现有关于会议通信的研究，大多是在协议和路由层次上进行的【1 0 09 1 。应用硬 件提出很好的支持会议通信的网络结构具有重要的理论意义和现实意义。 多级互连网络可以同时支持网络输入与输出间复杂的多级连接，它在并行分 布式处理器结构和高速电信交换方面占据极其重要的地位。由于多级互连网有可 能在任意网络输入和输出之间提供无死锁路由和公平通信，作为并行机和高速交 换设备的关键部分，多级互连网已经受到越来越多的关注。同时，组播通信作为 并行应用中的重要通信模式，快速实现组播通信将有效地降低类似应用的执行时 间，如何利用多级互连网来实现多播通信已变成了一个重要的课题。 本文探讨如何在多级互连网中应用硬件来支持复杂的组播通信，无阻塞的支 持和实现会议组通信。并给出两种实现会议组通信的多级互连网络结构： c l o s t y p e 嘶1 6 o m e g a 网。 1 1 会议通信简介 本文主要讨论的会议通信是组播通信的一个重要类型【2 】，在一个会议中，任 意一个或多个成员可以并发的广播消息给会议组内的其它成员。会议的成员称为 会议者，一个会议的会议者的最大数量称为会议的规模，一般的对于一个会议需 要先确定其一定的规模，然后在会议功能网络里按照该规模建立会议连接，在会 议者数量不超过会议规模的情况下，会议者可以在任意时刻加入或离开会议。 会议网络在实现时要能支持并发的多个不同规模的会议，每个会议可以由会 议网络的任意端口( 成员) 组成，但是会议网络的任一成员在同一时刻只被允许 加入至多一个会议。 会议网络适合多个要求实时有效的组通信应用方面，常见的有一组人之间的 音频视频会议通信；并行分布计算系统里多个要求协作的处理器之间的通信， 会议网络还可以应用到要求文本，图像，声音和视频信息传输的多媒体会议，在 第一章绪论 多媒体会议中允许多个成员对图文文件协作处理。 1 2 互连网多播通信已有的研究成果 二十世纪以来，硬件支持多播通信方面已经有不少的研究成果出现，c l o s 网是一类著名无阻塞网络，在目前的研究中，三级c l o s t y p e 网上的无阻塞置 换，单对多播送的充分必要条件以及相应的路由策略和路由算法都已经在相关 文献中得出。y a n g 和m a s s o n 2 0 j 论述了在- n 多播送中，在一定的路由策略下 要实现无阻塞所需要的充分条件是中间级数目m 满足m o ( n l o g r l o g l o g r ) ， 并且在他们的路由策略和路由算法下，算法的时间复杂度为o ( ) ，同时作者还 用串行的算法实现了多源点多播，算法时间复杂度为o ( n g ) 。h w a n g 和l i a w 瞄l j 提出了f 2 e a s t 三级c l o s 网络严格非阻塞的充要条件是： m = m i n ( n 1 1 m + 吃，( 川一1 ) 石+ 1 ，n 2 。y a n g 提出了一种能对任意多播指派提 供更好q o s 性能的新型广义非阻塞多播网络【2 2 】。这种新型网络可以广义非阻塞 地实现任意k f o l d 多播指派。所谓k - f o l d 多播指派是指任何一个目的端口最多 可以同时被k 个不同的多播连接共享。这类k f o l d 多播网络可以划算地支持任 意的k f o l d 多播通信，并且可以减少通信延迟，降低外部阻塞和丢包率，从而 更好地满足各种各样的多播应用需求。对于偶数级的c l o s 网络，y a n g 研究了 基础的四级c l o s 广义无阻塞网络【2 3 1 ，其无阻塞实现多播的条件为中间级开关数 目嘲= m 2 = l l + 4 2 n ，与一般的三级c l o s 相比降低了硬件代价的量级。 较小规模下c l o s 网可以很好的低延迟无阻塞的实现多播通信，但是目前 c l o s 支持无阻塞多播最小的硬件代价对于大规模的多播通信而言仍然是实践中 难以承受的。 大规模时可行的支持多播的多级互连网络中，典型的是对0 m g e a 网络加以改 造而成的多o m e g a 结构。文献【2 4 】提出的多- o m e g a 网络采用二进制寻路法自路由无 阻塞实现多播，硬件代价为o ( n l 0 9 2 ) ，路由时间为o ( 1 0 9 2n ) ：文献【2 5 】提出 s - 0 m e g a 网络，通过重排各级开关的状态，并发的实现任意的多源点多播，所需 开关元件总数为5 2 n l o g n ，多播路由时间复杂度能达到o ( n l o g n ) ；文献【2 6 l 在5 一o m e g a 网络的基础上提出3 - 0 m e g a 网同样可以无阻塞实现任意的多源点多播， 硬件复杂度为o ( nl o gn ) ，路由时间为o ( nl o gn ) 。 根据c l a u d es h a n n o n 2 7 】理 论知道，上述5 0 m e g a n 络和3 - 0 m e g a 网络硬件复杂度o ( n l o g ) 均达到交换网络 的理论下限。 关于会议网络的已有网络结构有：有序环【3 】，超立方【4 】，r 维网孔【5 】等，这 样的结构大都存在通信延迟不致，硬件拓扑不易扩展等不足。y a n g 先是通过 2 第一章绪论 增加交叉开关的功能和增加多余链路提出了附a n - 进制立方网络的c c n 结构【o j ， 又通过分析o m e g a 上会议网络的最大冲突度，提出了基于o m e g a 的3 倍链路冗余链 路的c c n 结构1 2 j ，很好的利用了o m e g a 网络的规则性及其上的通信特点，但是组 成两种结构的基本开关元件都较复杂，不易具体实现和扩展。 在已有研究的基础上，设计接近或者达到最优时间复杂度和最优硬件代价的 支持会议组通信的会议网络，同时保证网络结构整体规则对称易扩展实现，是一 个非常重要的研究课题 1 3 本文的研究内容和组织思路 本文主要探讨和研究在多级互连网上无阻塞实现会议组播通信的情况，并 在研究c l o s 网无阻塞多播的基础上，设计出实现小规模会议组通信的网络；为 了达到无阻塞会议通信多级互连网络的最优硬件代价和最优时间复杂度，具体 研究了o m e g a 网上实现会议组通信的情况，结合会议组通信的特点，设计出支 持超大容量交换的6 - o m e g a 会议网络，得到香农分析的理论下限的复杂度。 本文将给出的c l o s 类型网络上会议组通信的实现，是以c l o s 网对任意多 播无阻塞支持为基础的，无阻塞c l o s 网以具有全交叉网络的无阻塞性能著称， 同时相对全交叉开关网络又有效降低了硬件代价。虽然c l o s 类网随着通信规模 n 的增长仍不能很好的支持多播通信，但其较小规模下良好的性能无疑是实现 会议组通信的良好选择。 利用o m e g a 复制网【2 副上受限多播可以并发的性质，相对应的扩展开关元件 具备汇集功能，使单个o m e g a 。1 网络变成无阻塞支持受限规约通信的汇集网， 能够很好的完成信息收集。然后根据每个会议组内的会议通信可以逻辑的分为 规约和广播两个阶段的特点，串接o m e g a 。汇集网络和o m e g a 复制网络得到一 个2 - o m e g a 的网络结构来支持受限的会议多播通信，进而通过在2 o m e g a 结构 的两端加置换网络( o m e g a + o m e g a ) 构造出新型的6 - o m e g a 结构的会议网络，新 型的会议网络的硬件复杂度为o ( n l o g n ) ，路由时间为o ( n l o g n ) ，传输延迟为 o ( 1 0 9 n ) ，达到香农交换网络复杂度的理论下限。 本文在多级互连网上应用硬件实现会议组通信的研究成果，无论在方法上 还是结果上相对于已有的会议网络结构都有一定的优势和创新。所构造网络的 设计与实现都具有很好的通用性，对于进一步研究并发多播通信在多级互连网 上尤其是会议组播通信在o m e g a 网结构上的实现具有积极的意义。基于 6 - o m e g a 的会议网络硬件元件简单，网络结构更加规则且具有更好的整体对称 性，所以具有良好的应用前景。 第一章绪论 1 4 本文组织结构 本文分为六章，各章节的内容安排如下： 第一章，绪论：介绍研究课题的内容和研究意义，简述会议组通信和会议 网络，介绍国内外研究现状，并给出本文的章节安排。 第二章，多级互连网概述：介绍多级互连网和传输交换技术，多级互连网 结构和阻塞条件，给出c l o s 网，b e n e s 网和o m e g a 类网络结构，为本文工作的 展开做基本的准备工作。 第三章，c l o s 网上会议组播通信的实现：研究c l o s 网上无阻塞组播通信的 特点，并将结论推广到会议组播通信，得到三级c l o s 网络上会议组通信低延迟 无阻塞的实现的相关结论。 第四章，2 - o m e g a 结构c c n 的设计与分析：研究分析了o m e g a 复制网和 o m e g a 1 汇集网、介绍构造会议网络的一个重要策略，根据会议通信的特点， 设计构造出2 - o m e g a 结构的c c n 会议组成网络，。 第五章，6 - o m e g a 网上无阻塞会议通信的实现：在第四章构造的2 - o m e g a 结构的g b c c n 结构的基础上，进一步研究分析了o m e g a 串接结构可重排的特 性，进而按照三明治构造策略【2 】构造了实现无阻塞会议通信的6 - o m e g a 会议网 络，并分析其复杂性。 第六章，总结与展望：总结本文的主要工作、贡献；f d c t j 新点，并展望下一 步的研究工作。 最后列出参考文献等相关内容。 4 第二章多级互连网概述 数据只需穿过网络一次就可以到达目的地的中间互连网络结构称为多级互 连网络【2 8 1 。多级互连网是并行分布式系统中的一种互连网络结构，能够有效的实 现系统内部处理器等功能部件之间相互的通信，是系统构成的主要组成部分，对 并行处理机的性能影响很大。这一章主要介绍多级互连网的概念、结构和分类等 基础背景知识，并给出交叉开关网络、c l o s 网并0 b e n e s 网以及o m e g a 等价类网络 的相关讨论，引出本文构造会议通信网络的思想出发点。 2 1 互连网络及其分类 互连网络是由开关元件按照一定的拓扑结构和控制方式构成的网络，常用 来实现并行系统内部多个处理机或多个功能部件之间的相互连接【2 8 】，如图2 1 为 互连网络在多处理机系统中的功能模型。 图2 1 互连网络功能模型矧 互连网络有三大要素【2 8 】：即节点间互连拓扑( 包括连接模式) 、开关元件和 控制方式。这三种要素的不同，决定了互连网络的不同。从几何形状看，互连 网络可分为规则网和不规则网两大类，其中规则网又分为静态互连网和动态互 连网两种。 静态互连网又称直接互连网【2 8 】，组成结点是直接相连的，并且保持不变的。 常见的环形网( r i n g ) 、网格形网络( m e s h ) 和立方体网络( c u b e ) z q 都属于静态网。 这种网络一旦构成就固定不变了，比较适合于构成通信模式可预测的并行处理 系统和分布式计算机系统。 第二章多级互连网概述 动态互连网又称间接互连网【2 8 】，是为了达到多用或通用的目的，根据程序 要求实现各种通信模式的互连网络，常用于共享存储器和分布式存储器多处理 机系统中。在动态互连网络中，各结点之间不是直接固定连接的，而是在控制 信号的作用下，通过网络开关的设置来建立结点之间间接的、可变的连接通路。 这种连接通路是主动可扩的，常以一个独立部件的形式出现。动态互连网络按 输入端和输出端的布置可分为单边和双边；按连接能力可分为非阻塞、可重排 非阻塞和阻塞网络；按输入端数相比输出端数的大小关系又可分为连接器( 相 等) 、集中器( 大于) 和扩展器( 小于) 。按动态互连网络拓扑划分可分为单 级互连网和多级互连网。单级互连网则是由一级开关元件与构成一种连接模式 的线路连接而成的，只能实现有限的集中基本连接。顾名思义，多级互连网就 是把多套相同的或者不同的单级互连网串联起来，从而实现更多的连接模式。 2 2 多级互连网 本文所涉及的多级互连网络，指的是具有开关连接系统和互连网络组合特性 的多级互连网汹1 ，即在空间上重复设置多套单级互连网，单级网络之间采用固 定的连接模式串联，通过动态设置各级开关的状态来实现输人输出结点之间的连 接。对多级互连网络我们主要考察其以下三个方面：开关元件、网络拓扑和控制 结构，并对多级互连网络的阻塞特性进行研究分析。 2 2 1 多级互连网开关元件和连接 多级互连网络的动态性反映在其硬件基本构件开关元件上，每个开关有两 个输入连接：厶，五和两个输出连接；d ，q ( 图2 2 ) 。 6 二：二旺0 图2 2 开关元件 开关元件内的基本交换有四种状态：直通，交换，上播，下播( 图2 3 ) ： 二巨二匠二匣二艮 ( a ) 直通( b ) 交换( c ) 上播( d ) 下播 第二章多级互连网概述 4 个开关元件间的连接有两种：直通连接和蝶式连接( 图2 4 ) 。由于从输入 到输出的每个置换都只能有一条单独的路径，因此总的交换对数目41 ，图2 4 ( a ) 的简单蝶式连接情况下，能够实现的置换有8 种，很容易看出简单蝶式连接情况 下，不能实现所有的置换。例如，输入端l ，2 不能同时与输出端1 ，2 相连接。而 图2 4 ( b ) 的直通连接条件下，则只能实现4 种可能的置换。 i 2 踢i s e , z s g , i 踞2 ：j 二仁爿二工 s e , i踞2 ( a ) 简单蝶式连接( b ) 直通连接 图2 4 开关元件之间的连接模式 2 2 2 多级互连网网络拓扑和控制策略 设x 。为带m 个输入n 个输出的多级互连网络，其任意一个输入可以连接 到所有的输出，且任意一个输出也可以连接到所有的输入。假定网络内每个输 心出端口都可同时为某一个交换所使用，在同一网络内的两个交换不能同时 分享同一条连接。若有竞争，则引起冲突和拥塞。 由输入开始，穿过一条或多条连接链路并终结于输出端路径成为路由。构 造多级互连网络最需要考虑的就是路由时间复杂度。从输入端口到输出端口的 一条最短路径上的连接数量或者最短路径上的开关元件的数目定义为网络深 度。网络的深度与网络的硬件复杂度紧密相关。 多级互连网中有两个非常重要的时间参数口邵： 1 ) 网络的设置时间：即为了建立所希望的连接控制接通或者断开开关元件 所需要的时间。 2 ) 选路时间；即传输数据从输入到输出所需要的延迟时间。 二者决定了多级互连网的速度和传输效果，是我们构建多级互连网络时所 要着重考虑的关键问题。 多级互连网络的控制策略【2 8 】是指对网络中各交换开关的控制方法，通过控 制结构设置开关元件的连接状态。多级互连网一般有三种控制策略：级控制、 开关元件单元控制和介于二者之间的部分级控制。级控制要求m = l o g 个控制 信号；单元控制需要n 2 l o g 个控制信号。在实际应用中两种控制策略的折衷 7 第二章多级互连网概述 选取，就是部分级控制即所谓的“混合控制策略”。 控制的真正含义是地址映射的选路方法。在实际路由控制中，标志位控制 法最为常见，通常有以下两种方法【2 s 】： 1 ) 研究目的地址标志位来决定开关元件的设置； 2 ) 按照源地址和目的地址按位0 操作所形成的标志位来决定开关元件的 设置。 标志位控制法又可分为内置标志和外置标志。无论是内置标志还是外置标 志，到达的信元都带有数据标志作为指明路径的路由信息。有的交换基于输入 端口创造一个内置标志，内置标志为一连串的数位，代表向出口传递所要经过 的不同的层数。内置标志的位数为网络的层数，采用2 2 基本开关元件构造的 网络结构的层数，通常为玎= l o g n 。外置标志则带有路由交换表，结点从路由 交换表中查到并给出输出端1 2 1 。本文采用内置二迸制目的地址标志位的路由控 制方法，它根据所收到的信息位串头部的目的地址标志位来决定路由走向。 2 2 3 多级互连网络的阻塞特性 多级互连网络分为阻塞网和无阻塞网。 在阻塞网中，任意的输入终端都可与任意的输出终端相连接，反之亦然， 但是同时将两个或更多的输入输出相对连接时又可能会产生冲突。阻塞网l r 2 驯包 括b a s e l i n e 网、b a n y a n 网、f l i p 网、s o r t i n g 网、b i n a r yn c u b e 网络、d e l t a 网、 d a t am a n i p u l a t e 网、g a m m a 网、o m e g a 网等等，其中o m e g a 网是最常被人们 研究的阻塞网络，以b a s e l i n e 网为基准网络与众多阻塞网络功能等价。阻塞网 不能保证实现所有的置换。 无阻塞多级互连网有c l o s 网和b e n e s 网。无阻塞网做任意的连接时均不会 导致阻塞。无阻塞多级互连网的无阻塞特性分为三类【2 o 】：1 ) 严格无阻塞性； 2 ) 广义无阻塞性；3 ) 可重排无阻塞性。 严格无阻塞指：指不管网络处于什么状态。总有可能连接自由的终端对而 不扰乱网络中已经建立的连接。广义的无阻塞网指：指在存在阻塞状态的网络 中存在一种规则，按照此规则可连接任意新的终端对而不产生阻塞。可重排无 阻塞的网络则指能够通过重新排列现有连接建立任意新的终端对的网络。 由于严格无阻塞网络需要巨大的硬件代价，故实际应用价值受限。因此， 我们设计多级互连网时的主要考虑对象是广义无阻塞网和可重排无阻塞网。通 过好的算法或重排交换元件的设置来实现无阻塞。 v b e n e s t 2 嚣j 研究证明，用三级c l o s 网的逻辑构造思想来组建无阻塞的b e n e s 网，其所有输入输出间的连接都可以得到实现。v b e n e s 还证明，通过将阻塞 第二章多级互连网概述 的基本多级网如o m e g a 等价类网背靠背连接组成的2 l o g n 层网络，也可以达成 网络的无阻塞特性。o m e g a x o m e g a d 网和o m e g a + o m e g a 网便是典型的代表， 它可以在一定的构造规则条件下通过重排现有连接而满足任一新的连接请求， 其传输延迟秉承网络的层次数为o ( 1 0 9 ) 。 无阻塞网很受关注，然而无阻塞又是昂贵的，特别是在复杂多播或组播通 信传送的情况下。比较可行的是在阻塞网络中实现无阻塞特性，即可以在阻塞 网络中将连接阻塞的可能性控制在相当低的范围内，大大降低网络的总的连接 代价。t e dh s z y m a n s k i 3 l 】证明了可将阻塞状态的间隔时间控制在1 0 5 0 以下，即 令阻塞在地球存续时间内都无法发现，从而使阻塞网络获得无阻塞能力将阻塞 网变身为无阻塞网。张【2 6 】所提出的3 - o m e g a 多播网就是采用这种思路。 本文将在小规模情况下采用提供更好服务的无阻塞网，而在大规模下采用 基于阻塞网构造的无阻塞网来设计支持会议通信的会议网络。 2 3 典型互连网络简介 作为本文研究课题的基础，这节简单介绍几个典型的动态互连网络：交叉 开关网，c l o s 网$ 1 b e n e s 网，o m e g a 等价类网。 2 3 1 交叉开关网 这里之所以对交叉网络进行讨论，是因为1 2 8 】：( 1 ) 它是最基本、最直截了 当、连接功能最强、也是最早使用的开关连接网络；( 2 ) 它是各种多级网络( 如 c l o s 网络) 的基础，由它可发展出一大类称之为交叉开关型的互连网络： ( 3 ) 它的基本参数，交叉点数和延迟时间，将是各种多级开关网络的比较尺度。 最原始的交叉网络是一种单级的开关互连网络，在拓扑结构上排成方形或 矩形的二维阵列，分别称之为方形交叉开关和矩形交叉开关，如图2 5 。 ，翮矾n 、 图2 5 方形或矩形交叉开关的阵列形式。 从图论的角度，一个交叉开关就是一个全连接的图，所以交叉开关也可以 9 第二章多级互连网概述 表示成图，图2 6 给出4 x 4 的交叉开关及其全连接图的表示。 输 入 o 输1 x , 2 ol2 3 输出3 图2 6 交叉开关的全连接图表示 0 1 输 1 出 二 3 全连接交叉开关【2 8 】是开关网络最一般的形式，是最严格意义下的非阻塞开 关网络。因为每一个输入输出组合对都对应着一个单独的开关触点对。这种开 关具有真正均匀的单位延迟时间，而且由于从任何给定的输入到输出的通路上 只有一个开关元件，所以开关设置的控制方法极其简单。不过全连接交叉开关 的良好性能是以高的网络成本o ( n 2 ) 作代价的，并且没有充分利用这样高度的 硬件成本，全连接的交叉开关能够提供的网络内部状态总数为2 ，但是n 个输入到n 个输出映射的所有状态数目为! ，远小于硬件成本所能提供的性 能。 因此，在全交叉开关的基础上需要在得到同样性能的情况下降低硬件代价 来发展设计其它类别的互连网络。 2 3 20 i o s 网和b e n e s 网 c c l o s p 2 在十九世纪五十年代提出了一系列三层交换网络，通称为c l o s 网络。研究最多的c l o s 类网络为如图2 7 所示的n 输入n 输出端非阻塞网络， 网络的两边是对称的m x ，z 或n x m 的矩形交叉开关，中间是t - x g 的方形交叉开 关。交叉开关的每个输出均连向下一级每个交叉开关的一个输入，因此对于任 何的输入输出对之间均可能存在着一条通过中间级开关的路径。网络参数m ， n ，r 为整数，决定了开关的维数，此类网络通常记之为c ( m ，疗，) 。 1 0 栉x m ，r 图2 7 三级c l o s 网络 第二章多级互连网概述 令s 表示c i o s 网络的级数，c ( s ) 表示s 级开关总的交叉点数目假定疗= n “2 则三级c l o s 网络所需总交叉点数可表示为：c ( 3 ) = ( 2 n 2 一1 ) ( 3 ) = 6 n 3 彪一3 n ， 小于交叉开关2 的硬件代价。 c c l o s 强】实际构造了一个如图2 8 所示的n = 3 6 的三级非阻塞网络。其中输 入级有6 个6 l l 的矩形交叉开关，中间级有1 1 个6 6 的方形交叉开关，输 出级有6 个l lx6 的矩形交叉开关。总共使用了小于3 6 2 的l1 8 8 个交叉点数。 6 l1 6x6 ll 6 图2 8 三级c l o s 网络c ( 1l ，6 ，6 ) p 2 l c c l o s 3 2 1 已经证明：对于实现一到一置换的多级网络c ( m ，刀，) ，如果满足 条件m 2 n l ，则它是严格的非阻塞网络；如果满足条件m i3 n 2i ，则它就 是广义的非阻塞网络。a d u g u i d 3 3 1 和d s i e p i a n 3 4 1 根据p h a l l 3 5 1 的组合理论，采 用归纳法证明了：当且仅当m 刀时c ( m ，n ，r ) 是一种可重排的非阻塞网络。 对于c ( m ，) ，如果令n = 2 ，m = n = 2 ，则，= n 2 = 2 卜1 ，得到一类特殊 的c l o s 网络表示为c ( 2 ，2 ，2 卜1 ) 。对于形如c ( 2 ，2 ，2 卜1 ) 的c l o s 网络，我们可以使 用递归构造原理，逐次化为c ( 2 ，2 ，2 卜2 ) ，c ( 2 ，2 ，2 闰) ，一直到c ( 2 ，2 ，2 ) 网 络为止。此时得到一个2 2 基本开关单元的多级网络，此种网络通常称为b e n e s 二进制网络【3 6 】。由于他是由m = n 的c l o s 网络递归构造而成，因此它属于可重 排的非阻塞网络。 b e n e s 2 8 】网络有2 1 0 9 n 一1 级开关，每级有n 2 个开关单元，总共有 n l o g n n 2 个开关单元，交叉点个数为2 n l o g n n ，与香农的理论极限非常 接近。设k = l o g ，则b e n e s 可记为b ( k ) 。其实对于任意的b e n e s 网络b ( k ) 递归构造过程，都可以看作由一级n 2 个开关单元，继以两个同类型的b ( k 一1 ) ， 然后再附加一级n 2 个开关单元组成如图2 9 。 第二章多级互连网概述 图2 9b ( k ) 的递归构造 n 同时b e n e s t 2 8 】还证明了可以由基本的阻塞网络背对背连接( 如o m e g a 与 o m e g a 的串接) 构成可重排的非阻塞b e n e s 网络。借鉴b e n e s 网循环重构的思想， 可以用阻塞网络作基础网络，加以改造得到硬件代价达到香农理论下限的网络 结构，是现在非常有意义的研究课题。本文会议网络两端的用来实现会议成员 一般分布到满足一定约束分布的置换网络，可以按照这种思想构造而成。 2 3 3o m e g a 等价类阻塞网 o m e g a 网络t 2 8 】实际上是一种多级洗牌交换网络。它由n = l o g n 级单级洗牌交 换网络组成， o m e g a 网络的每级开关n 2 个，整个网络的开关是n l o g n 2 个，如 图2 1 0 所示为8 8 的o m e g a n 络结构。 输 入 端 图2 1 0n = 8 的o m e g a n 络 输 出 端 o m e g a 网是一种阻塞网，一对以上输入端和输出端可同时实现连接，但是 网络中有可能出现路径冲突，不能实现全部的函数置换。由于所用开关少，延 1 2 第二章多级互连网概述 时也不长，路径控制比较简单，又能实现并行处理中许多常用的置换函数，二 次通过可以构成可重排的非阻塞网络，实现任意的置换，所以实际系统中使用 广泛。 o m e g a 等价的阻塞网络【2 8 】包括( 逆) 基准网络，( 逆) b a n y a n 网络，( 逆) 间接二 进制立方体网络、( 逆) 简化数据变换网络、( 逆) s t a r a n 网络、( 逆) f = s 一2 的s w 榕树网络以及逆o m e g a 网络等。这些网络虽然在结构上所用的开关模式、互连 函数和控制方式各不相同，但是有它们具有拓扑等价关系，即对于其中的一个 网络，存在一个逻辑名结构使得它带有逻辑名的连线关系可以用另一个网络的 拓扑描述规则来描述。所谓的拓扑描述规则是指，描述不同级开关元件之间连 接模式的一组数据规则。拓扑描述规则可以从网络的具体结构直接导出。在拓 扑同构网络之间，可通过重新逻辑命名网络输入、输出端，使得一种网络的连 接能力完全等价于另一种网络。为了研究这类网络的拓扑关系，w u 并1 3 f e n g 3 7 1 3 8 】 引入了一个基准网络( b a s e l i n e 网络) ，如果每种网络与这个b a s e l i n e 网是拓扑同构 的，那么他们互相之间也是拓扑等价的。如图2 1 1 为o m e g a 等价网络相对b a s e l i n e 网络逻辑命名后的等价一致性情况。 b a s e l i n e o m e g a 图2 1 l 重新配置逻辑名的o m e g a 网络 b a s e l i n e 网络也可以用递归方法生成 3 7 , 3 9 】，如图2 1 2 它表示第一次迭代，将 n n 网络分为一级n 2 个2 2 基本开关单元，继以两个同类型的n 2 xn 2 规 模的网络子块g 和g ：第二次迭代再将c 0 和q 各分为n 4 个2 2 的基本单元块 和n 4 x n l 4 的网络子块，递归至每个网络子块为2 x 2 的基本开关单元。总的 迭代次数为l o g n l ，得到的b a s e l i n e 网络的开关级数为l o g n ，连线级数为 l o g n + l 。 根据b e n e s l 2 8 】网络的递归生成方法可以知道，b a s e l i n e 阻塞网络的生成过程 中，每次迭代l l ：b e n e s 网络每次迭代少一级基本的开关单元块，递归生成整个网 络时，生成的b a s e l i n e 网络相当于b e n e s 网络的一半网络结构。可以考虑将两个 b a s e l i n e 网络对接或两次通过b a s e l i n e 网络来构造等价的b e n e s 网络。如图2 1 3 令 逆b a s e l i n e 的最左列开关处于直送状态，, $ 1 j b a s e l i n e 网络与逆b a s e l i n e 网络相连接 便合成了可重排无阻塞的b e n e s 网络，于是合成网络的输入、输出间的任意置换 都可以实现。由于b a s e l i n e 网络与逆b a s e l i n e 网络拓扑等价，因此，二次通过 b a s e l i n e 网与第一次通过b a s e l i n e 网和第二次通过逆b a s e l i n e 网也是等价的。于是 可以得到基准网络b a s e l i n e 网的一个重要的性质【2 8 1 ，即二次通过基准网络能实现 任意的置换。 图2 1 2b a s e li n e 的递归构造过程 图2 1 3 二次次通过b a s e l i n e 网络等价b e n e s 网络 o m e g a 与b a s e l i n e 网络等价，因此也具有上述性质，即二次通过o m e g a 网 络或将两个o m e g a 类网络通过某种方式串接功能等价于b e n e s 网络。 这说明了b e n e s 网络的递归构造思想是可以运用在o m e g a 等价类网络上 的，提供t 幂u f f jo m e g a 基础网络构造无阻塞网的一种研究策略。 1 4 第二章多级互连网概述 2 4 小结 本章介绍了多级互连网络的概念，对多级互连网络的开关元件和连接、多 级互连网络的拓扑、控制策略以及阻塞特性等都做了系统性的说明。并给出了 几种基本多级互连网络类型交叉开关网络、c l o s 网络和b e n e s 网络、o