（应用数学专业论文）多级互连网络的结构、算法和可重排性.pdf

一 上海交通大学博士学位论文 多级互连网络的结构、算法 和可重排性 摘要 多级互连网络在并行计算等许多实际问题中有着重要的应用，它对 系统的软硬件性能都有很大影响。位变换网络是一类结构良好、而且包 含绝大部分在文献中得到深入研究的多级网络，本文着重对这类网络的 结构、路由算法和可重排性进行较系统的探讨。 在第一章对背景和问题作了简单的介绍后，我们在第二章给出位变 换网络的一个完全基于图论术语的刻划，这一结果将b e r m o n d 等人针对单 一网络的结论推广到所有的位变换网络，将对多级网络结构的了解大大 推进了一步，并且澄清了一些对位变换网络结构的模糊认识。 多级网络的分层叉积是e v e n 等人引进的一个较新的概念，它不仅是 研究网络结构的一个有力的工具，而且对于路由算法设计有着广泛的应 用前景。第三章我们给出位变换网络分解为一些“均匀”因子的结果，该 结果使得我们在第四章成功地将置换路由问题转化为一类特殊的矩阵问 题。这一转化将l i n i a l 等人关于洗牌交换网络的一个结论推广到所有位变 换网络，并且由此得到可重排网络的一个必要条件，部分解释了为什么 许多已有的工作对2 n 一1 级网络的关注。 第五章专门讨论2 几一1 级网络的可重排性。这一领域最重要的问题 之一就是b e n e 1 9 7 5 年提出的一个猜想，我们将这一猜想放到一个更广泛 的问题中，并对它作了较多的讨论。特别地，我们给出了包含b e n e 猜想 在内的一类可重排性问题一个新颖的数学描述。我们还着重对c a m 关于 上海交通大学博士学位论文 这一猜想的证明作了深入分析，简化了他的方法，并指出他的证明是不 完全的。 随着相关科学技术的进步，越来越多的研究兴趣集中到光信息在多 级网络中的传输问题上来。我们在第六章证明了位变换网络中的光信息 传输问题在理论上与传统的电多级网络是等价的，从而说明已有的理论 并不过时。在正式给出无干扰可重排性的定义后，我们建立了它与电网 络中的可重排性问题之间的关系，并证明d i l a t e db e n e 网络是级数最少的 无干扰可重排网络。 关键词多级互连网络，位变换网络，洗牌交换网络，分层叉积，平 衡矩阵，置换，路由，可重排性，b e n e 猜想，光多级互连网络，无干扰 d o c t o r a ld i s s e r t a t i o no fs h a n g h a iji a o t o n gu n i v e r s i t y m u l t i s t a g ei n t e r c o n n e c t l 0 nn e t w o r k s ： s t r u c t u r e a l g o r i t h m sa n d r e a r r a n g e a b i l i t y a b s t r a c t 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 kh a si m p o r t a n ta p p l i c a t i o n si np a r a u e lp r o c e s s i n ga n da l s oi nm a n yo t h e rp r a ( 扎i c a ls i t u a t i o n s i th a sa ni n n u e n c ei l o to n l yo nt h e h a r d w a r ea r c h i t e c t u r eb u ta l s oo nt h en a t u r eo ft h es y s t e ms o f t w a r e b i tp e r m u t a t i o nn e t w o r ki sac l l s so fw e l l 一s t r u c t u r e dn e 七w o r k sw h i c hi n c l u d e sm o s to ft h e i n 七e n s i v e l ys t u d i e dm u l 七i s t a g en e 七w o r k si nt h el i t e r a t u r e t h i st h e s i sf b c u s e so na s y s t e m a t i ca n a l y s i so ft h es t r u c t l l r e ，a l g o r i t h m sa n dr e a r r a n g e a b i l i t yo ft h i sc l a s so f n e t w o r k s a f t e rab r i e fi n t r o d u c t j o nt ot h eb a c k g r o u n da n di t sp r o b l e m si nc h a p t e r1 ， w ep r e s e n ti nc h a p t e r2ac h a r a c t e r i z a t i o no fb i tp e r m u t a t i o nn e t w o r k sw h i c hu s e s o n l yg r a p h t h e o r e t i c a lt e r m s t h er e s u l te x t e n d sat h e o r e mb yb e r m o n de ta 1 f r o m s i n g l en e t w o r kt oa l lb i tp e r m u t a t i o nn e t w o r k s i ta d d sm u c ht ot h ek n o w l e d g e o fn e t w o r ks t r u c t u r e ，a n dh e l p s 七oc l a r i f ys o m ei s s u e so nt h eu n d e r s t a n d i n go fb i t p e r m u t a t i o nn e t w o r k s l a y e r e dc r o s sp r o d u c to fm l l l t i s t a g ei n 七e r c o n n e c t i o nn e t w _ o r k si sar e c e n tc o n c e p t i n t r o d u c e db ye v e ne ta 1 i ti sau s e f u lt o o lf 6 rs t u d y i n gt h es t r u c t u r eo fn e t w o r k s ， a n do p e n su pb r o a dp r o s p e c t sf b ra ，p p l i c a t i o ni nt h ed e s i g no fr o u t i n ga l g o r i t h m s i n c h a p t e r3 ，w eg i v ead e c o m p o s i t i o no fb i tp e r m u t a t i o nn e t w o r k si n t oan u m b e ro f “u n i f o r m f a c t o r s ，w h i c hl e a d st oas u c c e s s f u lt r a n s f o r m a t i o no fp e r m u t a t i o nr o u t i n g i n t oas p e c i a lk i n do fm a t r i xp r o b l e m si nc h a p t e r4 t h i sr e s u l tg e n e r a l i z e saw o r k b yl i n i a le ta 1 f t o l ns l l u f 】! l e e x ( ：h a r l g ei l e t w o r k st oa l lb i tp e r i n u t a t i o i li l e t w o r k s b a s e do nt h er e s u l t ，w ed e r i v ea ，n e c e s s a r yc o n d i t i o nf 6 rab i tp e r m u t a 乞i o nn e t w o r k t ob er e a r r a n g e a b l e ，w h i c he x p i a j n si np a r tt h es p o n t a n e o u si n t e r e s to fr e s e a r c h e r s i nt h er e a r r a n g e a b i l i t yo f ( 2 札一1 ) 一s t a g en e t w o r k s c h a p t e r5i sd e v o t e dt ot h ei e a r r a n g e a b i l i t yo f ( 2 n 1 ) 一s t a g en e t w o r k s 0 n e o ft h em o s ti m p o r t a r l tp r o b l e m si nt h i sf i e l di sac 0 1 1 j e ( ：t l l r em a ( i eb yb e n ( i n1 9 7 5 w e p u tt h i sc o l l j e c t u r ei n t oab r o a d e rp r o b l e m a n dd i s c u s si tt os o m ee x t e n t i np a r t i c u l a r ，w ep r e s e n tan o v e lm a t h e m a t i c a lf o r m u l a t i o nf o rac l a s so fr e a r r a n g e a b i l i t y p r o b l e l n sw h i c hi n c l u d e sb e n e 蓉c o i l j e c t u r ea sas p e c i a lc a s e f u r t h e h i l o r e ：w eg i v ea ， 1 1 1 d o c t o r a ld i s s e r t a t i o no fs h a n g h 越j i a o t o n gu n i v e r s i t y d e t a i l e da n a l y s i st oc a l n sp r o o fo ft h ec o n j e c t u r e a f t e rs u b s t a n t i a l l ys i m p l i f y i n g h i sm e t h o d ，w ep o i n to u tt h ei n c o m p l e t e n e s so ft h ep r o o f w i t ht h ea d v a n c e m e n to fs c i e n c ea n dt e c h n o l o g yi nr e l a t e da r e a s ，m o r ea n d m o r ei n t e r e s ti sd i v e r t e dt ot h er e s e a r c ho nm 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 c a r r y i n go p t i c a lm e s s a g e s i nc h a p t e r6 ，w ep r o v et h a tt h ep e r m u t a t i o nr o u t i n g p r o b l e mo na no p t i c a lb i tp e r m u t a t i o nn e t w o r ki st h e o r e t i c a l l ye q u i v a l e n tt ot h e c l a s s i c a lp r o b l e mi ne l e c t r i c a ln e t w o r k s ，ar e s u l ts u g g e s t i n gt h a tt h eo l d e rt h e o r yi s n o to u t o f - d a t e a f t e rf b r i i l a l l yd e f i i l i n gc r o s s t a l k f r e er e a r r a n g e a b i l i t y ，、v ee s t a b l i s h i t sr e l a t i o nw i t ht h er e g u l a rc o n c e p to fr e a r r a n g e a 如i l i t y ，a n ds h o wt h a tt h ed i l a t e d b e n e 吾n e t w o r ki sac r o s s t a l k f r e er e a r r a n g c a b l en e t w o r kw i t hm i n i h l u mn u m b c ro f s t a g e s k e yw o r d 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 ，b i tp e r m u t a t i o nn e t w o r k ，s h u m e e x c l l a n g en e t w o r k ，l a y e r e dc r o s sp l o d u c t ，b a l a n c e dm a t r i x ，p e r i n u t a - t i o n ，r o u t i n g ，r e a r r a n g e a b i l i t y ，b e i l e 西c o l l j e c t u r e ，o p t i c a lm u l t i s t a g ei 1 1 t e r c o n n e c t i o n n e t w o r k c r o s s t a l k f t e e 1 v 上海交通大学博士学位论文 n i a i g i ，j c ( g ) j e i 。 又 n s n l ( g ) 己_ 1 ( 日) 易】 g 1 ：g 2 i ( z l z 2 z 。) ( d 1 ，d 2 ，d s ) 符号说明 = 扩，其中他1 ，d 2 ，均为正整数 集合a 的基数 g 从第i 级到第歹级组成的区问子网 g 的连通分支数 阶为的b e l l e 吾网络 阶为的2 咒一l 级沈牌交换网络 = o ，l ，一1 ) 阶对称群 g 的线图 h 的底图 最所在的等价类 g 1 和g 2 的桥接网络 单位平衡矩阵 结点的标号，d 进制数 位变换网络的特征序列 表示映射：( z l z 2 z 。) = z 2 z 。z 1 附件四 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 彩致 日期： 眵j 7 年7 月i b 日 附件五 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于， 不保密瓯 ( 请在以上方框内打“”) 学位论文作者签名：多t 弓k 日期：。r 年月1 1 ，日 指导教师签名： 明 降p 第一章绪论 本文主要研究多级互连网络中的一些理论问题，除了采用相关文献中的一些 术语外，将尽量使用图论的语言，对一些没有直接定义的术语和符号，读者可参 见 1 ，2 】o 1 1多级互连网络 经验表明，一个并行计算机的效能在很大程度上决定于它所使用的连接网络， 即负责在处理器和存储单元问传递信息的部件。连接网络不仅影响着系统的硬件结 构，而且对系统软件( 如操作系统) 也有极大影响。为了实现连接网络，不同的拓扑 结构被提出和研究，其中多级互连网络以其较好的性能和低廉的成本得到广泛的关 注，并被深入研究( 3 7 8 】，可参见文献 3 ，4 】的综述) ，而且在一些实际的系统中得到 应用。 一个多级互连网络的基本元素就是一些2 2 的开关( c r o s s b a r ) ，它可以实现两 个输入口到两个输出口的平行或交叉连接。图l 一1 ( a ) 就是一个带有两个输入和两个 输出的2 2 开关，它可以平行或交叉地连接两对输入输出( 图1 1 ( b ) ) 。一般情况下 可有d d 的开关，其中( f 2 ，一个d d 开关可以实现它的d 个输入口到d 个输出口 的任意置换。本文的网络一般都假定使用( 2 d 的开关，称为d 元网络。 图1 1 ( a ) 2 2 开关；( b ) 开关的两种状态 在一个多级网络中，若干个小开关被安排在一列，构成网络的一个级，一级中 所有开关上的输入( 输出) 的全体构成该级的输入( 输出) ，相邻两级问由连线将 上一级的输出与下一级的输入分别连接起来，这些连线的全体称为一个边级。第一 级的输入( 最后一级的输出) 称为网络的输入( 输出) ，它们将网络连接到外部。本 文假定每一级开关的数目均为扩_ 1 个，从而网络的输入和输出数均为= d ”，称 该多级网络为阶的，也可叫做一个开关( 每个开关都可以作为一个模 1 上海交通大学博士学位论文 块用来构成更大的开关) 。通常d d 开关的输入和输出分别用0 ，1 ，d 一1 这d 个数 进行编号，一级中的全部开关用长度为他一1 的d 进制数编号，一级中的全部输入和 输出用长度为n 的d 进制数编号，这些编号是为便于指定这些元素而采用的，不属于 网络的构成部分。当画出一个网络的图形时，编号一般默认按从小到大的自然顺序 给出。图1 2 ( a ) 和( b ) 是两个阶为8 8 的二元网络，分别是4 级的洗牌交换网络和3 级 的r e v e r s eb a s e l i n e 网络。 ( a ) 图l 一2 ( a ) 洗牌交换网络； ( b ) ( b ) r e v e r s eb a l s e l i n e 网络 网络中的边被看成是有向的，它们总是从低一级指向高一级。当把所有边都反 向时，得到的是原网络的反向网络，如上图中的r e v e r s eb a s e l i n e 网络就是b a s e l i n e 网 络【3 0 】的反向网络。洗牌交换网络【7 6 】的边级的定义是：上一级( 包括网络的输入部 分) 的输出( z ，z 。z n ) 被连接到下一级的输入( z 。z n z l ) ，级数为n 的洗牌交换网 络也称为o m e g a 网络，当把b a s e l i n e 网络最后一级的开关和r v e r s eb a s e l i n e 网络第 一级的开关按序重合起来，得到的就是有名的b e n e 百网络 6 】。下一章将具体介绍一 些常见网络的定义。 1 2 术语和约定 多级网络的最基本功能就是传输信息，给定一个网络的输入输出对，需要在网 络中找到连接这个输入输出对的一条路。一个输入输出对称作网络一个请求，找到 一条路连接它们，就是要在网络中实现这个请求，或给出该请求的路由( r o u t i n g ) 。 在同一时间可能会有多个请求同时出现，要实现它们，就是要找出一组边不相交的 路分别实现每一个请求，这等同于设置网络中相关开关的状态。显然，只需要考虑 最大负荷的请求，即：每个输入都发出一个请求，而每个输出都接收一个请求，此 时共有个连接请求，这可用集合人厂= o ，1 ，一1 ) 上的一个置换来表示，因 此，多级网络中的基本问题就是实现置换的问题。 2 第一章绪论 多级网络的每一个边级实际上是集合人厂上的一个置换，设置一级中所有开关的 状态，也是确定上的一个置换，因此可用下图来表示网络实现置换的过程： ，0e le 2，2 j 一口一口一 e 卜1 1e ：，8 一口一口一o e 1 屹易旺1 艮1k 图1 3 多级网络中实现一个置换 其中s 表示网络的级数， 是由网络结构决定的边级上的置换，勺是由各级中开关状 态决定的嚣换，0 i s ，1 歹s ，其中，o 和 是输入部分和输出部分对应的置 换，它们不一定是恒等置换。一个级中全部开关的所有状态对应一个大小为( d ! ) 等的 子群e ，要在网络中实现一个置换丌，就是要找到置换勺e ，1 歹s ，使得 o e l l e 2 s - 1 e s | s = 雨 此处置换的乘法是按从左到右的次序执行，因此兀= 而e e 以一，e 六就是网络 可以实现的全部置换的集合。例如，设丘为恒等置换，六= ，( 0 i s ) ，其中t 厂为 置换：( z l z 2 z 。) _ ( z 2 z 。z 1 ) ，则图1 3 表示的就是s 级的沈牌交换网络，而 “2 死一1 级的洗牌交换网络可以实现任意置换”这一陈述用式子表示就是：( ，e ) 2 肛1 = 5 ，这里s 表示阶对称群。 两个网络称为是功能等价的，当且仅当它们实现置换的集合相同，一个网络是 可重排的，当且仅当它可以实现全部! 个置换，不是可重排的网络称为阻塞网络。 本文不考虑任何硬件特性，将多级网络中的开关元件一律用结点表示，而将置 换的实现问题直接看作是在网络中寻找边不相交路的问题。另外，显然输入和输出 部分的接线对网络的结构和置换的实现( 或路由) 不产生实质性影响，因此我们在 画图时不画出网络的输入线和输出线，而将第一级的结点和最后一级的结点直接看 作是网络的输入和输出( 此时网络的一个置换中将包含每个输入结点和输出结点多 次，将在适当位置正式定义) 。我们用g ( ，k ，k ；e 。，易，忍一1 ) 表示一个s 级 的网络，其中，k 和e 1 ，易，忍一1 分别表示它的( 结点) 级和边级。两 个s 级网络是拓扑同构的，当且仅当在它们的结点问存在一个保持相邻关系的一一 对应，并且这个对应还保持级的关系，即它将同一级的结点映射到同一级的结点。 注意到多级网络本质上都是有向图，所以多级网络问的同构关系实际上就是普 通有向图间的同构关系。在本文的所有图形中，边的方向都没有标出，因为按照级 3 上海交通大学博士学位论文 增加的方向就可以确定边的方向。实际上，文中除了必须申明网络中的信息是从输 入端传送到输出端外，可以忽略网络中边的方向，在许多地方我们就是将网络看成 普通的( 无向) 图处理的，这么做不影响结果的正确性。显然，同构的网络能实现 的置换个数相同，也即它们有相同的置换实现能力，而且基于一个网络设计的路由 算法可以移植到所有和它同构的网络。正因为如此，本文不区分同构的网络，对于 同构的网络我们只选取一个代表来进行研究，这一点与许多文献中的做法有较大区 别。 串连( c o n c a t e n a t i n g ) 和堆砌( s t a c k i n g ) 是由较小网络构作较大网络常用的手段。 将两个多级网络串连起来就是把第一个网络最后一级的结点与第二个网络第一级 的结点等同起来。在一些文献中，很少具体讲明两级的结点是怎么对应等同的，这 是因为作者总是把这些网络看作是标号网络，即网络中的结点都带有标号，虽然标 号不一定明确给出，但习惯上总是假定标号按照图形画法从上到下( 当网络的级是 从左到右) 或从左到右( 当网络的级是从上到下) 顺序分配，因此第一个网络最后 一级的结点与第二个网络第一级的结点也就是按顺序等同。实际上，一般情况下串 连两个网络是由两级结点间的一个一一映射来确定的，相互对应的结点在串连时被 等同。堆砌两个级数相同的网络就是将它们平行摆放在一起，因此新网络的点级和 边级是原来两个网络的点级和边级的不相交并。 1 3 本文主要工作概述 前面已经介绍，多级网络中的基本问题就是实现置换的问题，研究的内容主要 包括结构、算法和可重排性几个方面。文献中出现较多的多级网络主要有两类，一 类是3 级的c l o s 网络，它使用p g 开关( 开关的输入和输出蜘，g 可以不同) ，通过在 各级选择不同的参数p ，g 来获取不同的网络性能，这类网络在本文中不作研究。另一 类就是本文讨论的位变换网络，它只使用一种对称的( d d ) 开关，这是一类结构良 好而且包含绝大部分得到深入研究的网络。尽管位变换的概念提出较晚，但大部分 得到较多研究的网络都属于这个范围。 结构直接决定网络的性能，对它的研究是不可避免的，早期对多级网络结构的 讨论很少，曾出现同一个网络被多次发现并被赋予不同名称的情况，而且许多研究 都只是局限于少数几类网络，甚至同构但表示方式不同的网络是被分开讨论的，因 此这一领域的研究结果比较零散，一般性的结论极少。将一些重要结论从单一的网 络推广到任意级数s 和任意基数d 的位变换网络是本文主要贡献之一。 4 叠 第_ 章绪论 关于网络的结构讨论主要包含在第二、三章。第二章给出了位变换网络的定义和 一些基本性质，主要证明了关于位变换网络结构的两个刻划( 定理2 2 4 和定理2 2 8 ) ， 这些结果都是基于子网中分支数等图论概念的，它将b e r m o n d 等人关于o m e g a 网络 的结果推广到所有位变换网络。本章还通过实例指出相关文献中的一些错误，这对 于澄清关于位变换网络结构的一些模糊认识是有意义的。第三章从多级网络分层叉 积的角度讨论结构问题，主要结果有定理3 2 1 和定理3 4 1 ，它们分别是后面几章讨 论网络实现置换能力和可重排性问题的基础。 第四、五章研究网络实现置换能力和可重排性问题。第四章推广了平衡矩阵 这一重要概念，并给出任意位变换网络可实现的置换的一个刻划( 定理4 3 4 ) ，这 一结论将许多零星结果都包含进来，并将l i n i a l 等人的关于洗牌交换网络的一个重 要结果推广到所有平衡矩阵。本章还给出了位变换网络可重排的一个必要条件( 定 理4 4 1 和推论4 4 2 ) ，推广l i n i a l 的一个猜想( 猜想4 1 5 ) 并对其作了初步的讨论。第 五章进一步讨论了和这一猜想有关的网络重排性问题，给出了包括b e n e 猜想在内的 一类问题一个纯组合意义的表述( 定理5 5 2 ) ，证明了新的可重排网络( 推论5 2 2 ) ， 综述了b e r l e 猜想的研究现状，并用较多篇幅详细分析了c a i l l 给出的关于b e u e 豆猜想 的新证明，简化了他的方法，并指出他的证明仍是不完全的，从而重申这一猜想没 有得到解决。 第六章讨论光信息在位变换网络中的传输问题。近几年有一种认为电多级网络 已经过时的观点，从而越来越多注意力转向光网络。本章证明了位变换网络一个基 于线图的刻划，并给出了求位变换网络底图的算法，论证了利用位变换网络传输光 信息的问题与经典网络中传输电信息的问题在理论上是等价的，从而解决了这一领 域的一个重要理论问题。本章还首次提出无干扰可重排的概念，建立了它与电网络 中的可重排性的联系，给出了无干扰可重排网络的一些性质和条件。 5 第二章位变换网络的图论刻划 本章给出位变换网络的定义和有关的一些基本结果，重点证明位变换网络的一 个基于它的子网中分支数的一个刻划，有关位变换网络结构的其它结果将在第三章 给出。 2 1 位变换网络的概念 位变换网络( b i tp e r m u t a t i o nn e t w o r k ) 的概念首先由c h a n g ，h w a n g 和t o n g 【4 9 提出，并在一些工作- ： j 得到深入研究 5 0 ，8 4 】，本节我们给出它的定义，并列出一些 常见的位变换网络。 设g = ( ，k ；e ，局，e 一，) 是一个多级网络，其中每个级k 中的结 点都由一个长度为n 一1 的d 进制数( z ，z 2 z 。一。) 标号，其中耽称为这个数的第i 位。 规定一个特殊的符号z 。，它代表集合 0 ，1 ，d 一1 ) 中的一个任意数，也就是，规 定( z 1 耽一1 z o 鼢+ 1 z 。一1 ) 表示d 个结点的集合 ( z 1 z 扣1 。o + 1 z 。一1 ) i z o = o ，1 ，d 一1 ) ，称为一个i 一位组。设仃为集合 o ，1 ，n 一1 ) 上满足条件盯( o ) o 的一 个置换，盯可以按如下方式定义g 的一个边级e ：k 中的一个结点( z l z 。z 。一。) 与且 仅与k + l 中的结点( z 。( 1 ) ，( 2 ) z 。( 。一1 ) ) 相邻接。由于盯( o ) o ，所以z o 必在z 。( 1 ) ，z ，( 2 ) ，z ，f 。一1 1 中出现，因此k 中的一个结点总是与k + 。中的d 个结点相邻，反之亦然。 如果盯( 0 ) = 庇且盯( 七7 ) = 0 ，则在最中，k 中一个七一位组连接到k + 1 中的一个七7 一位 组，最是由一些完全二部图d 的不相交并组成的。 定义2 1 1 设盯1 ，仃2 ，一1 为 o ，1 ，礼一1 ) 上的s 一1 个置换，吼( o ) o ，l i s l 定义网络g ( ( 2 ，n ；盯i ，盯2 ，i 丁。一1 ) 为一个级数为s ，阶为的d 元网 络，其中边级最是由吼定义的，1 i s 一1 。对一个网络g ，若能对其每个级的结 点适当标号后，存在上述的置换使得g = g ( d ，礼；盯1 ，盯2 ，g r s 一1 ) ，则称g 为一个位 变换网络。 在不引起混淆的情况下，直接记定义中的位变换网络为g ( 盯，盯2 ，c r s 一，) 。 用 i 1 ，i 2 ，i 】表示循环置换盯：盯( i 】) = i 2 ，盯( i k 一1 ) = i k ，盯( i ) = i 1 。位变换网路 是一个结构良好，而包括范围较广的网络。事实上，它包含绝大部分得到深入研究 的网络，下面列举其斗- 一些重要的网络： 1 b a s e l i n e ：盯i = 【o ，n 一1 ，司，1 i 几一1 2 r e v e r s eb a s e l i n e ：盯t = n i ，n 一1 ，o ，l i 礼一1 7 上海交通大学博士学位论文 3 b a r l y a n ( i n d i r e e tb i n a r yn c u b e ) ：o l = 【o ，n z 】，1 i 礼一1 4 f 1 i p ：c r t = i 他一l ，1 ，o ，1 i 佗一1 5 m o d i f i e dd a t am a n i p u l a t o r ：o i = i o ，j l ，1 i 佗一1 6 s h u m e e x c h a n g e ：o i = 【o ，1 ，仃一1 】，1 i s 一1 7 伸是柚刊，蓦蚤x c h a n g ，h w a n g 和】1 0 n g 证明了 定理2 1 2 每个位变换网络都同构于一个位变换网络g ( 盯1 ，仃2 ，一1 ) ，其中 吼= 1 0 ，觑l ，1 礼一1 ，1 z s 一1 。 定理2 1 2 中的位变换网络可以简记为( 七1 ，一，) ，称为该网络的特征序 列。当g 的特征序列为( 昆1 ，庇2 ，一1 ) 时，它的第i 级结点( z l z 2 z n 一1 ) 与第i + 1 级 的结点( 可1 可2 一1 ) 相邻当且仅当协= ，l 歹礼一1 ，j 觑。若序列( 忌1 ，七2 ， 一1 ) 满足条件：1 觑l h ，七2 ，) i ( 1 i s 1 ) ，则称此序列为规范序 列。c h a n g ，h w a n g 和t o n g 还证明了 定理2 1 3 每个位变换网络都同构于唯一一个具有规范特征序列的位变换网 络，两个位变换网络同构当且仅当它们的规范特征序列相同。 一个位变换网络的特征序列不是唯一的，而规范特征序列是唯一的。位变换 网络的特征序列( 忌1 ，忌2 ，一，) 以一个自然的方式导出边级集上的一个划分：边 级易和e ，属于该划分的同一个子集的充分必要条件是觑= 如。在c h a n g ，h w a n g 和 t o n g 的工作中，实际上已经证明了，两个位变换网络同构当且仅当它们的特征序列 导出的划分是相同的。因此( 1 ，2 ，佗一1 ) 和( 佗一1 ，2 ，1 ) 是同构的网络，它们都 表示一个与o m e g a ( 2 礼一1 级的洗牌交换网络) 等价的网络。除非特别申明，在本文 中我们仅使用规范特征序列来表示位变换网络，而且直接使用术语特征序列来代替 规范特征序列。特征序列的许多例子可以在【4 9 中找到。 在本文中，所有网络都被当作一个有向图来对待，在大多数情况下不区分拓扑 同构的网络，结点的标号对一个图来说不是必须的，但当一个位变换网络以它的特 征序列给出时，总是假定所有结点都已经标号，使得其特征序列可用。但在画位变换 网络的图形时，标号一般都是以默认的形式给出，即根据图形的实际画法，标号遵循 从上到下或从左到右的自然顺序。本文包含很多位变换网络的图例，如图3 2 ( a ) 和 图6 2 。 8 第二章位变换网络的图论刻划 最后，我们再引进几个记号。为了寻求可重排的多级互连网络，2 佗一1 级的网络受 到极为广泛的关注，并且得到深入研究( 如5 8 7 5 1 ) ，最典型的例子就是具有2 n 一1 级 的b e l l e 网络和洗牌交换网络。我们将用b 。和& 分别表示2 n 一1 级的b e l l e 网络和沈 牌交换网络，它们的特征序列分别是( 1 ，2 ，仡一l ，n 一1 ，2 ，1 ) 和( 1 ，2 ，礼一 l ，l ，2 ，几一1 ) 。用记号伫0 馆表示所有由两个o m e g a 等价网络串连起来的2 佗一1 级 网络的集合，用仃0 力表示仃0 力中所有的位变换网络组成的子集。我们使用不同 的记号是因为它们的确是不相同的集合，这一点将在节2 3 得到验证。 在本文中，我们将对仃0 力中两类特殊的网络作较多的讨论，它们的定义如下： 对任意七，1 南n 一1 ，设砩k 是将b 凡的特征序列中的第n 到第n + 七一1 个分量 改为相反次序而代表的位变换网络，设磁。是将鼠的特征序列中最后七个分量以相 反次序代替而到的位变换网络，它们也可以分别看作是将b e 1 e 百网络中不同位置的 两个七+ l 级子网作对称后得到的。砩和砩的特征序列分别是( 1 ，n 一1 ，竹一 七，孢一1 ，咒一后一l ：，1 ) ，( 1 ，几一1 ，礼一1 ，七+ 1 ，1 ，后) 。显然，b ：】= 磁，。= b n ，b ：，礼一，= j e 7 i m 一，= & 。注意砩，外部的边级是对称的，而砩，。两端不对 称。 2 2 位变换网络的图论刻划 对位变换网络中的许多问题的研究都大大早于这个概念的出现时问，由于网 络的内在结构被所采用的不同表示方式所掩盖，甚至出现同一个网络被反复发现， 并且以不同的名称被长期研究的现象。例如礼= l o g 级的网络o m e g a f 2 8 ，f 1 i p 2 6 1 ， i n d i r e c tb i n a r yc u b e f 2 9 ， m o d i f i e dd a t a m a n i p u l a t o r 27 ， b a s e l i n e ， r e v e r s e b a s e l i n e 【3 0 ，b u t t e r f l y ，r 脚e r s eb u t t e r a y 【3 ，由于具有很好的一些特性，如可分 性( p a r t i t i o n a b i l i t y ) 、自适应路由( s e l f - r o u t i n g ) 等，得到广泛的研究。1 9 8 0 年w u 和 f e n g 【3 0 】首次正式地给出多级网络拓扑等价的定义，并通过具体给出同构关系证明了 上面提到的所有礼级网络都是拓扑同构的。对网络的拓扑结构的研究是重要的，同构 的网路具有相同的置换实现能力( 实现置换的个数相同) ，针对一个网路设计的算法 可以移植到同构的网络，而且为了某种需要，我们可以选取最合适的网络表达方式， 从而使问题简化。这方面的另一工作是由a g r a w a l 所作的【4 5 1 ，但遗憾的是他的结果 只对n 级且咒很小的网络才正确。h u ，s h e n 和y a n g f 5 8 】以及c a l a m o n e r i 和m a s s i n i 【5 4 1 通 过算法来检验某些n 级或2 n 一1 级网络问的同构。首先应用图论的方法来研究多级 网络结构的工作属于b e r m o n d ，f 0 u r n e a u 和j e a n m a r i e 4 6 ，4 7 ，4 8 1 ，他们完全利用 图论的术语给出了o m e g a 等价网络的一个刻划。 9 上海交通大学博士学位论文 以下所说的连通是指去掉网络中所有边的方向后的连通( 即弱连通) ，也不考 虑一条路上边的方向。 定义2 2 1 设l i 歹礼。 俐若g 中每对输入和输出结点间有唯一一条路连接，则称它是满足j e 7 0 聊。礼性 质的； 一i ，若g t ，恰好包含2 n j 卅一1 个连通分支，则称g 满足性质p ( i ，歹) ；g 满足性质 尸( 冰，木) 当且仅当它对所有i ，歹均满足p ( i ，j ) 。 定理2 2 2 ( 【4 7 ) g 同构于( 二元的) o m 留口网络当且仅当它满足b 口咒y o 几性质 和p ( ：i ：，牢) 。 在同一工作中，b e r m o n d ，f o u r n e a u 和j e a n m a r i e 还将条件p ( 木，水) 减为p ( 1 ，木) 和 p ( 木，凡) 。另外，h o t z e l 【1 3 也给出了o m e g a 等价网络的几个刻划。这些结果都只是针 对二元的0 m e g a 网络，因而其局限性是明显的，下面我们将把定理2 2 2 推广到任意 基数d 和任意级数s 的所有位变换网络。 设丌为多级网络g 的边级集 e 1 ，岛，e s 一1 ) 上的一个划分( 或等价关系) ，用 符号【厩】表示晟所在的等价类，令死，j = i 【易】，【鼠+ - 】，【马一，】) i 。设仳m ，u 巧，( 札，歹) = 伽i 叫k ，且g 中存在一条从到加的路) ，( u ，t ) = 叫i 训k ，且g 中存在一条从叫到u 的路，1 i j s 。先对定义2 2 1 作如下推广 定义2 2 3 设l is 歹s 。 一i i ，若g ，恰好包含d ”一代j 一1 个连通分支，则称g 满足性质p 丌( t ，歹) ；g 满足性 质只( 术，木) 当且仅当它对所有t ，j 均满足p 丌( t ，j ) ； 一训若对任意u ，u ，( 让，歹) = ( u ，歹) 和( u ，歹) n ( ，j ) = 之一成立，则 称g 满足性质q 歹) ；g 满足性质q ( 木，木) 当且仅当它对所有t ，歹均满足q ( z ，歹) ； 俐若在g t ，j 的每个连通分支中，各级的结点数均为d 叱，其中咄，j 为某个整数， 则称g 满足性质兄( i ，歹) ；g 满足性质r ( 木，木) 当且仅当它对所有i ，j 均满足r ( i ，歹) 。 定理2 2 4g 为一个位变换网络当且仅当存在g 的边级集 目，易，现一1 ) 的 一个划分丌，使得g 满足性质只( 术，木) 和q ( 木，木) 。 当d = 2 ，s = 礼，且丌的每个子集恰包含一个元素时，性质p 丌( z ，歹) 和乓( 木，水) 正是 定理2 2 2 中的性质p ( z ，j ) 和p (