（应用数学专业论文）多级互连网络及其可重排性研究.pdf

上海交通大学硕士学位论文 明其可重排性。 1 9 8 5 年以来，作者至今尚未见到系统阐述多级互连网络理论 进展的国内论著，本文试图在比较全面地介绍目前广泛应用的各 种多级互连网络的基础上，以网络的可重排性作为本文的主线， 结合本人的一些初步工作，向国内希望了解这一研究课题近期进 展的数学工作者介绍多级互连网络的基本概念、已知的结论及一 些尚待解决的问题。 主要内容有以下三个方面： 1 提出了利用网络的拓扑等价和功能等价证明多级互连网络 可重排性的方法，并以具体的实例来说明这种方法对于研 究2 1 0 9 n 一1 级或2 1 0 9 n 级多级互连网络是有意义的； 2 比较全面地介绍了目前广泛应用，但散录在很多文献中的 各种多级互连网络； 3 已有的大量有关多级互连网络的文献中所使用的术语比较 混乱，本文试图采用统一的术语来描述多级互连网络。 关键词多级互连网络，可重排网络，b e n e s 猜想，s e 网络。 上海交通大学硕士学位论文 as i 瓜v e yo ft h em u l 月i s t a g e i n t e r c o n n e c t i o nn e t w o r ka n di t s 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 k s ( m i s s ) i s ak i n do f w i d e l y u s e ds w i t c h i n gn e t w o r k i ti sf i r s tu s e di nt e l e p h o n en e t w o r k ，a n d l a t e ri ti su s e dt o e x c h a n g e i n f o r m a t i o nb e t w e e n p r o c e s s o r s o r b e t w e e n p r o c e s s o r s a n dm e m o r ym o d u l e so f c o m p u t e r a st h e p a r a l l e lo n e - t o - o n ed a t ae x c h a n g ei s af u n d a m e n t a lr e q u i r e m e n to f s w i t c h i n gn e t w o r k s ，m i n i s a l w a y sr e q u i r e d t or e a l i z ea l lt h e p e r m u t a t i o n so fa n yni n p u t o u t p u tp a i r s ，t h a tm e a n st h e m i s s s h o u l db ea r e a r r a n g e a b l e n e t w o r k a n d p a r t i c u l a r l y , m a n y r e s e a r c h e r s a r e a l w a y s i n t e r e s t e di n 2 n - s t a g eo r ( 2 n - 1 ) s t a g e ( h = l o g n ) n e t w o r k s i n19 6 0 s ，c l o sa n db e n e sl a i das o l i df o u n d a t i o no nt h et h e o r y o fm n s i n19 7 5 ，b e n e sp r o p o s e dt h ef a m o u sc o n j e c t u r e ：f o rs e n e t w o r k s ，( 2 n - 1 ) - s t a g ei s s u f f i c i e n tt ob er e a r r a n g e a b l e f o rs e v e r a l d e c a d e s ，m a n y r e s e a r c h e r st r yt os t u d yt h er e a r r a n g e a b i l i t yo f m i n s ， b a s e do ns o m e s p e c i f i c2 n s t a g eo r ( 2 n - 1 ) 一s t a g ex t l n s w u , f e n g 8 】 a n dl e e 9 】s h o w nu sb a s e l i n e 。- b a s e l i n e _ 1a n do m e g a 川- o m e g a a r et o p o l o g i c a l l y e q u i v a l e n tt o b e n e sn e t w o r k y e ha n df e n g 6 】 s t u d i e da s y m m e t r i c a lc l a s so fm i n s ，w h i c h h a v et h es a m er e c u r s i v e s t r u c t u r ea sb e n e sn e t w o r k ，a n ds h o w nt h a tt h i sc l a s so fi v i n sa r e r e a r r a n g e a b l e a l lt h ea b o v en e t w o r k sa r eb a s e l i n e t y p e l i n s i n 19 9 7 ，q i n gh u ，x i a o j u ns h e na n d j i n g y uy a n g 4 6 】s t u d i e dt h e t o p o l o g ys t r u c t u r eo f ( 2 n - 1 ) - s t a g en e t w o r k 0 a ，a n da l s ot h e y p r o p o s e da l la l g o r i t h mt od e t e r m i n e w h e t h e rt w o g i v e n o 7 a r e t o p o l o g i c a l l ye q u i v a l e n t i n1 9 9 9 ，f e n ga n dm a 4 p r o p o s e da l l a l g o r i t h mt os o l v et h er o u t i n go f av a r i a n to f 2 n - - s t a g es e n e t w o r k o m e g a o m e g an e t w o r k b u t ，t h ep r o b l e m o ft h er e a r r a n g e a b i l i t yo f ( 2 n - 1 ) - s t a g es e n e t w o r ki ss t i l lo p e nn o w 上海交通大学硕士学位论文 i n t h e o r y 4 1 3a n dt h e o r y4 1 4 ，w e p r o p o s e d at o p o l o g i c a l e q u i v a l e n tm e t h o d t os o l v et h er e a r r a n g e a b i l i t yo fm 【n s a n ds t u d y h o wt w o b a s e l i n e - t y p en e t w o r k s a n d a r ec o n n e c t e d a n dl e t t h en e wn e t w o r k 一一b er e a r r a n g e a b l e a tt h es a l n et i m e ，i n t h e o r y4 1 5 ，w ep o i n t o u tt h a tr e p l a c i n go n es u b n e t w o r kw i t ha f u n c t i o n e q u i v a l e n t n e t w o r kw i l ln o ti n f l u e n c et h en e t w o r k s p e r m u t a t i o na b i l i t y a n d w et a k et h e1 6 x 1 6 o m e g a o m e g a n e t w o r ka se x a m p l et oi l l u s t r a t ei t sr e a r r a n g e a b i l i t y s i n c e19 8 5 t h ea u t h o rh a v e n ts e e na n yl i t e r a t u r ed e v o t e dt 0 d i s c u s s si nc h i n e s e t h i sp a p e rt r yt o p a r t i c u l a r l y i n t r o d u c e d i f f e r e n tk i n d so f w i d e l yu s e dn e t w o r k s ，a n do r g a n i z et h ep a p e ri n t h er e a r r a n g e a b i l i t yo f n sw i t ho u re x p l o r i n gw o r k a n dh e l pt h e m a t h e m a t i c i a n st ou n d e r s t a n dt h eb a s i cc o n c e p t so fh n s k n o w n r e s u l t sa n ds o m e o p e np r o b l e m s t h em a i nc o n t e n to f t h i s p a p e r a r ea sf o l l o w i n g ： 1 t h i sp a p e rp r o p o s eat o p o l o g i c a l e q u i v a l e n ta n df u n c t i o n e q u i v a l e n tm e t h o d t os o l v et h e r e a r r a n g e a b i l i t yo f s a n d w et a k eas p e c i f i ce x a m p l et os h o wt h a tt h i sm e t h o dm a k e s e n s e 2 i n t r o d u c ed i f f e r e n tk i n d so fw i d e l yu s e dn e t w o r k sw h i c h s c a t t e r e di n m a n y l i t e r a t u r e 3 d i f f e r e n tk i n dt e r m si nl i t e r a t u r ea r eu s e dt od e s c r i p tm n s i nt h i sp a p e r , w et r yt ou s et h es a m et e r m st od e s c r i p ta l lt h e ：n s k e yw o r d s x 恤r n s ，r e a r r a n g e a b l en e t w o r k , b e n e sc o n j e c t u r e ， 上海交通大学硕士学位论文第l 页 第一章多级互连网络简介 在通信系统及分布和并行计算机系统中已经广泛地应用了多级互连网 络( m i n s ) ，用来在电话网络或计算机的处理器之间或处理器与存储模块之 间交换信息的。因为许多并行算法是在一对一数据传输的基础上设计的， 因此常常要求1 n s 实现处理器之间的任意置换，即要求网络具有可重排性。 所谓可重排网络就是指，带有n = 2 ”个输入输出的互连网络( 1 n s ) ，对! 个置换中的任意一个置换经过网络一次即可以实现此置换【1 。其中 2 0 0 9 ：n ) ( 或者2 0 0 9 2 n ) - 1 ) 级可重排网络一直是众多学者研究的热点，参 见文献 2 】， 3 】，【4 ， 5 】，【6 】，【7 】， 8 。但是，迄今为止，我们并不知道 是否所有2 ( 1 0 9 2 n ) 级基于o m e g a 的腑都是可重排的，如2 ( 1 0 9 2 n ) 级 o m e g a o m e g a 网络的可重排性尚不清楚。 众所周知，b e n e s 网络 2 】为可重排网络，a w a k s m a n 在 5 】中证明了 b e n e s 网络能够实现从个输入到个输出的! 个置换。w u 和f e n g 1 0 1 比较了六个常用l o g ，n 级阻塞网络，证明了它们相互之间的拓扑等价性， 并进一步声明了它们有相同的路由能力。w u 和f e n g 8 1 向我们展示了 b a s e l i n e 一b a s e l i n e l 拓扑等价于b e n e s 网络；l e e 在 9 】中向我们展示了 o m e g a - o m e g a 。等价于b e n e s 网络，亦为可重排网络。y 如f e n g 6 及 k i m ，y o o n ，m a e n g 7 对具有对称结构的m _ n s 得出了可重排的结论，这种 具有对称结构的g n s 和b e n e s 网络有相同递归构造形式。最近，f c n g 和 m a 4 提出了一种算法来解决一类2 ( 1 0 9 2 n ) 级o m e g a o m e g a 网络的可重 排性。以上的这些研究工作都是针对具体的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 ，o m e g a - o m e g a 。及o m e g a o m e g a 为例，利用本文 中提出的结论可以容易地证明他们拓扑等价于b e n e s 网络或者和b e n e s 网 络具有相同的置换能力，从而说明它们具有可重排性质，有着很好的实用 效果。 本文讨论的主要对象是多级互连网络。在多级互连网络的提出和发展过 程中，由b e n e s 所建立起来的理论占有十分重要的地位。现今所使用的多级 互连网络中，他所提出的b e n e s 网络依然有着广泛的应用和影响。 为了使数学工作者能对多级互连网络的提出背景有所了解，以便在阅读 上海交通大学硕j ：学位论文第2 页 有关计算机方面的文献时更加清晰。在本章中，我们先给出互连网络的整 体介绍然后再介绍多级互连网络的基本概念。 1 1 互连网络的分类 自从c l o s 和b e n e s 为多级互连网络( m i n s ) 奠定了基本的理论基础后，多 级互连网络即在交换网络中得到了广泛的应用。在当今的科学和工程应用 领域对并行和分布计算能力的要求越来越高，因此有必要在并行处理概 念的基础上开发高级计算机结构。在本节中，我们就以计算机的结构为例 来讨论互连网络的基本概念。通常一个并行计算机系统由许多处理器单 元、存储单元及其他资源所组成。在设计和分析并行计算机系统中的一个 关键问题就是必须在处理器之间或处理器与存储器之间提供经济和可靠的 互连网络。随着计算机或处理器数目的增多，这种互连网络将变成系统设 计的关键环节，它的好坏直接影响着整个系统的性能所以，多年来一直 吸引着研究和技术人员对多处理器或多计算机的互连网络进行研究。 一个互连网络可以由以下三个部分组成：( i ) 端点的集合；( i i ) 实现 端点间连接的互连网络；( i i i ) 控制单元，用来控制端点之间在互连网络中 的连接。互连网络中端点间的连接按以下步骤进行：( f ) 两个空闲的端点 要求建立连接；( i i ) 控制单元处理端点间的连接要求，如果可能的话，建 立端点间的连接：( i i i ) 端点间的通信结束之前，端点间的连接一直存在； ( i v ) 当端点间的通信结束时，端点回复到空闲状态。图1 _ l 示出了一个互 连网络的大体结构。 针对不同的系统，互连网络的抽象不同。其中最著名的有单指令流多数 据流( s i m d ) 及多指令流多数据流( m i m d ) 的计算机体制 1 1 】。但它们 都可以看成由n 个处理单元p e ( 每个p e 均由处理器和存储器所组成) 用 公共网络互连起来。无论在s i m d 还是在m i m d 体制中，对p e 所能使用 的存储器而言，既可以为所有p e 公共拥有，也可以是某一p e 所专有，分 别示于图1 1 2 和图1 1 _ 3 。前者适用于处理器与存储器数目相等的场合；后 者当处理器数目多于存储器时尤为适合。 m i m d 计算机实质上就是通常所说的分布式计算机系统 1 2 。对上述两 种机器组态那些具有共享存储器的m i m d 通常称为多处理机或多处理器 ( m u l t i - p r o c e s s o r ) ，此时所有的处理器共享同一个存储器；而不具有共享 存储器的m i m d 则称为多计算机( m u l t i - c o m p u t e r ) ，此时每个计算机都拥 有它自己私有的存储器。 上海交通大学硕j ：学位论文第2 页 有关计算机方面的文献时更加清晰。在本章中，我们先给出互连网络的整 体介绍然后再介绍多级互连网络的基本概念。 1 1 互连网络的分类 自从c l o s 和b e n e s 为多级互连网络( m i n s ) 奠定了基本的理论基础后，多 级互连网络即在交换网络中得到了广泛的应用。在当今的科学和工程应用 领域对并行和分布计算能力的要求越来越高，因此有必要在并行处理概 念的基础上开发高级计算机结构。在本节中，我们就以计算机的结构为例 来讨论互连网络的基本概念。通常一个并行计算机系统由许多处理器单 元、存储单元及其他资源所组成。在设计和分析并行计算机系统中的一个 关键问题就是必须在处理器之间或处理器与存储器之间提供经济和可靠的 互连网络。随着计算机或处理器数目的增多，这种互连网络将变成系统设 计的关键环节，它的好坏直接影响着整个系统的性能所以，多年来一直 吸引着研究和技术人员对多处理器或多计算机的互连网络进行研究。 一个互连网络可以由以下三个部分组成：( i ) 端点的集合；( i i ) 实现 端点间连接的互连网络；( i i i ) 控制单元，用来控制端点之间在互连网络中 的连接。互连网络中端点间的连接按以下步骤进行：( f ) 两个空闲的端点 要求建立连接；( i i ) 控制单元处理端点间的连接要求，如果可能的话，建 立端点间的连接：( i i i ) 端点间的通信结束之前，端点间的连接一直存在； ( i v ) 当端点间的通信结束时，端点回复到空闲状态。图1 _ l 示出了一个互 连网络的大体结构。 针对不同的系统，互连网络的抽象不同。其中最著名的有单指令流多数 据流( s i m d ) 及多指令流多数据流( m i m d ) 的计算机体制 1 1 】。但它们 都可以看成由n 个处理单元p e ( 每个p e 均由处理器和存储器所组成) 用 公共网络互连起来。无论在s i m d 还是在m i m d 体制中，对p e 所能使用 的存储器而言，既可以为所有p e 公共拥有，也可以是某一p e 所专有，分 别示于图1 1 2 和图1 1 _ 3 。前者适用于处理器与存储器数目相等的场合；后 者当处理器数目多于存储器时尤为适合。 m i m d 计算机实质上就是通常所说的分布式计算机系统 1 2 。对上述两 种机器组态那些具有共享存储器的m i m d 通常称为多处理机或多处理器 ( m u l t i - p r o c e s s o r ) ，此时所有的处理器共享同一个存储器；而不具有共享 存储器的m i m d 则称为多计算机( m u l t i - c o m p u t e r ) ，此时每个计算机都拥 有它自己私有的存储器。 上海交通大学硕士学位论文第3 页 这两种类型又可以分别根据互连网络的体系结构进一步细分，在图 1 1 4 中，我们把这两种分类描述为总线型( b u s ) 和交换型( s w i t c h e d ) 。 端点 图1 1 1 互连网络的大体结构 p e o p e 端点 p e n 1 图1 1 2私有存储器机器组态 处理器0处理器1处理器n - 1 i 互连网络 j 存储器0存储器1存储器n - 1 图1 1 3共享存储器机器组态 所谓总线型是指仅通过单个网络、底板、总线、电缆或其他介质将所有 计算机联结起来。有限电视采用的就是与此类似的方案，即电缆公司在街 上海交通大学硕士学位论文第4 页 道下面布线，所有的用户都通过分接头将他们的电视与这条总线连结起来。 本文并不打算对总线型的网络进行介绍，有兴趣的读者可以参阅相关的文 献。 交换型系统并不像有线电视那样有一个网络主干，而是在机器和机器之 间有独立的线路，在实际应用中有许多不同的连线方式，本文所研究的多 级互连网络即为其中很重要的一种。在交换型系统中信息沿着线路传送， 在每一步都需要进行明确的路由选择，以将信息通过某个输出线路发送出 去。如今，我们所使用的世界范围的公共电话系统就是采用这种方式组织 的。 图1 1 4并行及分布式计算机系统分类法 在分析各类互连网络时，我们把连结的对象( 如处理器、运算器、存储 器等) 称为节点，对应的单向或双向通路称为边。 从几何形状上看互连网络可分为两大类：规则网络和不规则网络，参见 图1 1 5 。本文中我们所提到的互连网络均为规则网络，规则网络又可以分 为静态网络和动态网络。 静态网络又叫直接互连网络，或基于寻径器的网络，是指网络中的单元 是点到点连接的，网络单元之间使用专用的连线，其连接形式是固定的。 一般地相邻的两节点通过一对相反方向的单向通道连接但也可用一个 双向的通道连接所有的节点都有一个寻径器来处理节点间的消息通信。 静态网络又可进一步分为全互连网、星形网、总线、循环移数网、一维线 性网、环网、网格网、树形网、超立方体网、m 元n 立方体网、p a r a d h a n 网等。其中，环网、网格网和超立方体网是典型的静态网络的拓扑结构。 总线型m n f d 及大部分的交换型m i m d 多处理机均属于此种类型。 互 连 网 络 上海交通大学硕士学位论文 第5 页 动态网络又叫间接互连网络，或基于开关的网络，是指网络单元间的连接 是通过公共总线或网络的交换单元实现的，而非固定的，在不同的时间， 或不同的要求下，可能有不同的连接。它适用于大规模互连网络的网络拓 扑结构。在这类网络中网络的各节点不是通过直接相连的通道进行消息 通信，而是通过网络的开关元件进行的。 不规则网络 规则网络 静态网络 动态网络 全互连网 星形阿 总线 循环移数网 一维线性网 环网 网格网 树形网 交叉开关网 单级互连网 多级互连网 图1 1 5 互连网络的分类 动态网络也可进一步分为交叉开关网络、单级互连网络和多级互连网 络。对单级互连网络而言，数据在最终到达目的地之前往往须连续穿过网 上海交通大学硕士学位论文 第6 页 络若干次，所以也称为循环网络。单级互连网络包括最常用的网孔连接网 络，p m 2 i 网络，洗牌交换网络和立方网络等。有兴趣的读者可以参阅文献 1 3 。而对多级互连网络而言，数据一般只须穿过网络一次，即可到达目的 地。 多级互连网又可分为阻塞网、可重排非阻塞网、非阻塞网。典型地，三 级c l o s 网络为非阻塞网络：b e n a s 网络为可重排非阻塞网络：o m e g a 网络 ( 即q 网络) 、基准网络( 即b a s e l i n e 网络) 、间接二进制n 立方网络( t h e i n d i r e c tb i n a r yn - c u b en e t w o r k ) 、艿网络、数据变换网络( d a t a m a n i p u l a t o r n e t w o r k ) 、s t a r a n 网络和正规s w 榕树网络( r - e g u i a rs w - b a n y a nn e t w o r k ) 等为阻塞网络。大部分的交换型m i m d 多计算机均属于动态网络。 值得注意的是，动态网络中的单级互连网络的拓扑结构本质上与静态网 络的拓扑结构相同。把静态网络的固定连接换成开关便是单级互连网络。 要实现任意节点间的互连有两种方法。一种是循环使用同一套单级互连网 络，组成循环互连网络；另一种办法是把多套相同的单级互连网络串联起 来，组成阻塞的多级互连网络。如果阻塞的多级互连网络再循环使用或 背靠背连接，又可组成可重排非阻塞网络。 在本文中所讨论的多级互连网络即属于动态网络。有关静态网络，本文 并不打算进行讨论，有兴趣的读者可以参阅文献【1 4 ， 1 5 。 评价一个多级互连网络的好坏，一般从以下几个方面考虑： ( 1 ) 连接特性好，即实现的互连函数多。 ( 2 ) 网络延时少即网络的级数少。 ( 3 ) 使用的开关数量少。 ( 4 ) 控制简单即可以找到较好的算法。 ( 5 ) 便于集成。 1 2 有关多级互连网络的一些基础知识 在上一节中，我们已经提到了多级互连网络的结构可以用开关元件、连 接模式和控制方式三个参量描述。下面就对这三个方面进行简单的介绍。 1 开关元件 开关元件可根据控制信号的不同，工作在各种不同的状态，从而实现输 入端点与输出端点之间的连接。一般情况下，开关的输入端数，与输出端 数0 可以相等，也可以不等。当二者相等时，一般选，= o = 2 ”，”2 1 。 我们最常用的开关有2 x 2 ，4 x 4 等在这些开关中，每个输入可同时与一 上海交通大学硕士学位论文 第6 页 络若干次，所以也称为循环网络。单级互连网络包括最常用的网孔连接网 络，p m 2 i 网络，洗牌交换网络和立方网络等。有兴趣的读者可以参阅文献 1 3 。而对多级互连网络而言，数据一般只须穿过网络一次，即可到达目的 地。 多级互连网又可分为阻塞网、可重排非阻塞网、非阻塞网。典型地，三 级c l o s 网络为非阻塞网络：b e n a s 网络为可重排非阻塞网络：o m e g a 网络 ( 即q 网络) 、基准网络( 即b a s e l i n e 网络) 、间接二进制n 立方网络( t h e i n d i r e c tb i n a r yn - c u b en e t w o r k ) 、艿网络、数据变换网络( d a t a m a n i p u l a t o r n e t w o r k ) 、s t a r a n 网络和正规s w 榕树网络( r - e g u i a rs w - b a n y a nn e t w o r k ) 等为阻塞网络。大部分的交换型m i m d 多计算机均属于动态网络。 值得注意的是，动态网络中的单级互连网络的拓扑结构本质上与静态网 络的拓扑结构相同。把静态网络的固定连接换成开关便是单级互连网络。 要实现任意节点间的互连有两种方法。一种是循环使用同一套单级互连网 络，组成循环互连网络；另一种办法是把多套相同的单级互连网络串联起 来，组成阻塞的多级互连网络。如果阻塞的多级互连网络再循环使用或 背靠背连接，又可组成可重排非阻塞网络。 在本文中所讨论的多级互连网络即属于动态网络。有关静态网络，本文 并不打算进行讨论，有兴趣的读者可以参阅文献【1 4 ， 1 5 。 评价一个多级互连网络的好坏，一般从以下几个方面考虑： ( 1 ) 连接特性好，即实现的互连函数多。 ( 2 ) 网络延时少即网络的级数少。 ( 3 ) 使用的开关数量少。 ( 4 ) 控制简单即可以找到较好的算法。 ( 5 ) 便于集成。 1 2 有关多级互连网络的一些基础知识 在上一节中，我们已经提到了多级互连网络的结构可以用开关元件、连 接模式和控制方式三个参量描述。下面就对这三个方面进行简单的介绍。 1 开关元件 开关元件可根据控制信号的不同，工作在各种不同的状态，从而实现输 入端点与输出端点之间的连接。一般情况下，开关的输入端数，与输出端 数0 可以相等，也可以不等。当二者相等时，一般选，= o = 2 ”，”2 1 。 我们最常用的开关有2 x 2 ，4 x 4 等在这些开关中，每个输入可同时与一 上海交通大学硕士学位论文第7 页 个或多个输出相连，但不能有两个以上的输入端与一个输出端相连。如果 出现这种情况，就会发生冲突或争用。所谓冲突就是指要求一个输入端连 到一个输出端时，该输出端已被占用的状态。所谓争用就是指两个以上的 输入端同时要求连至同一个输出端的情况。 本文中所使用的开关元件基本上都是2 2 的每个开关元件有两个输 入端口，上输入端口l ，下输入端口，两个输出端口，上输出端口q ， 下输出端口d j ，如图1 2 l ( a ) 所示，这种开关元件可能有直通、交叉、 上播和下播四种工作状态，如图1 2 1 ( b ) 、( c ) 、( d ) 、c e ) 所示。 2 连接模式 连接模式是指多级互连网络的各级开关之间链路的互连模式。连接模式 实现的互连函数不同，就可以构成各种不同的多级互连网络。 3 控制方式 控制方式是指对网络中各级开关的控制方式，般有三种控制方式。 ( 1 ) 级控制 同一级开关使用同一个信号来控制，处于同一种工作状态。其优点是控 制简单、实现容易，但网络能实现的互连函数少。 上案入连蛾 n上输出连线q 下输入连绌五。一下输出连缝q ( a ) 2 2 开关元 # 垂# # ( b ) 直通( c ) 交叉( d ) 上播( e ) 下播 图1 2 1 2x 2 开关元件及其工作状态 ( 2 ) 单元控制 网络中的每一个开关都有单独的控制信号，所以同一级的开关也可以处 于不同的状态。单元控制的优点是网络实现的互连函数多，但控制复杂， 实现也不太容易。 ( 3 ) 部分级控制 这是介于上述两种控制方式之间的控制方式，是用i + 1 个控制信号来控 制第i 级开关，其中0 f 打一1 ，一为级数。 土壁至塑查学硕士学位论文第8 页 多级互连网络的连接模式从本质上反映了其连接特性，即从网络的输入 端到输入端的连接能力。连接模式可以用一组互连函数来表示，实现的互 连函数不同，就可以构成各种不同的多级互连网络。常用的互连函数表示 形式有两种：互连函数表示和输入输出对表示形式。设互连网络输入输出 端个数为n n = 2 “，则两种表示形式的具体描述如下： ( 1 ) 互连函数表示形式 用z 表示输入端变量，用，b ) 表示互连函数。引蔼二进制形式表示为 x n - i - 2 x t x 0 ，互连函数则对应地表示为厂k 1 - 2 x l x 0 ) 。例如 f ( x 工m 而) = x a _ 2 x 而x o 工。- l 表示均匀洗牌函数。即等号左边括号 内为输入端二进制地址，经均匀洗牌函数变换后，等号右边为对应的输出 端二进制地址。 ( 2 ) 输入输出对表示形式 另一种互连函数表示形式是列表表示形式， 力) ：爿1 ) o 热上嘈的输入0 , 1 , - , n - 1 各端号变换 成下一排对应输出的各端号，( 0 ) 厂( 1 l ，( 一1 ) ， = 8 的均匀洗牌函数的这种表示形式为f ：2 4 1 3 几种常用的互连函数 下面我们先给出本文后面章节中要用到的几种互连函数。 1 恒等置换 恒等置换是相同编号的输入端与输出端一一对应互连所实现的置换。其 函数表达形式为：，b 。x 。) = 一。- x , x o ，其输入端与输出端的 变换图形如图1 3 1 所示。 2 交换置换 交换置换是实现二进制地址编号中第0 位位置不同的输入端与输出端 之间的连接。其函数表达形式为：e g 。x n 2 一x i x 。) = x n - ! - 2 一x o ，其输 入端与输出端的变换图形如图1 3 2 所示。 如例 o、 数7 7 函6 5连0， 互 是4 ， 、3 6 土壁至塑查学硕士学位论文第8 页 多级互连网络的连接模式从本质上反映了其连接特性，即从网络的输入 端到输入端的连接能力。连接模式可以用一组互连函数来表示，实现的互 连函数不同，就可以构成各种不同的多级互连网络。常用的互连函数表示 形式有两种：互连函数表示和输入输出对表示形式。设互连网络输入输出 端个数为n n = 2 “，则两种表示形式的具体描述如下： ( 1 ) 互连函数表示形式 用z 表示输入端变量，用，b ) 表示互连函数。引蔼二进制形式表示为 x n - i - 2 x t x 0 ，互连函数则对应地表示为厂k 1 - 2 x l x 0 ) 。例如 f ( x 工m 而) = x a _ 2 x 而x o 工。- l 表示均匀洗牌函数。即等号左边括号 内为输入端二进制地址，经均匀洗牌函数变换后，等号右边为对应的输出 端二进制地址。 ( 2 ) 输入输出对表示形式 另一种互连函数表示形式是列表表示形式， 力) ：爿1 ) o 热上嘈的输入0 , 1 , - , n - 1 各端号变换 成下一排对应输出的各端号，( 0 ) 厂( 1 l ，( 一1 ) ， = 8 的均匀洗牌函数的这种表示形式为f ：2 4 1 3 几种常用的互连函数 下面我们先给出本文后面章节中要用到的几种互连函数。 1 恒等置换 恒等置换是相同编号的输入端与输出端一一对应互连所实现的置换。其 函数表达形式为：，b 。x 。) = 一。- x , x o ，其输入端与输出端的 变换图形如图1 3 1 所示。 2 交换置换 交换置换是实现二进制地址编号中第0 位位置不同的输入端与输出端 之间的连接。其函数表达形式为：e g 。x n 2 一x i x 。) = x n - ! - 2 一x o ，其输 入端与输出端的变换图形如图1 3 2 所示。 如例 o、 数7 7 函6 5连0， 互 是4 ， 、3 6 上海交通大学硕士学位论文第9 页 0 0 l 一1 2 2 3 3 4 一d 5 - - - - - - - - - - - - - - - - - - 一5 6 6 7 - - - - - - - - - - - - - - - - - - - 7 7 ； ； ： 6 、。6 7 7 图1 3 1 恒等置换图1 3 2 交换置换 3 洗牌置换 均匀洗牌簧换是将输入端的二进制地址循环左移一位，于是得到了输出 端的二进制地址。其函数表达形式为： 盯g 一2 而z o ) = x n - 2 一3 x o _ 一】， 其输入端与输出端的变换图形如图1 3 3 所示。另外，洗牌置换还有子洗牌、 超洗牌及逆均匀洗牌置换等。 子洗牌置换是指输入端二进制地址的第k 位以下的部分进行循环左移 一位，第k 位以上的二进制地址不变，得到输出端二进制地址。其函数表 达形式为： o f f x ) ( 矗一】工扣2 - 一x k + i x f 工一i 一x l x o ) = - - - x a l 2 x k + i x 片，l x l x o x f 。 超洗牌置换是指输入端二进制地址的第刀一k l 位以上的部分进行循 环左移，第r l k 一1 位以下的二进制地址不变，得到输出端二进制地址。 其函数表达形式为： c r ( 。g 一1 x n 一2 一f x n r 一1 x 。一片一2 x l x o ) = x 。一2 x n k x 月一f 1 了 一】善 一片2 x l x o 逆均匀洗牌置换是将输入端的二进制地址循环右移一位，于是得到了输 出端的二进制地址。其函数表达形式为： 盯一b n 一】x 月一2 x l x oj = x o x h l x h 一2 x 月一3 x l 。 显然有以下两式成立： 0 - ( ”1 0 ) = q 州g ) = 盯g ) ； 仃b ) = c r ( 0 1 b ) = z 。 4 蝶式置换 蝶式置换是将输入端的二进制地址的最高位和最底位互换位置，得到相 应输出端的二进制地址。其函数表达形式为： 上海交通太学硕士学位论文第l o 页 矽g 。了m , x i ) = 而_ - 2 - 而刈其输入端与输出端的变换图形如图1 3 4 所示。另外，还有子蝶置换及超蝶置换等。 子蝶式置换是将输入端的二进制地址的最高位和最底位互换位置，得到 相应输出端的二进制地址。其函数表达形式为： 崩f l b 州矗一2 x k + i x f x 一】x 1 z 。j = x m - l x h 一2 h + 】x r 1 毛工f a 超蝶式置换是将输入端的二进制地址的一一k 一1 位和最高位互换位置， 得到相应输出端的二进制地址。其函数表达形式为： 怛0 一- 1 x a _ k x n 一一f 一2 而石o ) = x a - k - 1 x n 一2 一f 矗一l z 卜f 2 x t x o 同样有以下两式成立： 卢h 。1 g ) = 反。1 g ) = 卢b ) ： 卢o 扛) = 崩。1 0 ) = x 。 图1 3 3 均匀洗牌置图1 3 4 蝶式置换 5 位序颠倒置换 位序颠倒置换是把输入端的二进制地址的位序颠倒过来，得到相应输出 端的二进制地址。其函数表达形式为：p ( x s l 善。2 工1 ) = x o x 】一2 】 当：8 时，其输入端与输出端的变换图形亦可由图1 3 4 表示。另外，还 有子位序颠倒置换及超位序颠倒置换等。 子位序颠倒置换函数的表达式为： p ( 、协卜【x 2 。工“x 片z r 一1 工t 石oj = x 卜1 x 一_ 2 工r + 1 x o x l x 一i 善。 超位序颠倒置换函数的表达式为： p 。g 。一】x n - k x n r 1x 月一f 一2 - x l x 。) = x n - i ( - i x 月一 同样也有以下两式成立： 户”b ) = p ( 。) b ) = 卢b ) ； p ( 0 b ) = 只o ) 扛) = # 。 上海交通大学硕士学位论文第1 2 页 绍。在本文的第二部分( 第四章) ，是我们在多级互连网络可重排性方面所 做的一些工作；在这一章中，我们提出了利用网络的拓扑等价和功能等价 证明多级互连网络可重排性的方法，并以b a s e l i n e 类复合网络 b a s e l i n e “- b a s e l i n e 一，o m e g a o m e g a “及o m e g a o m e g a 为例利用本文 中提出的结论可以容易地证明他们拓扑等价于b e n e s 网络或者和b e n e s 网 络具有相同的置换能力，从而说明它们具有可重排性质，有者很好的实用 效果。 1 5 本文的主要工作 自从1 9 6 5 年b e n e s 1 提出了经典的交换网络理论以来，国外的许多学 者对互连网络进行了大量的研究，发表了很多有价值的学术论文和专籍。 f r a n k k h u a n g 1 7 】对非阻塞交换网络的数学原理进行了研究； v a r m a r a g h a v e n d r a 1 8 】编集了许多论文，对互连网络的许多方面进行了详 细的介绍。但是目前国内尚无对互连网络进行详细介绍的文献，本文试图 比较全面的介绍目前熟知的各种多级互连网络，并以网络的可重排性作为 本文的主线，向国内的数学工作者介绍多级互连网络的基本概念、已知的 结论及一些尚待解决的问题，希望能作为有志于研究互连网络的数学工作 者的入门知识，并能从中找到一些既有理论研究价值又有实际应用意义的 研究课题。 本文的主要工作有以下三个方面： 1 本文中提出了利用网络的拓扑等价和功能等价证明多级互连网络可 重排性的方法，并以具体的实例来说明其对于2 1 0 9 n l 级或2 1 0 9 n 级多级互连网络有着很好的实用效果； 2 目前国内尚无对多级互连网络进行比较详细介绍的文献，本文比较全 面的介绍了目前熟知的各种多级互连网绍，及其基本概念、术语、已 知的结论及一些尚待解决的问题； 3 众多文献中对多级互连网络进行描述时所使用的术语比较混乱，本文 在借鉴前人的基础上，采用统一的术语对多级互连网络进行描述。 上海交通大学硕士学位论文第1 3 页 第二章阻塞的多级互连网络 2 1 几种常用的阻塞多级互连网络 一般地讲，阻塞的多级互连网络由一级( n = l o g