（计算机系统结构专业论文）基于Ω网结构的多级互连网及多播研究.pdf

中国科学技术大学硕士论文 致谢 在论文完成之际，首先感谢我的导师顾乃杰教授，没有他的悉心指导和帮助， 本文不可能顺利完成。在研究工作过程中，顾老师给了我极大的关怀和帮助；在 论文完成过程中，顾老师给了我许多鼓励和支持。顾老师治学严谨、思维敏捷、 学识渊博、坚持原则，无论是在治学态度还是在做人准则方面，都为我树立了学 习的典范。顾老师勤奋踏实的工作和诲人不倦的精神，使我永生难忘。顾老师敬 业爱国，以诚待人的高尚人品我将铭记在心，永以为镜。在此，谨向尊敬的导师 致以深深的敬意和衷心的感谢。 其次，我由衷地感谢在研究生学习阶段传授给我知识的陈国良、赵保华、杨寿 保、黄刘生、熊焰、许胤龙、安虹、蒋凡等老师，是他们用辛勤的汗水，培养我 不断成长进步。 感谢华为基金项目组的每一位老师和同学，在整个课题的研究工作中他们认真 负责的工作态度，他们的敬业和协作精神使我受益匪浅。项目组的李栋、刘刚两 位同学及任开新老师给我提出了大量极有见地的建议，并在日常的研究工作中给 了我无私的帮助。 感谢实验室的陈静、刘刚、胡红晖、谢晖、刘小虎、李婧、刘勇、张建明等同 学多年来的热心支持和大力帮助，实验室浓厚的研究氛围和和谐融洽的关系，使 我得以顺利地完成论文。特别感谢跟我一起度过了三年研究生生涯的陈静同学， 陈静同学知识丰富、乐于助人，从她身上，我学会了很多东西。这三年的学习生 活经历，将是我人生最宝贵的回忆之一。 最后感谢我的父母、家人和朋友，是他们多年来始终如一的理解和支持，使我 取得了今天的成绩。 中围科学技术大学硕上论文 摘要 多级互连网是并行分布式系统中一种重要的互连网络结构，能够有效的实现系 统内部处理器等功能部件之间相互的通信，包括单播、置换和多播等各种方式。 其中，多播操作的研究是一个有相当难度，但又具有重要应用价值的问题，也是 目前多级互连网络研究领域中的一个热门课题。而已有的关于多播的成果大多只 针对现有的多级互连网络，并且一般只能实现单个多播，对多播的支持能力很不 好。因此，为多播操作专门设计的多级互连网引起了越来越多的重视。y a n g 在 i7 中，提出了一种新的多播网络，硬件复杂度为o ( n l o g ! n ) 。 本文研究和分析了多种多级互连网( 尤其是结构简单规范的q 网) 的现有成果， 包括网络结构及相应的路由算法。并在此研究基础上，根据q 网上的置换和多播 的特点，提出了一种基于q 网结构的多播网络( j q 网) ，通过重排各级开关的状 c 态，可以不冲突的实现任意的多播，所需开关元件总数为三n l o g n 。然后又进一 z 步提出2 一q “xq 网，开关元件数降低至2 n l o g n 。与y a n g 提出的多播网络相比， 该多播网络的硬件代价小得多。 同时，我们对该网络上的多播路由进行了计算机模拟实验，所用算法的时间复 杂度是o ( n l o g n ) ，和目前的置换算法相同，这在相关的成果中，是最优的。并 且由于q 网络本身的结构较为简单规范( 每一级的连接模式都相同) ，所以j q 网 和2 一q 一q 网的硬件集成也非常容易，因此更具有实用价值。在这些多播网的构 造基础上，我们还提出了一种新的多播网络模型，为多播网络的设计以及现有的 多级互连网上多播问题的研究。提供了一种参考方法。 关键词：多级互连网，q 网，置换，多播，拓扑等价。 生璺登兰堇查壁堡圭堡茎王二_ a b s t r a c t i n p a r a l l e l a n dd i s t r i b u t e ds y s t e m s ，m u l t i s t a g e i n t e r c o n n e c t i o n n e t w o r k m i n ) i sa ni m p o r t a n tk i n do f i n t e r c o n n e c t i o ns t r u c t u r e i tc a n r e a l iz et h ec o m m u n i c a t i o n sa m o n ga l lt h en o d e si n t h es y s t e m ，i n c l u d i n g u n i c a s t s ，p e r m u t a t i o na n dm u l t i c a s t s a n dt h er e s e a r c h o nm u l t i c a s t si s as i g n i f i c a n tp r o b l e mw i t hq u i t eaf e wd i f f i c u l t i e s ，w h i c h i sa l s oa r e s e a r c hf o c u sn o w b u tm o s to fc u r r e n tr e l a t i v es t u d i e sm e r e l yf o c u so r t h ep r e v i o u sm i n sa n du s u a l l yi n v o l v eas i n g l em u l t i c a s to n l y t h e s er e s u l t s a r e n cv e r yg o o df o rm u l t i c a s t s s om o r ea n dm o r ea t t e n t i o n i sp a i dt o t h en e wm i nd e s i g n e de s p e c i a l l yf o rm u l t i c a s t s al o to fm i n sa r es t u d i e di nt h i sp a p e ri n c l u d i n gt h e i rn e t w o r k s t r u c t u r e sa n dt h ec o r r e s p o n d i n gr o u t i n ga l g o r i t h m s ，e s p e c i a l l yt h e q n e t w o r kw h o s es t r u c t u r ei ss i m p l ei nt h a ta l l i t sc o n n e c t i o nm o d e sa r e u n i f o r m b a s e do nt h e s es t u d i e s 。w ep r o p o s eam u l t i c a s tn e t w o r k ( 5 一n n e t w o r k lb a s e do nt h es t r u c t u r eo ft h enn e t w o r k f u r t h e r m o r e ，w ep r o p o s e a n o t h e rm u l t i c a s tn e t w o r k ( 2 一n1 xnn e t w o r k ) t h eh a r d w a r ec o s to ft h e s e t w on e t w o r k si s o ( n l o g n ) ，w h i c hi so p t i m a li nc u r r e n tr e l a t i v er e s u l t s i nt h em e a n t i m e ，w ep r e s e n tt h es i m u l a t i o no ft h er o u t i n gp r o c e s sf o r m u l t i c a s t si nt h em u l t i c a s tn e t w o r k t h et i m ec o m p l e x i t yo ft h em u l t i c a s t r o u t i n ga l g o r i t h mw ep r e s e n ti s0 ( n l o g n ) ，w h i c hi st h es a m ea st h o s eo f c u r r e n tp e r m u t a t i o nr o u t i n ga l g o r i t h m s w h a t sm o r e ，t h e s en e t w o r k sa r e e a s yt oi n t e g r a t eb e c a u s eo ft h es t a n d a r ds t r u c t u r eo fnn e t w o r k t h e n w ep r o p o s ean e t w o r km o d e lf o rm u l t i c a s t s ，w h i c hp r o v i d e san e wm e t h o df o r t h er e s e a r c ho nm u i t i c a s t si nm i n s k e y w o r d s ：m i n ，nn e t w o r k ，p e r m u t a t i o n ，m u l t i c a s t ，t o p o l o g i ce q u i v a l e n c e 中国科学技术人学硕士论文 第1 章多级互连网概述 多级互连网是并行分布式系统中的一种互连网络结构 1 ，能够有效的实现系 统内部处理器等功能部件之间相互的通信，是系统构成的主要组成部分，对并行 处理机的性能影响很大。这一章主要介绍多级互连网的概念、结构和分类等基础 背景知识，以及网络上置换、多播等各种通信操作问题的研究现状，并提出本文 的思考方向。 第1 节互连网络及其分类 互连网络是由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现 并行系统内部多个处理机或多个功能部件之间的相互连接。互连网络有三大要素： 连接模式( 互连拓扑) 、开关元件和控制方式，这三种要素的不同，决定了互连网 络的不同。从几何形状看，互连网络可分为规则网和不规则网两大类，其中舰则 网又分为静态网和动态网两种。 静态网又称直接互连网，网中结点是直接相连的。常见的环形网( r in g ) 、网 格形网络( m e s h ) 和立方体网络( c u b e ) 等都属于静态网。这种网络一旦构成以 后就固定不变了，比较适合于构成通信模式可预测的并行处理系统和分布式计算 机系统。 动态网又称间接互连网，是为了达到多用或通用的目的，根据程序要求实现各 种通信模式的互连网络，常用于共享存储器和分布式存储器多处理机系统中。在 动态互连网络中，各结点之间不是直接固定连接的，而是在控制信号的作用下， 通过网络开关的设置来建立结点之间间接的、可变的连接通路。这种连接通路是 主动可扩的，常以一个独立部件的形式出现。交叉开关网、单级互连网和多级互 连网都属于动态互连网络。 交叉开关网的开关数是输入端和输出端的乘积，所以能实现任意结点之间的连 接，但硬件复杂性以平方数上升，造价太高，所以只适于规模小的系统。单级互 连网则是由一级开关组成的网络，也只能实现有限的集中基本连接。顾名思义， 多级互连网就是把多套相同的或者不同的单级互连网串联起来，从而实现更多的 中国科学技术大学硕士论文 连接。 第2 节多级互连网的结构 多级互连网是在空间上重复设置多套单级互连网，单级网络之间采用固定的连 接模式串联，通过动态设置各级开关的状态来实现输入输出结点之间的连接。因 此，首先介绍两种互连函数，它们常用作多级互连网的连接模式。 1 2 1互连函数 互连网络的一个重要特性是连接模式，它反映了网络输入端到输出端的连接能 力。为了说明这一特性，每一种互连网络都可以用一组互连函数来表示他每一级 之间的连接模式。下面简单介绍两种常用的互连函数。 1 ) 均匀洗牌置换 均匀洗牌置换是将输入端的二进制地址循环左移一位，得到输出端的二进制地 址。其函数表达式为：o ( x 。x 。- 2 x l x 。) = x n - 2 x 。x o x 。常用于n 网等多级互连 网的组成。 另外，洗牌置换还包括子洗牌、超洗牌和逆均匀洗牌置换。子洗牌置换是指输 入端二进制地址的第o ，k l 位进行洗牌，其他位地址不变。其函数表达式为： o 怔) ( x n l x k + l x k x k l x o ) = x n l a k + l x k 1 x 0 x k ， o k n - l 。 超洗牌置换与子洗牌置换相反，是指输入端二进制地址的第n k 一1 ，n 一1 位进 行洗牌，其他位地址不变。其函数表达式为： d 啦) ( x n 4 x 一2 x n _ k - 1 x 卜弛_ l x o ) = x n 一2 x n h x 一l x n 一2 x o ， o s k n l 。 逆均匀洗牌置换则是指将输入端二进制地址编号循环右移一位，得到输出端地 址。其函数表达式为：a ( - 1 ) ( x 。x 。x 。) = x o x 。x ，。图1 1 是这四种洗牌置换的例 子。 中国科学技术大学硕士论文 ( a ) o 置换 ( b ) 0 0 ) i 换 图1 1 oo 11 22 33 44 55 66 77 ( c ) o o ) 置换( d ) o r ( 一t ) 2 t 9 n = 8 的各种洗牌置换 2 ) 蝶式置换 蝶式置换是将输入端二进制地址的最高位和最低位互换位置，其他位地址不 变，得到相应输出端的二进制地址。其函数表达式为： 口( x n _ x n 一2 x 1 x o ) = x 0 x n 一2 - x i x n 一1 。 与洗牌置换一样，蝶式置换也可分为子蝶式置换和超蝶式置换。予蝶式置换是 把第k 位和最低位互换位置，函数表达式为： 卢“、g n - l 屯十1 z i ，k _ 1 x i x 0 ) = 工n 一1 x k + 1 x t ) x k - 1 x 1 z k ，0 k n - i 。 超蝶式置换则是将第n k 一1 位与最高位互换位置，其他位地址不变，其函数 表达式为： 声o g 。_ x n _ 2 一x n 。x n l - 1 x n t _ 2 ) = _ l 2 工。 _ z 。一t 一2 ，o sk n 一1 。 蝶式置换用于b a n y a n 网的构成。 0 l 2 3 4 5 6 7 ( a ) 1 3 置换 0 1 2 3 4 5 6 7 o 1 2 3 4 7 0 1 2 3 4 5 6 7 o 1 2 3 4 5 6 7 o l 2 3 4 5 6 7 ( b ) 1 3 0 ) t t 换 ( c ) b q ) 置换 图1 2n = 8 的各种骤式置换 中国科学技术大学硕士论文 1 2 2多级互连网 上一节讲的两种互连函数可直接构成单级互连网，但单级互连网只能实现有限 的几种基本连接方式，不能满足目前并行系统高通信的要求。因此，为了构筑大 型开关网络，将单级互连网级联起来，得到一个多级互连网 2 ，可用于h i m d 和 s i m d 并行机等。通过动态设置开关状态，多级互连网能够实现输入和输出之间建 立所需的连接，比单级互连网的连接能力强。 第3 节多级互连网的分类 由于所使用的开关元件、连接模式以及控制方式的不同，多级互连网可分为 各种各样的类型。从网络的连接能力来看，多级互连网大致可以分为两类：阻塞 网和非阻塞网。下面分别介绍这两类网络。 1 3 1多级阻塞网 1 ) 阻塞网的概念 阻塞网是指一对以上输入端和输出端可同时实现连接的网络，但是网络中有可 能出现路径冲突。各种阻塞网都能实现一些典型互连函数的映射，但不能实现任 意的函数置换。由于这类网络所用开关少，延时也不长，路径控制比较简单，又 能实现并行处理中许多常用的置换函数，所以在实际系统中使用广泛。常用的多 级阻塞网有n 网 3 、b a n y a n 网 4 、间接二进制网 5 等。 阻塞网的控制方式是指网络中各级开关的控制方式，一般有三种：级控制、单 元控制和部分级控制。级控制是指同一级开关用一个信号来控制。单元控制则是 指网络中的每一个开关都有单独的控制信号，所以同一级的开关也可以处于不同 的工作状态。部分级控制则介于两者之间。 2 ) 各种阻塞网之间的拓扑关系 根据所用开关模式、互连函数和控制方式的不同，阻塞网又可分为n 网、b a n y a n 网、间接二进制网等多种网络。这些网络虽然结构各不相同，但是有一定的拓扑 关系。 中国科学技术大学硕士论文 两个网络拓扑等价是指，对于其中一个网络，存在一个逻辑名结构，使得它带 有逻辑名连线的连接关系可以用另一个网络的拓扑描述规则来描述。所谓的拓扑 描述规则是指，描述不同级开关元件之间连接模式的一组数据规则，这可以从网 络的具体结构直接导出。在拓扑同构网络之间，可通过重新命名网络输入、输出 端，使得一种网络的连接能力完全等价于另一种网络。 骥攀囊 ( a ) n 网( b ) b a s e l i n e 网( c ) b a n y a n 网 图1 3n 网、b a n y a n 网、b a s e l i n e 网之间的拓扑等价关系( n = 8 ) 为了研究这种拓扑关系，w u 和f e n g 6 7 】引入了一个基准网络( b a s e l i n e 网) 作为比较其他各种多级阻塞网的参考。如果每种网络都能与这个b a s e l i n e 网等价， 那么它们之间也是互相等价的。例如，n 网、b a n y a n 网和b a s e l i n e 网都是拓扑同 构的网络，如图1 3 所示。类似的可以证明：n 网、b a n y a n 网、间接二进制网， 以及相应的各种逆网络都是拓扑等价的 1 。 1 3 2 多级非阻塞网络 阻塞网在连接两个以上的终端对时，可能会产生冲突。顾名思义，非阻塞网就 可以避免这种冲突的情况。首先我们介绍一般连接系统 2 】的概念，如图1 4 所示， 一般连接系统有一组端头、控制单元和连接网络三部分组成。 图1 4 一般连接系统的模型 中国科学技术大学硕士论文 图中，控制单元专门负责处理输入输出端口之间的连接请求；然后通过连接网 络建立这些连接。连接网络具有三种组合特性：可重排性、广义的非阻塞性和狭 义的非阻塞性。对于一个多级互连网络，如果通过重新排列现有的连接，就能处 理所有新的终端对连接请求，则称这个网为可重排非阻塞网，例如b e n e s 网 81 。 如果不需要改变现有的连接，但必须按一定的规则才能实现新的连接请求，则称 之为广义的非阻塞网。如果不管网络处于什么状态，任意选用目前可用的链路就 能实现所有新的连接请求，则称之为狭义的非阻塞网，例如交叉开关。下面分别 介绍这三种非阻塞网。 1 ) 可重排非阻塞网 可重排非阻塞网络的定义是：如果重新安排现有的连接，便可实现无阻塞的任 意端点对的连接，从而能实现一个新的端点对的连接请求。可重排网的连接能力 比阻塞网要强，但因此硬件代价以及路径控制算法的复杂度也都要比阻塞网大。 b e n e s 网 8 是一种重要的可重排非阻塞网，使用g g 开关，结构如图1 jf 。t ) 所示。当q = 2 时，b e n e s 网可以看成b a s e l i l i e 网和b a s e l i n e “网拼接而成，如 图1 5 ( b ) 。类似的，用其他阻塞网也可以构造出可重排非阻塞网，如q q 网 9 j 和q q 网 1 0 ，将在下一章详细介绍。 ( a ) b e n e s 网的一般结构( 使用g 。g 开关) 中国科学技术大学硕士论文 ( b ) n = 8 ，q = 2 的b e n e s 网 图1 5b e n e s 网的结构 可重排非阻塞网的开关控制算法比阻塞网复杂，有循环控制法、改进的终端标 记法、方阵分解法、并行设置法和递归分治法等。下面介绍用于b e n e s 网的循环 控制算法，该算法的基本思想是先给出输入输出置换关系图，然后从某一个输入 端起，按照其对应置换关系进行循环，直到终点为止。这样便得到输入、输出两 端开关的状态，递归下去，直到得出所有开关的状态，参见第2 章第3 节。 2 ) 狭义和广义的非阻塞网 这里的非阻塞网是指，不必改变网络中原来的输入端和输出端置换的开关状 态，便可实现任意输入端和输出端直接的连接请求。与可重排非阻塞网不同，对 于网络中新的连接请求，多级非阻塞网不需要改变网络里原来的连接路径，就能 实现新的连接。 狭义的非阻塞网的约束性很强，它要求：使用任意一条当前未被占用的链路 就能实现所有可能的、新的终端对连接请求。n n 的交叉开关就是一种狭义的非 阻塞网，但硬件代价太大，需要2 个2 2 开关。 i l l1 6 三级c l o s 网c ，n ，) 咖 m 中国科学技术大学硕士论文 为了降低硬件代价，c 1o s 1 1 提出了一类非阻塞网络c ( m ”，r ) ，如图1 6 所 示。根据参数坍， ，的不同，c l o s 网的组合特性也不尽相同。当中间级开关 数m 满足m 时，c ( m ，”，r 1 就是可重排非阻塞网。例如上一节中， 7 = 2 ”的b e n e s 网是一种可重排非阻塞网，它其实是从形如c ( 2 ，2 ，2 “) 的c 1 0 s 网递归构造而成， 即重复使用c l o s 网的结构c ( 2 ，2 ，2 ) ，c ( 2 ，2 ，2 ”! ) ，直到所有的开关都是 一个2 2 的基本开关元件的c ( 2 ，2 ，2 ) 蔓j j j 2 。 当m = 行时，如果中间级开关数埘满足m 2 n l 时，这个c 1 0 s 网就是狭义的 非阻塞网 2 。当埘o ( n l o gr l o g l o gr ) ，c b ，”，r ) 是一个广义的非阻塞网，即可 以不改变网络中原有的连接，但要按一定的规则从目前尚未使用的链路中选路， 才能实现新的连接请求 1 2 。关于这个网络上多播问题的研究，我们已经发表了 一些文章，参见 1 3 1 4 。 第4 节多级互连网及其多播问题的研究现状 上面介绍的各种多级互连网，特别是阻塞网及其构成的可重排非阻塞网，由于 其结构整齐、路由算法简单，在并行分布式系统中得到了广泛应用，这方面目前 也有很多相关研究成果。首先介绍一下多级互连网中常用的几种连接请求。 1 4 1 多级互连网中的连接请求 在并行分布环境中，各处理器之间经常用到散布( s c a t t e r ) 、集中( c 0 1 1e cl ) 等各种通信方式。当多级互连网用于并行环境中的时候，这些通信就要通过网络 中的各种连接请求来实现。图1 7 是常用的三种连接请求方式。 舞挝瓣 ( a ) 置换( b ) 多播 ( c ) 多个多播 图1 7多级互连网中的连接请求 中国科学技术大学硕士论文 4 一个“单播”是指一个端口播送到一个端口的操作，“置换”则是指个互不 相干的单播，其中是网络中端口的个数。一个“多播”是指由一个端口播送到n 个端口g 1 ) 的操作，是单播0 = 1 ) 的一般形式。如果两个多播有相同的目的地址， 则它们必定在输出端冲突，这时就需要输出端口用一定的策略来解决这种冲突， 而不是靠网络中的路由算法就能解决的。本文只是研究多播在网络中的路由问题， 所以不涉及这种冲突；因此文中讲到的多播，没有特殊说明，都是指目的地址互 不相同的多播操作，如图1 7 ( c ) 所示。 由图1 7 中可以看出，( a ) 和( b ) 其实都是( c ) 的特殊形式。因此能实现多 个多播的网络，必然也能实现置换。所以对多个多播的研究才是多级互连网中通 信问题的一般化问题，也是最复杂的一类。可是，目前对各种网络的研究都仅限 于置换操作。下面介绍置换网的概念。 1 4 2 置换网的概念 置换网是指可以无阻塞的实现所有置换方式的多级互连网，如上面讲的b e n e s 网 8 ，下一章要介绍的q + n 网 9 、q x n 网 1 0 和简化的q x n 网都属于这种 网络。这是目前研究很多的一种多级互连网，因为它硬件代价与阻塞网相同 ( o ( l o gn ) ) 、路由算法简单，并且连接能力较强( 可以实现任意置换方式) 。 f e n g 在 9 】中根据n 网上置换操作必须满足的某些条件，提出了n - x 0 网上 的一种置换算法( i n s i d e o u t 算法) ，经过对置换的转换，可以用于n + n 网上的 置换。 m a 和f e n g 在 1 0 】中又针对n 0 网，提出了一种新的置换算法，时间复杂度 是d ( l o g n ) 。 h a n s o n 在【1 5 中提出b e n e s 网上一种代价最优的置换算法，时间复杂度是 d ( l o g n ) ，在p 个处理器构成的并行机上( 1 p s n l o g n ) ，可以在 o ( n l o g nip ) 的时间内完成。该算法同样适用于与b e n e s 拓扑等价的网络，如简 化的q 呶q 网等。 我们对这些典型的置换算法进行了详尽的描述，从理论方面分析了算法的正确 中国科学技术大学硕士论文 性。并给出了相应的计算机模拟实验。参见第二章。 这些置换网络都和阻塞网有相同的硬件代价( d ( l o g n ) ) ，但连接能力远远 强于阻塞网，且路由算法简单易实现，所以得到广泛的应用和研究。然而随着并 行系统中处理器数目和问题规模的增加，多播操作得到越来越多的应用；因此， 多级互连网中多播问题的研究也变得越来越重要，这也正是本文的研究重点。 1 4 3多播问题的研究和思考 1 ) 现有网络上的多播 一般而言，阻塞网不能实现任意的多播。但是由于网络结构的特点，通常可以 实现满足某种条件的多播。例如，l e e 在 1 9 中提出：b a n y a n 卜”网本身是一个阻 塞网，但若满足条件：源点地址连续且相应的目的地址有序( 升序或降序) ，则可 以无冲突的同时播送。 这个性质主要是由b a n y a n 卜”网本身的连接模式和路由算法决定的，并不是所 有与之拓扑等价的网都具有这种性质。例如，b a s e l i n e 网和i n c u b e 网 2 就没有 这种性质，但我们证明了n 网也具有这种性质( 参见本文第3 章) o 置换网可以实现所有的置换，但是对多播的支持性能并不是很好。因为一般对 多播的路由都是通过把多播分解成若干个单播，再用置换算法实现。当一个多播 的目的地址很多，源地址较少的时候，就需要多次调用置换算法，且每次的置换 只用到很少的一部分，这显然是一种很不理想的解决方法。 2 ) “多播网”的提出 随着并行分布式系统中处理器数目和并行问题规模的增加，对多播操作的需求 也越来越大；然而现有网络对多播的支持性并不是很理想。因此，专门为多播构 造的多级互连网“多播网”，也得到了越来越多的关注。y a n g 在 1 7 中针对多 个多播的并发提出了一种新的自路由多播网络，需要o ( n l 0 9 2n ) 的开关元件数， 这个硬件复杂度比较大，并且网络本身的构造很复杂，也不利于集成。 c l o s 网也可以有效的实现多个多播，我们也针对这个问题进行了研究，参见 1 3 1 1 4 1 。但由于c l o s 网本身作为非阻塞网的硬件代价很大 中国科学技术大学硕士论文 ( o ( n l o g r l o g l o g r ) ) ，所以虽然我们把c l o s 网上的路由算法时间复杂度降 低至 ( ( 石黠) 2 l o gn ) ，但硬件代价仍然无法得到太大的改善 12 l 3 ) 我们的思考 从上面两点可以看出，专门的多播网络往往硬件代价太高；而现有的多级互连 网对多播的支持效果又不好。因此，要用尽可能少的硬件代价，在尽可能短的时 间内，实现多播，这就是本文的基本出发点。 上一节讲的置换网就是用与阻塞网相同的硬件代价( o ( nl o gn ) ) ，通过简单 的路由算法( o ( n l o g n ) ) ，实现了所有的置换操作。于是，我们考虑是否能用与 置换网相同的硬件代价，以及和置换路由算法相同的时间复杂度，来实现任意多 播操作。通过对各种阻塞网和置换网现有成果的研究，我们发现q 网的网络结构 很利于这种多播网络的构造，这正是本文的主要研究内容。 本文后面的章节如下安排：第2 章介绍并分析q 网上已有的一些研究成果，包 括q 网本身的结构和路由，以及基于q 网结构的置换网和相应的置换算法：第3 章介绍。网上无冲突多播的性质，并给出证明：第4 章介绍基于q 网结构的多播 网，并提出一类新的多播网络模型，为多播问题的研究提供了一个参考方案；第j 章是总结和展望。 中国科学技术大学硕士论文 第2 章基于q 网的置换网 第1 章中提到的q 网是一种阻塞网，由于其结构利于硬件集成且连接能力较 强，得到了广泛的应用 3 1 。n 网本身并不能实现所有的置换，但是由n 网和相应 的n 一网就可以构造出一些置换网，例如n + n 网 9 、n n 网 1 0 】和简化的n 一1 n 网等。这一章着重介绍这三种网络的网络结构和相应的置换算法，从理论方面 分析了算法的正确性，并给出了相应的计算机模拟实验。 首先，对n 网进行简单的介绍。n 网【3 是一种阻塞型多级互连网，又称为多 级洗牌交换网络，由n = l o g n 级开关组成，每级由n 2 个4 功能的2 x 2 开关组成， 开关的四个功能分别为直通、交换、上播、下播，如图2 1 所示。 爿三# 爿孓爿孓爿孕 ( a ) 直通( b ) 交换( c ) 上播( d ) 下播 图2 , 14 功能开关的连接状态 因此，整个网络的开关数为芸1 0 9 ，其中n 为输入输出端1 3 数。级数的编排 从输入端到输出端依次为0 一n 一1 ，每一级的连接模式依次为c 。c 。，其中 g e 一。为洗牌交换仃，g 为恒等置换。对连接请求，q 网采用单元控制方式， 使用终端标记控制的路径算法。这是一种自路由策略，基本思想是第k 级的每个 开关的状态，由其输入端连接请求的目的地址的第k 位决定( n 一1 k 0 ) ：为0 则播往上输出端，为1 则播往下输出端。图2 2 是该路径控制的一个例子。 0 0 l 输 o l l 入 端 输 1 0 0 出 1 0 1端 图2 2n 网的终端标记控制算法 中国科学技术大学硕士论文 每一对源点和目的点之间的连接路径由目的地址唯一决定，不能保证多个单 播并发时不发生冲突，因此n 网是一种阻塞网。上图中，0 0 1 1 0 0 和0 1 1 1 0 0 两个连接请求就在第1 级的开关上产生了冲突。所以，n 网不能实现所有的连接 请求，但可以实现以下各种函数置换： ( 1 ) 恒等置换：，b ) = x ，0 s x n l 。 ( 2 ) 按c 序散播加距离为d 的移数置换：f ( x ) = c x + b ，o 1 6 的网络。 第2 节q q 网 q q 网 1 0 1 也是由两个n 网连接而成，但是这两个n 网中间一级的连接模 式与n + n 网的直连不同。为了描述这一级的连接模式，我们首先介绍一下 7 中 x 寸2 l o g n 级网络提出的“标记方案”。对一个2 1 0 9 n 级的网络来说，从外向内对 它的每一级进行分层：第1 级和第2 l o g n ( 最后一级) 是第1 “层”；第2 级和第 2 1 0 9 n 一1 级是第二层；第l o g n 级和第l o g n + 1 级是第l o g n 层。从第2 层 开始，对每一层根据前面一层的标记进行标记。设第i 层的某个开关标记为 工。z 。，它的上( 下) 输出端连接第f + l 层的某个开关，则开关标记为z 。0 ( x i r 1o 下图是两个n 网组成的2 l o g n ( n = 1 6 ) 级的网络执行该标记方案后 的结果。 o oo o oo o oo o 图2 7n = 1 6 的n x n 网 对网络进行标记之后，把第1 0 9 级的编号为呱2 、l 版坟。的两个开关， 和第l o g n 级与之编号相同的两个开关，用一个蝶式置换连接起来，就得到了n q 网，如上图所示。 m a 在【1 0 中针对这一类q q 网，根据 7 】中提出的标记方案，设计了一种新 o ， 2 3 4 s 6 7 a 9 m坦竹倦 中国科学技术大学硕士论文 的置换算法，时间复杂度为o ( nl o gn ) 。下面给出该算法的形式化描述。 算法2 2 ( n n ) 【1 0 】 p n ：置换数组。 m i n n 2 ，2 o g n ：存放2 1 0 9 n 级开关状态的数组。 d n 1 。d n 】：存放决定表分别到行和列的投影的数组。 d r o w n ：存放决定表行标记的数组。 d c o li n ： 存放决定表列标记的数组。 p r o c e d u r er o u t e 2i o g n ( ) ( d r o w - o ，n 一1 ； d r o w - 【0 ，n l 】； 设置第一层开关 f o r ( i = 0 ；i n 2 ；i + + ) ( 把输入端的偶数开关状态设置为与决定表相反，其他开关不变。 i f ( i 2 = = 0 】( m 啉b ，o 】- i - d 2 i ； 心艮2 1 0 9 n l 】pd 2 i 】； ) e l s e ( m 时艮o - d 2 i 】； m 阱6 2 1 0 9 n 1 _ d 7 2 i 】； ) 根据第一级路由结果，设置新的d r o w 和d c o l ； f o r ( j = 1 ；j ”的时候，a 、。 中任意个连续的列向量都构成一个n 维的置换矩 阵。 因此，当k = 时，置换矩阵( 例如b 。，i 、。和r 、。) 和平衡矩阵是等价 的。 定义2 2 1 5 ：矩阵a 的完全匹配图p g 。是指：p g 。中的顶点v ，和v ，相邻，当且 仪当a 的第f 亍和第行相等( a i - a j j ) 。 完全匹配图的概念将在下面求列向量x 的算法中用到。 引理2 4 1 1 5 ：对于平衡矩阵a 。和b 。，存在一个维列向量x ，使得矩阵 a ! 。x 和矩阵 b 2 。x 仍是平衡矩阵。该引理保证了算法2 3 的第i 步和第2 步 的正确性。 i 5 中并没有给出该引理的详细证明，下面我们给出具体的证明过程。 证明：先构造一个算法 1 5 求出列向量x ，并通过证明该算法是正确的，从而得 出这个引理的正确性。 算法2 4 ( c o l u r 州) 1 5 3 输入：置换矩阵爿。和b 。 输出：列向量x ，使得矩阵j = 【爿：。x 和矩阵占= 【垦。x 仍是平衡矩阵。 第1 步：求出a ，。( b 。) 的也, 置挟，炬晔以。- i ( b 。- i ) ，即矩阵a 。- * 表示 的置换是4 ，。表示的置换的逆置换。 第2 步：把彳：的每一行彳二 ) 看作图的一个顶点”( o 七一1 ) ，通过把 标号为爿一陆】和彳一 尼+ 譬 的两个顶点连线使之成为相邻顶点 璺型兰垫查查兰堕主兰壅二! 生 ( 0 k 芸一1 ) ，构造出图g 。类似的，构造图g 。 2 第3 步：将上一步得到的两个图g 。，g 。合并起来得到图u ，并对图u 进行 2 - 着色( 0 色和l 色) 。指派给顶点k 的颜色值就是列向量x k l 的值， 0 茎k n l 。 下面证明该算法的正确性。 首先，证明用第2 步中的方法构造出的图g 。( g 。) ，就是矩阵a “( b “) 的 完全匹配图，g 屯，( j ! ) g 既) 。设彳：! ， ) = f ，爿：。f + 警 = ，其中。女s 等一i 。则 爿d 】_ t ，爿【，】_ + i n ，即仅4 p 和爿口】的最高位不同；由置换矩阵的定义，爿p 和 彳阴仅在第1 列不同。因此，爿：。p 和4 ，。d 】是完全相同的，则p g 屯，中顶点弭口顶 点，相邻且仅与之相邻。而根据算法2 4 构造的图g 。中，顶点i 和顶点i 也是相邻 的，且仅与之相邻。因此，g 。就是p g 。，。类似的，可以证明g 。就是p g 。 其次，证明第3 步中对图u 的2 - 着色是可以进行的。由于图g 】和g 。的顶点 集都是相同的 o ，1 ，n 1 集合，所以图u 的顶点集也是0 ，1 ，a _ 1j ， 且u 中的边集合是g 。和g 。的边集合的并集，设g 。中的任意一个顶点i 与另一个 顶点，相邻( 且仅与之相邻) ，g 。中的该顶点i 与另一个顶点k 相邻f 且仅与之相 邻) ，则在图u 中，顶点i 仅与顶点，和顶点k 相邻。由此得知：图u 中的任意 个顶点仅与另外两个顶点相邻，且这两条边中，一条属于g 。，另一条属于g 一 推广至图u 中的任意一个连通分量中，有一半的边属于图g 。，另外一半的边属于 图g 。，所以该连通分量一共有偶数条边，因此，它是可以被2 - 着色的。所以，算 法第3 步中对图u 的2 一着色是可以完成的。 最后，证明第3 步得到的x ，使得彳= 爿：，x 】和矩阵百= 岛。，x 仍是平衡矩阵， 即彳【f 】j 阴且占 f 】百阴，f ，。用反证法，假设存在某个f ，使得j 【f 】= j ， 则必有爿：。 f 1 = 爿：。，】，那么在p g 札中顶点f 和顶点，是相邻的，所以经过2 - 着色， ! 里型兰垫查查兰堡主堕苎二! 生 顶点碍口顶点必定是不同的颜色，x h x b ，因此j p 】j d 】，与假设矛盾a 综上，我们证明了算法2 4 的正确性；因此，引理2 4 得证。 口 下面给出算法2 4 的一个例子。 例2 2 ：令a - = 1 6 ，对两个置换：h = ( o4 71 0 1 31 4 ) ( 12 ： ) ( jh 9 l l1 2 ) ( 6l j ) ，中= ( o367 ) ( 158 1 01 2 ) ( 249t 4 ) ( hl ： ) ( 1 5 ) ，相应的置 换矩阵a 、b ( 是平衡矩阵) ，如图2 9 ( a ) 所示。 解：用算法2 4 。 第l 步： n l = ( o1 41 3l o 74 ) ( 132 ) ( j1 21 l98 ) ( 61 j ) 中一i = ( o763 ) ( 11 2 1 085 ) ( 21 494 ) ( 1 113 ) ( 1 5 ) 第2 步：构造图g 。和g 。，如图2 9 ( b ) 。 第3 步：令图u = g 。ug ，并对u 进行2 - 着e ( o 色和l 色) ，如图2 1 ( c ) 。 得到列向量x ，如图2 9 ( d ) 。矩阵j = 爿二。z 和矩阵百= f b 。_ 】仍是 a = a ：。，x b = 最4 。 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 l l l l 0 0 1 0 0 0 0 l l 0 1 1 1 1 0 l l 1 0 0 0 1 0 1 0 1 l o o 0 0 0 0 1 1 0 1 ( a ) 原平衡矩阵( d ) 所求列向量 ( e ) 新平衡矩阵 洲吣洲舢 o ) 1 ，1 1 1 0 o o 1 0 1 0 o l 爿 洲眦咖川m删 i-一1。o。)、：14：-一1。1)、73。i。f。i-一ii。)。=，：l，。：ij：3：2二薹!：!：；t1-一1l(153)2：lt20 t1一-11(61)4)l：j1。i-1。-ii7 。)til9 1 0r ij：。 n 一1 ( 8 卜i兀一1 ( 9 ) 8 n 一1 ( 1 0 ) ：7 兀一丌一l ( l 2 ) = l l ：j 兀一l l j ) 6 。一- o ) 二? 中- | 4 1 ) 1 2 。一( 2 ) 叫。一1 l 3 ) ”o 中；“) 2。l ( j ) “l m 一6 ) 中l r l 6 一c u a 一鹕叶叫 奄p 一还广。一还舱一o 0 ( c )进行2 一着色后的图u 图2 9算法2 4