（计算机系统结构专业论文）递归立方环的结构及多播算法研究.pdf

中国科学技术大学顼：l 学位论文递归立方环的结构及多播算法研究 致谢 在论文完成之际，首先感谢我的导师顾乃杰教授，没有他的悉心指导和帮助， 本文不可能顺利完成。在研究工作过程中，顾老师给了我极大的关怀和帮助：在 论文完成过程中，顾老师给了我许多鼓励和支持。顾老师治学严谨、思维敏捷、 学识渊博、坚持原则、以诚待人，无论是在治学态度还是在做人准则方面，都为 我树立了学习的典范。顾老师勤奋踏实的工作和诲人不倦的精神，使我永生难忘。 在此，谨向尊敬的导师致以深深的敬意和衷心的感谢。 其次我由衷地感谢在研究生学习阶段传授给我知识的陈国良、赵保华、杨寿 保、黄刘生、许胤龙、王煦法、陈恩红等老师，是他们用辛勤的汗水，培养我不 断成长进步，也要感谢系里的李胜柏、卢贤若、于天顺等老师在各方面的帮助和 指导。 感谢实验室的任丌新、谢晖、刘刚、刘小虎、张建明、刘勇、李婧、翟卫丰 等同学多年来的热心支持和帮助，很荣幸属于这个集体。特别感谢在论文完成之 际给了我很多帮助和建议的张建明同学，和他的讨论使得我对这个领域的概念更 加清晰，也促使了这篇论文的顺利完成。 同寝室的好兄弟杨洋、程克勤、牛晓松，感谢你们这三年来对我学习和生活 上的帮助，也要感谢好朋友虞震、王进、王秦辉，你们的存在使得我的研究生生 活更有意义和色彩。 最深的谢意献给我的父母和家人。 第l t 页 中国科学技术大学 i ! j 上学位论文 递归立方环的结构及多播算法研究 摘要 并行计算机设计的趋势是朝着可扩展的结构发展的，互连网作为并行计算机 的一个关键组成部分也必须是可扩展的。在现有的互连网结构中，超立方网络没 有固定的度；m e s h 网络的直径太长且带宽不能作最佳扩展：在多极互连网中， 由于在消息路由时处理中间级开关的需要，通常代价太高。 y u z h o n gs u n 在文献【5 】中提出了一种新的可扩展的互连网结构递归 立方环( r c r ) ，它是一种有着很好的拓扑特性的互连网结构。然而在对递归立 方环的结构及其递归构造过程的讨论中，我们发现目前r c r 上仍然存在着一些 问题，主要在于三个方面：1 ) 当参数r = l 时，递归立方环r c r ( k ，r ) 是一个非 连通图：2 ) s u n 在【5 】中对r c r 对剖宽度的定义不正确；3 ) r c r 的直径的 定义也存在着错误。在本论文中，我们对目前递归立方环上存在的上述问题给出 了详细的说明和论述，并针对递归立方环的对剖宽度和直径的定义给出了必要的 修正。 同时，基于目前已有的递归立方环上的单播和广播路由算法，本文中我们提 出了一个有效的多播路由算法，为了避免死锁，使用了虚拟通道( v i r t u a l c h a n n e l ) 1 2 1 1 7 1 1 8 1 技术。该算法的时间复杂度为o ( n + l m l ( 1 0 9 一l o g ，+ l _ ；1 ) ) ， l 二j 其中m 为多播组成员节点集。 关键词：互连网结构，递归立方环( r c r ) ，对剖宽度，网络直径，多播路由， 第2 页 中国科学技术大学硕士学位论文递归立方环的结构及多播算法研究 a b s t r a c t at r e n di np a r a l l e lc o m p u t e rd e s i g ni st o w a r d ss c a l a b l ea r c h i t e c t u r e a sak e y c o m p o n e n to fa n yp a r a l l e lc o m p m e r , t h ei n t e r c o r m e c t i o nn e t w o r k sm u s ta l s ob e s c a l a b l e a m o n gt h ec u r r e n ti n t e r c o n n e c t i o nn e t w o r k s ，t h eh y p e r c u b en e t w o r kh a sa l l t h ep r o p e r t i e sa b o v e ，e x c e p tf o rc o n s t a n td e g r e e ；t h em e s hn e t w o r k sh a v el o n g d i a m e t e ra n dt h eb a n d w i d t hd o s en o ts c a l eo p t i m a l l y ；i nm u l t i s t a g en e t w o n s ，i ti s a l w a y se x p e n s i v eb e c a u s eo ft h en e e dt oi m p l e m e n tt h em i d d l es w i t c h i n gn o d e sf o r r o u t i n gm e s s a g e s i n 5 ，y u z h o n gs u np r o p o s e dan e wf a m i l yo fs c a l a b l ei n t e r c o r m e c t i o nn e t w o r k t o p o l o g i e s ，n a m e dr e c u r s i v ec u b eo fr i n g s ( r c r ) ，w h i c hp o s s e s sm a n yd e s i r a b l e t o p o l o g i c a lp r o p e r t i e s h o w e v e r , w h e nd i s c u s s i n g t h et o p o l o g ya n dr e c u r s i v e e x p a n s i o no fr c rn e t w o r k ，w ef i n daf e wp r o b l e m se x i s t i n go ni t ，w h i c hi n c l u d e ：1 ) w h e nr = 1 ，r c r ( k ，r ，- ，) e v e ns h o w st ob ead i s c o n n e c t e dg r a p h ；2 ) t h ed e f i n i t i o no f b i s e c t i o nw i d t ho fr c rn e t w o r ki n 5 d o e s n ta p p l yt os o m ec a s e sv e r yw e l l ；3 ) t h e d e f i n i t i o no f d i a m e t e ro fr c rn e t w o ni sa l s oi n c o r r e c t i nt h i sp a p e r , w ed e s c r i b ea n d a n a l y z et h ea b o v ep r o b l e m se x i s t i n go nr c r n e t w o r ki nd e t a i la n dm a k es o m e n e c e s s a r ym o d i f i c a t i o n so nt h eb i s e c t i o nw i d t ha n dn e t w o r kd i a m e t e r m o r e o v e lb a s e do nt h ec u r r e n tu n i c a s ta n db r o a d c a s tr o u t i n ga l g o r i t h m so nr c r n e t w o r k ，w ep r e s e n ta ne f f i c i e n tm u l t i c a s ta l g o r i t h m si nt h i sp a p e lt oa v o i dd e a d l o c k ， w eu s ev i r t u a lc h a n n e l 【2 】， 1 7 “1 8 】t e c h n i q u e t i m ec o m p l e x i t yo f t h ea l g o r i t h mi s 。( 州研( 1 0 9 n - 1 。”卧) ，w h e r em i s t h e n o d es e t o f m u l i i c a s tg m u p k e y w o r d s ：i n t e r c o n n e c t i o nn e t w o r kt o p o l o g y , r e c u r s i v ec u b eo fr i n g s ( r c r ) ， b i s e c t i o nw i d t h ，n e t w o nd i a m e t e r , m u l t i c a s tr o u t i n g 第3 页 中国科学技术大学碳：e 学位论文递归立方环的结构及多撬算法研究 第1 章引言 互连网是并行计算机的一个主要组成部分，能够有效的实现系统内部处理器 等功能部件之间相互的通信，对并行处理机的性能影响很大。传统的并行机互连 网络，主要是进行处理器、存储器和i o 设备之间的互连，包括静态互连网络和 动态互连网络。机群作为现代并行机系统的一种重要类型，其互连网络主要连接 诸独立的完整的计算机节点，通常是采用高速商用网络，如快速以太网、a t m 等。这一章主要介绍互连网的概念、结构和分类等基础背景知识，以及网络上单 播，多播等各种通信操作问题的研究现状，并提出本文的思考方向。 1 1 互连网络及其分类 并行计算机设计的趋势是朝着可扩展的结构发展的【1 】，可扩展的结构可通 过改善一个计算机系统硬件和软件资源来满足日益增长的用户需求。并行计算机 的一种很常见的结构是由多个节点构成的，这些节点通过一个互连网络相连，如 图1 1 所示。每个节点包含有一个通用处理器( c o m m o d i t y p r o c e s s o r ) ，该处理 器通过一个定制外部电路( c u s t o ms h e l lc i r c u i t r y ) 与本地存储器和网络接口电 路n i c ( n e t w o r ki n t e r f a c ec i r c u i t ) 相连，每个节点也可以有本地磁盘单元。 互连网络是由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实 现并行系统内部多个处理机或多个功能部件之问的相互连接。互联网络有三大要 素：连接模式( 互连拓扑) 、开关元件和控制方式，这三种要素的不同，决定了 互连网络的不同。从几何形状看，互连网络可分为规则网和不规则网两大类，其 中规则网又分为静态网和动态网两种。 静态网又称直接互连网，是指处理单元间有着固定连接的一类网络，网中节 点是直接相连的，在程序执行期问，这利t 点到点的连接保持不变。典型的静态网 络有环形网( r i n g ) 、网格形网络( m e s h ) 、立方体网络( c u b e ) 以及立方环网 络( c u b e & r i n g s ) 等。这种网络一旦构成以后就固定不变了，比较适合于构成 通信模式可预测的并行处理系统和分布式计算机系统。 第6 页 中国科学技术大学坝土学位论文 递归立方环的结构及多捕算法研究 图1 1 并行计算机的一种常见结构 动态网又称间接互连网，是由交换开关构成的，为了达到多用或通用的目的， 根据应用程序的要求动态地改变连接组态，实现各种通信模式的互连网络，常用 于共享存储器和分布式存储器多处理机系统中。在动态互连网络中，各节点之间 不是直接固定连接的，而是在控制信号的作用下，通过网络开关的设置来建立节 点之间间接的、可变的连接通路。这种连接通路是主动可扩的，常以一个独立部 件的形式出现。总线、交叉开关网和多级互连网都属于动态互连网络。 1 2 静态互连网络 本论文研究的是上述的静态互连网络以及相关网络上的通信策略。在对互连 网结构的讨论中，为讨论方便，有如下定义【2 】： 定义1 1 ：射入或射出一个节点的边数称为节点度( n o d ed e g r e e ) 。在单向网络 中，入射和出射边之和称为节点度。 定义1 2 ：网络中任何两个节点之间最短距离的最大值，即最大路径数，称为网 络直径( n e t w o r kd i a m e t e r ) 。 定义1 3 ：如果从任一节点观看网络都一样，则称网络为对称的( s y m m e t r y ) 。 第7 页 中国科学技术大学硕卜学位论文递归立方环的结构及多播算法研究 定义1 4 ：一个有n 个节点的网络的对剖平面( b i s e c t i o np l a n e ) 是一组连线，移 去它将把网络分为两个n 2 个节点的网络。一个网络可以有许多个对剖 平面。最小的对剖平面是指具有最小连线数的对剖平面。 定义1 5 ：对分网络各半所必须移去的最少边数称为对剖宽度( b i s e c t i o n w i d t h ) 。 令b 为穿越对剖平面的链路数，w 为每条链路的连线数( 也叫链路宽度或通 道宽度) ，那么乘积b w 就是对剖宽度，表示穿越对剖平面的总连线数。 互连网作为并行计算机的一个关键组成部分也必须是可扩展的，除了可扩展 性，互连网还应具有以下五种特性： 1 ) 对称性。从网络中的所有节点观看网络都是一样的，因此可以仅设计一个n i c 并复制到所有的节点上，路由算法也可以应用到所有的网络节点上。 2 ) 固定度数。任意一个节点的邻节点的个数应该是一个较小的常数，不随着网 络大小( 例如，所有的节点数) 的增长丽变大。这样才能保证互连网中的节 点不会随着网络大小的增长而改变节点中的网络接口。 3 ) 容错性。目前的大规模并行处理器可以扩展至上千个节点。因此，一些节点 或链接出错的可能性相对较高。系统其它部分仍然保持互连是很重要的。理 想的情形下，我们希望一个网络是最佳容错的，其中一个节点只有当它的所 有邻节点全出错时才从该网络中断开。 4 ) 较小的直径。一个网络的直径是所有成对节点之问晟短路径长度的最大值。 小直径有助于减少一些集体通讯操作之间的通讯延迟。理想情况下我们希望 得到一个c i o g n 的直径，其中c 是一个小的常数，是网络的大小，即节点 数。 5 ) 可扩展带宽。网络应该提供足够的带宽，且随着网络大小的增长而成比例增 加。一个用来衡量网络带宽能力的标准是其对剖宽度，即生成两个源网络一 半大小的子网所需删除的边的最小数目。为了提供可扩展带宽，对剖宽度应 与网络大小成比例。 1 2 1 几种典型的静态互连网络 典型的静态互连网有一维线性阵列、二维网孔、树连接、超立方网络、立方 第8 页 中圜科学技术大学硕士学位论文递归立方环的结构及多捕算法研究 环、洗牌交换网、蝶形网络等【2 】。 1 ) 一维线性阵列 一维线性阵列，( i - dl i n e a r a r r a y ) 是并行机中最简单、最基本的互连方式， 其中每个节点只与其左、右近邻相连，故也n q - 近邻连接，个节点用1 条 边串接之，内节点度为2 ，直径为j v 1 ，对剖宽度为1 。当首、尾节点相连时可 构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度 恒为2 ，直径或为l 2l ( 双向环) 或为1 ( 单向环) ，对剖宽度为2 。 2 ) 二维网孔 在一个4 - g v 的二维网孔( 2 dm e s h ) 中，每个节点只与其上、下、左、 右的近邻相连( 边界节点除外) ，故也称四近邻连接，因而节点度为4 ，网络直 径为2 ( 一1 ) ，对剖宽度为( 见图1 2 ( a ) ) 。如果在垂直方向上带环绕，而 水平方向呈蛇状，则2 一d 网孔就变成i l l i a c 网孔了( 见图1 2 ( b ) ) ，此时节点度恒 为4 ，网络直径为一1 ，而对剖宽度为2 。如果2 d 网孔的垂直和水平方 向均带环绕，则它就变成了2 - d 环绕( 2 dt o r u s ) ( 见图1 2 ( c ) ) ，其节点度恒为 4 ，而网络直径为2 4 - 万2i ，对剖宽度为2 万。 赫酵 _ ( ) _ _ ( _ 叫 ( a ) 2 一d 网孔( b ) 1 1 l l a c 网孔( c ) 2 - i ) 环绕 图1 2 四近邻连接 3 ) 树 二叉树除了根节点和叶节点之外，每个内节点只与其父节点和两个子节点相 连，故也称为三近邻连接。如图1 3 ( a ) 所示，显然节点度为3 ，对剖宽度为1 ， 而树的直径为2 矿l 。g n 7 一1 ) ( 为树的总节点数) 。为了减小直径，可使用x 一树， 笫9 页 中国科学技术大学硕士学位论文 递归立方环的结构及多捕算法研究 它将同级的兄弟节点彼此相连。如果尽量增大节点度为一1 ，则直径缩小为2 ， 此时就变成了如图1 3 ( b ) 所示的星形网络了，其对剖宽度为l n 2 j 。传统二叉树 的主要问题是根易成为通信瓶颈。1 9 8 5 年l e i s e r s o n 【3 】提出的胖树( f a tt r e e ) 可缓解此问题。如图1 3 ( c ) 所示，胖树节点间的通路自叶向根逐渐变宽，它更像 真实的树，连向根部的枝叉变得愈来愈粗。 4 ) 超立方 ( a ) 二叉树( b ) 星形连接 ( c ) 二叉斛树 图1 3 树型连接 ( a ) 3 - 立方( b ) 4 一立方 ( c ) 顶点代之以环( d ) 3 一立方环 图1 4 超立方网络 - 4 n 一立方由n = 2 ”个顶点组成，3 立方如图1 4 ( a ) 所示；4 一立方如图1 4 ( b ) 第1 0 页 中国科学技术大学硕士学位论文 递归立方环的结构及多播算法砷f 究 所示，由两个3 立方的对应顶点连接而成。月一立方的节点度为n ，网络直径也是 h ，而对割宽度为n 2 。由于该网络缺乏可扩放性并且不易构成多维超立方，所 以它正逐渐被其它的网络所代替。但过去在超立方上开发了很多优秀的算法，而 像二叉树，网孔和很多其它低维网络均能嵌入超立方中，所以超立方具有学术研 究的意义。 5 1 立方环( c u b eo f r i n g s ) 如果将3 一立方的每个顶点代之以一个环就构成了如图1 4 ( d ) 所示的3 立方 环，此时每个顶点的度为3 ，而不像超立方那样节点度为n 。立方环，简记之为 c o r ，它结合了环网和立方连接的优点及性质，在立方网络的每个顶点代之以一 个环，顾得名为带环的立方网络，简称为立方环。在此网络中，每个顶点的度为 3 ，从而与问题的规模无关。这一点对v l s i 的实现极为重要。一般而言，可以 从一个k 一立方构成一个具有行= 2 4 带环n a ( 每个顶点是k 个连成环的节点) 的k 立方环，此时k 一立方环中总共有n = k 2 。个节点( k 3 ) ，网络直径为 2 k i + l 七2 j ，而对剖宽度为( 2 】 ) 。 表1 静态互连网络特性一览表 网络名称网络规模节点度网络直径对剖宽度对称链路数 ( 节点数) 环形 2 2 j 2是 ( 双向) 2 d 网孔 慷万) 4 2 ( 一1 )商 非 2 ( n 一4 n i l l i a e 网孔 悔厨) 4_ n 一12 万 非 2 2 一d 环绕旧厢) 4 2 1 4 万2 j 2 厨 是 2 二叉树n3 2 l o g 一1 ) 1非一1 星形一12 l n 2 j 非 | v 一1 超立方n = 2 “nh2 是 n n ，2 立方环 n = k 2 3 2 k i + i l ，2 n ( 2 k ) 是3 2 第1 1 页 中国科学技术大学硕士学位论文 递归立方环的结构及多播算法研究 1 2 2 静态互连网络综合比较 表1 汇总了静态互连网络的重要特性。大多数网络的节点度都是一个小的常 数，这是比较理想的。随着选路技术的革新( 例如虫蚀选路) ，网络的直径变得 不那么重要了。对剖宽度会影响网络的带宽，网络的对称性与可扩放性和选路效 率有关( 注意表中对数以2 为底) 。 1 3 互连网及多播问题的研究现状 1 3 1 现有网络的拓扑特性 在现有的互连网中，超立方网络没有固定的度。事实上一个超立方网络的度 是l o g n ，且随着网络大小的增加而增大：m e s h 网络的直径太长( 2 - dm e s h 的直径是d ( 万) ，3 - dm e s h 的直径是o ( 河) ) 而且带宽不能作最佳扩展。例如， 一个2 dm e s h 的对剖宽度仅为，当节点数加倍时，对剖宽度只增加2 倍而 不是2 倍。 多级互连网有上述的全部五种特性。最重要的是，它的网络带宽可以随着其 网络规模的增长得到很好的扩展。但由于在消息路由时处理中间级开关的需要， 通常维护一个多级网络比起直接网络代价更高，并且在一个直接网络中，路由功 能可以被整合到n i c 当中。 因此，我们需要的是一个具有以上五种特性的可扩展直接网络。【4 】中提出 的立方环( c o r ) 网络则较好地在网络可扩展性和硬件代价之问提供了一个平衡。 一个立方环网络是将超立方中的每个节点代之以相同大小度数的环构造形成的， 如图l 4 ( d ) 所示为一个3 一立方环，它与立方连接环( c c c ) 6 1 的区别就在于确 定其每个节点立方邻节点的方式不同。立方环有固定的节点度数和小直径但是可 选的网络大小是很有限的。y u z h o n gs u n 在【5 】中提出的一种新的通过递归构 造形成的互连网拓扑结构递归立方环( r c r ) 则很好的解决了这一问题。 众所周知，一个给定拓扑的网络的实际规模与其目标网络的预期规模 是会有所不同的。比值就称之为匹配率。当匹配率越接近于1 ，我们就说 第1 2 页 中国科学技术大学硕士学位沦文 递归立方环的结构及多播算法研究 它越有好的规模匹配。一个h 立方，n 维立方连接环( c c c ) ，立方环( c o r ) 和递归立方环( r c r ) 的网络规模分别为2 4 ，n 2 4 ，2 ”和r 2 “，。与其它三种 网络拓扑相比，很显然递归立方环通过选取合适的参数r ，k 和，可以更好地匹 配一个给定的网络规模。例如，对于n 2 0 ，0 0 0 ，一个n 立方的网络规模当n = 1 4 时是1 6 ，3 8 4 ( n i n = o 8 2 ) ，当n = 1 5 时是3 2 ，7 6 8 ( = 1 ，6 4 ) 。通过选取合 适的参数r ，k 和_ ，可以构造出一个网络规模为1 8 ，4 2 2 ( n i n = o 9 2 ) 或2 0 ，4 8 0 ( = 1 0 2 ) 的递归立方环。很容易就可以证明在这个例子中递归立方环也 比立方连接环和立方环有更好的匹配率。 1 3 2 现有网络上的多播 在互连网结构和并行分稚式系统中，多播路由是更为常见和重要的消息路由 方式。m e s h 网络上的多播问题一直以来都是研究的热点所在，这方面的研究成 果也比较多1 7 1 【8 】 9 1 【1 0 1 【1 1 】。由于像二叉树，网孔和很多其它低维网络 均能嵌入超立方中，所以超立方也具有很大的学术研究意义，相继提出了许多优 秀的超立方网络上的多播算法【1 2 】【1 3 】【1 4 。 作为互连网络，由于m e s h 和超立方网络始终存在着拓扑特性上的不足之处， 因此我们把更多的目光投向了立方环网络和在此基础上通过递归构造形成的递 归立方环上。但目前在立方环和递归立方环上仅有单播或广播路由的算法【4 】 【5 】，还没有多播算法方面的成果。 1 3 3 我们的思考 基于以上两点的研究和分析，因此我们考虑了对递归立方环这利，新的互联网 拓扑结构的一些较好的拓扑特性的研究以及考虑如何在递归立方环上实现多播 路由。在对递归立方环的递归构造过程的讨论中，我们发现目前的递归立方环网 络中仍然存在着一些问题，主要是在三个方面：1 ) 当参数，= 1 时，递归立方环 r c r ( k ，_ ，) 是一个非连通图；2 ) s u n 在 5 1 中对r c r 对剖宽度的定义不正确； 3 ) r c r 的直径的定义也存在着错误。针对这些问题我们做了详细的阐述和分析， 第1 3 页 中国科学技术大学磺：k 学位论文递归立方环的结构技多播算法研究 并对其中的拓扑参数包括r c r 对剖宽度，网络直径做出了必要的修正，并在已 有的r c r 单播和广播路由算法的基础上，提出并分析了一个r c r 上的无死锁 ( d e a d l o c k f r e e ) 多播路由算法，这也正是本文的主要研究内容。 本文后面的章节如下安排：第2 章介绍了立方环和递归立方环的拓扑结构和 它们的一些较好的拓扑特性，以及递归立方环网络上现有的单播和广播路由通 讯：第3 章对递归立方环的递归构造进行了讨论，详细阐述并分析_ 了目前递归立 方环上仍然存在的一些问题，并对其中一些拓扑参数包括对剖宽度，网络直径做 出了修正：第4 章中基于目前已有的递归立方环上的单播和广播路由，提出了一 个无死锁多播路由算法，并对算法性能进行了对比分析；第5 章是总结和展望。 第1 4 页 中国科学技术大学硕士学位论文递归立方环的结构及多播算法研究 第2 章递归立方环 第1 章中提到在目前的互连网结构中，立方环( c o r ) 网络【4 】有较好的 拓扑特性，在网络可扩展性和硬件代价之间提供了一个平衡。然而也应看到虽然 立方环有固定的节点度数和小直径但是可选的网络大小有限。y u z h o n gs u n 在【5 】 中提出的一种新的通过递归构造形成的互连网拓扑结构递归立方环( r c r ) 则很好的解决了这一问题。本章中首先简单介绍立方环网络，然后重点介绍了递 归立方环的结构，递归构造过程以及它的一些较好的拓扑特性。 2 1 立方环网络( c o r ) 一个立方环网络可以表示为c o r ( k ，) ，定义为是一个m 维的超立方，且超 立方中包含有2 个由，个节点组成的环，其中m = k r ，k 是非负整数。换句话说， c o r ( 七，r ) 网络是由一个m 维超立方构成，其中2 “个超立方顶点中的每个顶点都 是，个节点组成的环。每个节点地址表示为l 4 ，b 】，包含有一个m 位的二进制数 和一个小于，的数的有序对：k 。a 。，b 】，其中口， o ，l ，0 j m 一1 ， b e o 1 ，r - 1 ) 。地址为i 爿，6 的节点( 最多) 与七十2 个节点相连，在这些相邻节 点中有七个立方邻节点，地址分别为k 。k ，6 】，k 。一c 2 b k 。棚。，b ， b 。瓦枷a 。，6 j 和最多两个环邻节点，地址为k 。，( 6 + 1 ) m o d r 】和 k 。口。，( 6 1 ) m o d r 】。当，= 2 时， 口，露。，( b + 1 ) m o d r - = k ，。一，( 6 1 ) m o d r ， 因此该节点只有一个环邻节点。当，= 1 时，每个环退化成仅有一个节点并且没有 任何环邻节点。图2 1 中显示的就是这样的两个网络。 立方环的拓扑是多样的，通过选取参数k 或r 的不同值，可以得到作为立方 环网络特殊情形的一系列现有的拓扑结构，如表2 中所示。 第1 5 页 中国科学技术大学硎二匕学位论文递归立方环的结构及多播算法研究 一c u b e e d g e _ - - - - 一r i n ge d e e ( b ) 图2 1 立方环网络：( a ) c o r ( 1 ，3 ) ，( b ) c o r ( 2 ，2 ) 立方环网络c o r ( k ，r ) 有如下性质： 4 1 1 ) 网络的大小定义成节点数，为n = r 2 “= r 2 “； 第1 6 页 中国科学技术大学硕一1 - - 学位论文 递归立方环的结构及多播算法研究 2 ) 网络是规则的，例如所有的节点都有相同的邻节点数，称为网络的节点度数； 3 ) 网络的度数d 为 j k + 2， 2 d = z l k + r 一1 r = 1 , 2 注意到当， 2 时，对于固定的k ，任意c o r ( k ，) 都有固定的度数，与网络 中的节点数无关： 4 ) 网络中的边数为e = 2 “r d ； 5 ) 网络的对剖宽度为b = 2 “1 ； 6 ) 任意的立方环网络c o r ( k ，r ) 是对称的； 7 ) 度数为d 的任意立方环网络c o r ( k ，r ) 容错度为d 一1 ，达到最佳容错性： 8 ) 对于七 o 且r 3 ，立方环c o r ( k ，r ) 的直径为d = 膏( r + 1 ) + r 1 2 j 一2 。 表2 立方环网络中的现有拓扑结构 c o r 网络 拓扑结构 c o r ( 0 ，r ) 环网络 c o r ( 1 ，) 立方连接环( c c c ) c o r ( k ，1 ) 超立方网络 综上所述，立方环网络c o r ( k ，) 显示了可扩展网络所应具有的五种特性： 对称性，最大的容错性，固定度数，对数级的直径以及可扩展带宽。但由于立方 环网络可选的网络大小有限，而【5 】中提出的递归立方环网络则很好的解决了 这一问题，因此接下来介绍这种新的可扩展的互连网结构递归立方环。 2 2 递归立方环( r c r ) y u z h o n gs u n 在文献【5 】中提出了一类新的可扩展的互连网结构递归 立方环。一个递归立方环网络r c r 是在一个给出的产生源( g s ) 上通过递归扩 展而生成的。用于生成r c r 的g s 是由一些以立方的形式互连起来的环构成的， 它根据某种标准例如网络的目标大小来创建。递归立方环在构建可扩展的并行机 第1 7 页 中国科学技术大学硕士学位论文 递归立方环的结构及多播算法研究 时有很多很好的拓扑特性，例如固定度数，小直径，高对剖宽度以及对称性。环 网络，超立方和立方连接环是r c r 的特殊形式。此外，r c r 还拥有平面特性， 一个r c r 网络中的每个节点都位于至少一个立方平面上，这一点与c o r 有所不 同。这个特性可以极大的简化路由算法的设计。 2 2 1 递归立方环的结构 递归立方环网络是由通过立方链接互连起来的环构成的，环内的节点由环链 接相连。一个递归立方环网络可表示为r c r ( k ， - ，) ，其中k 是立方的度，是一 个环上的节点数目，j 是从产生源扩展的次数。 s u n 在【5 】中定义了一个厂函数用于节点地址的表示和递归立方环特性的 分析。f 的定义在0 口b 的条件下与模操作有不同，定义如下： b - a o 口s 6 厂g ，6 2 i n l 詈j 6 口。 其中口 6 ， 在递归立方环中一个节点的地址详细表示为k ，。a 。，b ，其中 m = k + ，；口f 是一个二进制位，o i m 且o 6 ( c ) r c r ( 2 ，2 ，2 ) 根据给定的k 和n ，用n 表示网络中的预期节点数，n 表示实际生成的递 归立方环网络中的节点数，选取一个目标, t g r ，它反过来决定了j 的值，经过次 扩展可得到目标网络r c r ( k ，r ，) 。根据以下等式使得n 与n 最接近： 吲- n ”， 中国科学技术大学硕：仁学位论文递归立方环的结构及多播算法研究 图2 2 ( a ) 中是产生源g s ( 2 ，2 ) ；从产生源g s ( 2 ，2 ) 经过一次扩展后得到的 r c r ( 2 ，2 ，1 ) 如图2 2 ( b ) 所示：图2 2 ( c ) 中显示的是从r c r ( 2 ，2 ，1 ) 再经过一次扩展 后得到的r c r ( 2 ，2 ，2 ) 。每一次扩展过程中，网络中的节点数加倍且必须增加一些 新的立方链接。同时，为了保证节点度数不变，相应的必须删去一些立方链接。 i n p u t ：立方的度k 和要构造的网络中的预期节点数n ； o u t p u t ：递归立方环r c r ( k ，r ，- ，) ，且网络中实际节点数为。 p r o c e d u r e ： 1 选取参数尼，r ，- ，使得与最接近并构造g s ( k ，) ； 2 产将g 。和g 。初始化为g s ( k ，r ) + g 。( y ，e ) = g s ( k ，r ) ；g 。妒，e ) = a s ( k ，r ) ： 3 f o ri = 1 t oj d o 产分别在g 。和g 。中节点的立方地址部分的最高位添加一个0 位和1 位4 对g 。和g 。中的每个节点“和v ，扩展其地址d 。= 0 0 0 。) ；d ，= 0 1 0 。) ； 严取吼和瓯的并集生成下一较高序的r c r ，g 。 g = g l u g ： 产通过适当的链接插入和删除操作完成下一较高序r c r 的生成+ 在g 中插入和删除适当的立方链接，使得g 中每个地址为 k 。a 。“。，b 】的节点的k 个立方邻节点的地址分别为 【口，0 ( 。) 口。，6 j ，k ，。蚺。) a 。，b l ，k ，_ ，( 。扎。) a 。，6 j ， 其中，m = k + ，一1 ，1 z s k 。且g 中每个节点的环邻接关系保持不变。 。g l = g ；g 月= g ； 4 r c r ( k ，r ，) = g 。产生成目标网络r c r ( k ，_ ，) + 图2 3r c r 的递归构造算法【5 】 递归立方环r c r ( k ，r ，) 上的递归构造算法【5 】如图2 3 中所示。需要指出 的是，般情形下r c r 网络中的实际节点数可能会与预期网络中的节点数 不同。在图2 3 给出的递归构造算法中，对于一个节点地址为 d ，= k 。d 一，口。，h i = 口，b 】( 其中口，是一个二进制位，0 f 州) 的节点v ， 第2 0 页 中国科学技术大学硕士学位论文递归立方环的结构及多播算法研究 0 1 0 ，) = 1 a 。a 。n 。，6 】和0 0 0 ，) = o a 。n 。a 。，6 】分别是节点v 下一次扩展后的 地址，i 为当前扩展次数。在递归构造的一次操作中，将原有r c r ( k ，j 一1 ) 网 络( 在第一次扩展中，r c r ( 七，r ，_ ，一1 ) 即为产生源g s ) 复制，分别在这两个 r c r ( k ，j 一1 ) 中的所有节点的立方地址部分的最高位上添加一个0 地址位和1 地址位，并将它们节点的并集作为生成的r c r ( k ，r ，) 的节点集，r c r ( k ，) 中 所有节点之间的环链接关系保持不变，节点之间的立方链接关系由函数 f ( j x b + f ，+ k ) 确定，其中i = 1 ，k 。即在生成的r c r ( 七，) 中地址为 a m a i n _ 1 , a o , 6 】的节点的七个立方邻节点地址分别为k 卅a f ( j x b + 1 y , k ) - a o , 6 j ， b 。一，( 且6 + 。，+ ) 日o ，6 j ，k 。乃( 且6 + + t ) 口o ，b l ，其中m = k4 - j 一1 ，1 工k 。 例如，在扩展r c r ( 2 ，2 ，1 ) 生成r c r ( 2 ，2 ，2 ) 的过程中，r c r ( 2 ，2 ，1 ) 中的节点 o o o ，o 和节点 0 1 0 ，o 在r c r ( 2 ，2 ，2 ) 中分别扩展成了节点 o o o o ，o 和 o o l o ，0 ，r c r ( 2 ，2 ，1 ) 中的立方链接( o o o ，o 】 0 1 0 ，0 ) 在扩展生成r c r ( 2 ，2 ，2 ) 时删除，因此在扩展过程中 当节点 o o o o ，0 和 0 0 1 0 ，o 上分别增加了到节点 1 0 0 0 ，o 和 1 0 l o ，o 】的两条新的立 方链按时，节点 o o o o ，o 】和 o o l o ，o 仍然能保持固定的度数3 ，如图2 2 ( c ) 所示。 2 2 2 递归立方环的拓扑特性 前面已经提到，递归立方环在构建可扩展的并行机时有很多很好的拓扑特 性，例如固定度数，小直径，高对剖宽度以及对称性。 递归立方环r c r ( k ， ) 可以表示成一个图g = g 妒，e ) ，其中v ( a ) 中的一个 顶点对应于r c r 网络中的一个节点，并且e ( g ) 中的一条边对应于r c r 网络中 的一条链接。 【5 】中给出了递归立方环r c r ( k ，r ，) 的如下性质： 性质1 1 ：网络中的节点数为r 2 “。 性质1 2 ：r c r ( k ，r ，j ) 中p f i ：有的节点有相同的度数，并且当， 2 时度数为k + 2 ， 而当1 s ，2 时为k + r 一1 。 第2 1 页 中国科学技术大学硕士学位论文递归立方环的结构及多播算法研究 性质1 , 3 ：网络中边的数目e 为： e = r z + ，( - + 兰) r ： r ：“( 丢+ 圭) r = 2 ，2 k + 生 r = l 2 性质1 4 ：网络的对剖宽度b 为n u m ( k ，r ，j ) x 2 “川或n u m ( k ，r ，j ) r n ，其中n 是 网络的节点数，且n u m ( k ，) 定义如下：对于任意的自然数石和y ， 0 z sr 一1 且1 y ，n u m ( k ，r ，) 表示的是满足，o x + y ，j + ) = l 的石的值的数目。 性质1 1 ，1 2 ，1 3 从g s 的结构以及图7 中的r c r 递归构造算法可以很容 易得到，但是在对r c r 递归构造的讨论中，我们发现【5 】中给出的性质1 4 对 r c r 对剖宽度的定义有问题，这在本论文的第3 章中将会有具体的阐述并相应 提出了必要的修正。 对于递归立方环r c r ( k ，r ，) ，还有如下性质：【5 】 性质2 1 ：对于任意的r 和j ，r c r ( 0 ，r ，_ ，) 是环网络。 性质2 2 ：一个月维的超立方是r c r ( 2 ，1 ，) 。 当参数，= 1 时，r c r ( 2 ，1 ，_ ，) 是一个非连通图，网络中所有节点的度数都为2 ， 因此s u n 在【5 】中给出的性质2 2 是错误的。具体的证明过程会在本论文第3 章中给出。 表3 中是r c r 与一些常见的网络拓扑如n 立方，n 维立方连接环( c c c ) ， 和立方环( c o r ) 的节点度数，直径以及二分宽度的比较。结果显示递归立方环 有固定的度数和较短的直径，并且递归立方环有比除了超立方的其它网络拓扑更 大的二分宽度，然而超立方网络没有固定的度数。 递归立方环还拥有一项特殊的平面特性，因此递归立方环r c r ( k j ) 可以 看成是两种不同类型的平面立方平面和环平面的结合。该特性有助于开发有 效的路由算法。y u z h o n gs u n 在文献【5 】中引用了如下的定义，为了本文叙述 第2 2 页 中国科学技术大学硕士学位论文 递归立方环的结构及多播算法研究 的方便和完整性，将其引用如下： 定义2 1 ：一个立方平面( c p ) 是递归立方环r c r ( k ，r ) 的一个子图，立方平 面是互连的，且立方平面的所有链接是立方链接。在一个立方平面中， 节点 a ，b 和节点 彳，b 】由一条立方链接互连当且仅当阻o a i = l 并 且b = b 。 定义2 2 ： 一个环平面( r j p ) 是递归立方环r c r ( k ，) 的一个子图，环平面是 互连的，且环平面的所有链接是环链接。一个环平面包含有，个地址 分别为 a ，0 ， a ，1 】，【4 ，一l 】的节点，其中4 是一个确定的二进 制数。 例如，递归立方环r c r ( 2 ，2 ，2 ) 有1 6 个环平面和8 个立方平面，如图2 4 所 示。图2 4 中也说明了立方平面之间通过环平面的连接关系。例如个表示为