（应用数学专业论文）几类网络的结构及相关参数研究.pdf

摘 要 将互联网络的各个处理器视为节点， 各处理器之间的链接作为边，则得到该 网络的一个拓扑结构，图 g 。图 g的性质直接反映网络的性能。考虑到在网络 信息传输中对小的通信延迟和大的容错性能的需求， 以 及在构造网络中经济因素 及物理机制等方面的要求，本文在研究一般图的宽直径，容错直径的基础之上， 对。 c u b e ,m - a r y n - c u b e ,g h c ,n - s t a r 等网 络的 性能 和结 构 作了 研究 和比 较。 研究图 的 宽 直 径， 容 错 直 径等 参 数是 本 文的 主 要 手 段。 设c 。 为 一 个n点 的 圈，在c 。 中添加 t 条边得到的图的集合记为c ( n , t ) , 1 2 中定义了函数 h ( n , t) = m in ( d 2 ( g ) g e c ( n , t) 并 将 h ( n , t) 的 计 算 作 为 公 开 问 题 提 出 。 本 文 对 函 数 h ( n , t ) 进行了讨论。 n - c u b e 作为一个具有广泛应用的流行网 络拓扑， 具有很好的 性质，而以它为基础的g h c结构既具有类似的拓扑结构，又突破了点数必须为 2的幂的限制。本文在文献 9 中提出的路由算法的基础之上计算了 q ( m n m n - , . . . m i ) 和忿( m ) 的 宽 直 径 和容 错 直 径， 并 对g h c 结 构 优 化作了 讨论 。 作为通常讨论的容错问题的推广和补充， 1 0 提出了限制故障集条件 b y e v ( g ) , a ( v ) f 下的 连通度与 容错 直径的问 题。 本文对q ( m m a - , . . . m , ) 和 q( m ) 在限 制故障 集合条 件下的 连通度与容 错直径进 行了 讨论和计 算。 作为对 n - c u b e 的性能进一步提高的拓扑结构，本文将 n - s t a r 网络与n - c u b e 网络在基本参数，基本结构，基本路由 等方面进行了比较。 n - s t a r 具有很多优于 n - c u b e 的性质。然而其缺点也是明显的，即不同阶的n - s t a r 的顶点数跃迁太大。 作为 对 这 一 缺陷 的 弥 补， 文中 介 绍了a r r a n g e m e n t g r a p h网 络 和 ( n ,k ) - s t a r 网 络， 并列出了它们的基本性质。 c a y l e y图由 于其正 则性， 传递性以 及 规整性近 年来受到广泛的 关注。 在设 计具有强层次性结构的网 络时， c a y l e y 图 往往是首选。 而两个图的笛卡尔积由 于 兼具两个图的很多性质， 在设计有特殊要求的网络时， 往往是不错的选择。 本文 对积图的性质作了补充， 证明了积图具有传递性， 并将一些典型的网络的笛卡尔 积的基本参数作了对比。 计算参数是手段， 但研究网络结构， 为设计更为优化的网络结构作必要的 知识准备才是本文的目 的。 作者认为将 c a y l e y图 和图的笛卡尔积综合利用， 将 有利于设计出满足要求的优化的网络。 关键字: 互联网络 宽直径 容错直径 限制故障集 c a y l e y 图 图的笛卡尔积 ab s t r a c t i f a v e rt e x r e p r e s e n t s a n o d e o f p r o c e s s o r ( o r a s t a t i o n ) a n d a n e d g e b e t w e e n t w o v e rt i c e s a l i n k ( o r c o n n e c t i o n ) b e t w e e n t h o s e t w o p r o c e s s o r s , a n i n t e r c o n n e c t i o n n e t w o r k c a n b e m o d e l e d a s a g r a p h g . c o n s i d e r e d t h e r e q u i r e m e n t o f s m a l l e r c o m m u n i c a t i o n d e l a y a n d b i g g e r f a u l t t o l e r a n t i n m e s s a g e t r a n s m i s s i o n , a n d t h e r e q u ir e m e n t o f p 坷s i c a l l i m i t a t i o n a n d e c o n o m i c f a c t o r s i n t h e d e s i g n o f a n e t w o r k , w e l l s t u d y t h e p a r a m e t e r s u c h a s w i d e d i a m e t e r , f a u l t t o l e r a n t d i a m e t e r f i r s t . t h e n w e l l a n a l y z e t h e p r o p e rt i e s a n d s t r u c t u r e o f s o m e s p e c i fi c n e t w o r k s : n - c u b e , m - a r y n - c u b e , g h c , n - s t a r e t c . l e t c b e t h e c y c l e w i t h n v e rt e x e s . l e t u s d e f in e c ( n , t ) t o b e t h e s e t o f t h e r e s u lt i n g g r a p h b y a d d in g t e d g e s to c. d e fi n e : h ( n , t ) = m i n d 2 ( g ) ig e c ( n , t ) t h e c o m p u t a t i o n o f h ( n , t ) i s b r o u g h t o u t i n 1 2 a s a o p e n p r o b l e m . i n t h i s p a p e r , t h i s p r o b l e m i s s t u d i e d . a s a p o p u l a r n e t w o r k t o p o l o g y , n - c u b e h a s m a n y g o o d p r o p e rt i e s . t h e g e n e r a l i z e d h y p e r c u b e ( g h c ) s t r u c t u r e n o t o n l y h a s t h e s i m i l a r p r o p e rt i e s o f n - c u b e b u t a l s o b r e a k o u t t h e l i m i t o f t h e n u m b e r o f v e rt i c e s n m u s t b e t h e p o w e r o f 2 i n n - c u b e . i n t h i s p a p e r , u s i n g t h e r o u t in g a l g o r i t h m i n 9 w e c a l c u l a t e t h e w i d e d i a m e t e r a n d f a u l t d i a m e t e r o f q ( mm_ , . . . m , ) a n d q ( m ) . m o r e o v e r , t h e o p t i m a l p r o b l e m o f t h e s t r u c t u r e o f g h c i s d i s c u s s e d h e r e . t h e c o n n e c t iv i t y g e n e r a l i z a t i o n i n t r o d u c e d b y e s f a h a n i m a n d h a k i m i c a n b e u s e d t o m o d e l t h e f a u l t - t o l e r a n t a n a l y s i s o f n e t w o r k s w i t h f o r b i d d e n f a u l t y s e t s 1 0 , v v e v ( g ) , a ( v ) a f， w h e r e f i s t h e s e t o f f a u l t v e r t i c e s . i n t h i s i s s u e t h e c o n n e c t i v i t y a n d f a u l t d i a m e t e r o f q ( mm_ , - . - m , ) a n d q ( m ) is c o m p u t e d . t h e n - s t a r g r a p h a s a n a t tr a c t i v e a l t e rn a t i v e o f n - c u b e i s s t u d i e d in c a p t u r e 4 , a n d c o m p a r e d w i t h n - c u b e i n b a s i c p a r a m e t e r , s t r u c t u r e , r o u t i n g e t c . a r r a n g e m e n t g r a p h n e t w o r k a n d ( n , k ) - s t a r n e t w o r k a r e in t r o d u c e d i n t h i s p a p e r a s g e n e r a l i z a t i o n o f n- s t a r . mo r e a t t e n t i o n i s p a i d o n c a y l e y g r a p h t h i s y e a r s , b e c a u s e o f t h e g o o d t o p o l o g i c a l p r o p e rt i e s s u c h a s r e g u l a r i t y , s y m m e t r y - - - .wh e n d e s i g n i n g a s t r o n g l y h i e r a r c h i c a l n e t w o r k , t h e c a y l e y g r a p h w i l l b e t h e f i r s t c a rt e s i a n p r o d u c t o f i n t e r c o n n e c t i o n n e t w o r k s i s d e s i r a b l e p r o p e rt i e s o f c o m p o n e n t n e t w o r k s . we a g o o d t o p o l o g ic a l m o d e l . t h e m e t h o d f o r c o mb i n i n g p r o v e s o me mo r e p r o d u c t g r a p h in t h i s p a p e r a n d c o n d u c t a c o m p a r a t i v e s t u d y b e t w e e n n e t wo r k s . p r o p e r t i e s o f s o me c l a s s i c k e y w o r d s : in t e r c o n n e c t i o n n e t w o r k s , f o r b i d d e n f a u l t y s e t s , c a y l e y g r a p h , c a r t e s i a n w i d e d i a m e t e r , f a u l t t o l e r a n t d i a m e t e r , p r o d u c t o f g r a p h s 丫 独 创 性 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。 据我所知， 除了文中 特别加以 标注和致谢的地 方外， 论文中不包含其他人已 经发表或撰写过的研究成果， 也不包含 为获得电 子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名:日 期: 7 - f 辱 i 月1 1 日 关于论文使用授权的说明 本学位论文作者完全了解电 子科技大学有关保留、 使用学位论文 的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁 盘， 允许论文被查阅和借阅。 本人授权电子科技大学可以 将学位论文 的全部或部分内容编入有关数据库进行检索， 可以采用影印、 缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名:导 师 签 名 : 3 l % 日 期:a 0 年 、月叮 日 电子科技大学硕士论文 第一章综述 1 ， 引言 互联网络的应用十分广泛，小到超大规模集成电路 ( v l s i )内部总 线， 大到计算机广域网。 互联网络应用主要包括底板总线和系统域网络、 电话交换机、异步传输模式 ( a t m )和网际协议 ( i p )交换机内部网络。 同时还包括向量超级计算机处理器/ 存储器互连、多计算机和分步共享 主存多处理器系统互联网络、 工作站和个人计算机集群、局域网、 城域 网、 广域计算机网以及工业应用网络等。 并且互联网络的应用还在不断 增长， 例如: 汽车集中控制系统就需要一个网络把多个微处理器和外设 连接起来。对互联网络高性能和高可靠性的要求以及缺乏统一的标准， 推动了多计算机互联网络的发展。 这种技术被用来提高分步共享主存多 处理器系统的可伸缩性，因此对网络性能提出了比多计算机更高的要 求， 从而进一步推动了互联网络的发展。 事实上， 各种互联网络结构在 某种程度上都可以以抽象为有向或无向的图， 从而用图论的相关理论和 方法来构造更新的符合要求的网络或研究其性质. 人们从未停止过对更高计算能力的追求。 尽管从 1 9 8 0 年到 1 9 9 6 年， 处理器的性能大约每 3 年翻一番， 但软件复杂度、 应用的规模和解决方 案的质量任然不断推动着处理器向更快的速度发展。 在国防、 太空、 汽 车制造业和科学领域已经出现了大量具有巨大挑战性的应用问题， 它们 要求计算机具有每秒钟万亿次级浮点运算，甚至更高级别的计算能力。 这些问题中， 即使规模较小的， 也需要每秒钟十亿次浮点运算性能的计 算机连续计算几个小时。 规模较大的甚至要求每秒钟万亿次浮点运算性 能的计算机不停地运算上千小时。 具有多处理器的并行计算机为实现高 j性能计算提供了解决方案， 以满足对计算能力日益增长的要求， 这些要 求包括更快的运算速度、更高的网络带宽和输入/ 输出 i / 0 )带宽以及 电子科技大学硕士论文 更大的存储容量。 因此设计高性能的互联网络已经成为改善并行计算机 性能的一个关键问题， 而且互联网络是并行计算机中唯一不可能用商品 化部件来高效实现的子系统， 因此它的设计就变得尤为重要了。 但为并 行计算平台选择合适的互联网络受到很多因素的影响，这些因素包括: 性能需求，可伸缩性，递增可扩充性，可分割性，简单性，跨距，物理 限制，可靠性和可修复性，预期工作负载，成本限制等。 这些都是我们 研究网络性能时必须考虑的因素， 也是我们在设计可实现的网络时必须 注意 的问题 ，没有可行性的网络是没有 多大意义 的。 利用图论来研究的网络拓扑，从网络的分类来说属于直接网络。直 接网络的传统模型是一个图g ( v , e )，图中顶点集合v 代表处理节点的 集合，边集e 代表通信通道的集合。这样，网络的很多性质就可以作为 图的性质进行研究。 直接网络是一种很流行的网络结构， 伸缩性好并支 持大数量的处理器。在以后的讨论中，我们将就互联网络的图论模型g ( v , e )的相关参数以及寻径算法进行进一步的讨论。 ， 2 流行的网络拓扑 根据图论的知识，已 经提出了 许多网 络拓扑结构， 其中 最常用的 有: 一维线 性连接、网孔连接、 数型连接、 树网 连接、 金字塔连接、 超立方体连接、 立方环 连接、 洗牌交换连接、 蝶形连接、 多维网 格， d e b r u i j n网等。 图 1 一1 , 1 一2 ， 1 -3 , 1 -4 ，显示了几种常用的互联网络。 图 1 一1图 1 -2 电子科技大学硕士论文 1 0 0 l 1 0 图 1 一3图 1 一4 在已经实现的这些网络中，大多数都是正交拓扑。网络拓扑正交的 充要条件是:节点可以在一个正交的n 维空间内组织起来，每条链路的 安排都要在一维中产生一个偏移量. 正交拓扑可进一步分为严格正交和 弱正交。 在严格正交中， 每个节点至少有一条链路通过每一维。 在弱正 交中， 某些节点在某些维上没有链路: 因此不可能从任意节点穿过任意 维，从给定的节点传到给定的维首先要转移到其他维。 严格正交拓扑的一个优势是路由简单，因此可以使用硬件来实现高 效的路由算法。在严格正交拓扑中，可以用节点在n 维空间的坐标作为 节点的编号。由于每条链路都遍历了一维， 而且每个节点在每一维上至 少有一条链路， 两个节点之间的距离就可以用每一维的偏移量的和来计 算。由于从网络中的任意节点可以直接到达任意维， 路由的实现就比较 简单，只需在某一维上选择绝对偏移量减小的链路就可以了。 最流行的直接网络是n 维网格，k 元n 立方或环网和超立方， 它们都 是严格正交的。 如果n 维网 格有凡x k , x . . . k _ , x 气 _ 。 个节点，k 是第i 维的 节点数，k , _ 2 且。 _ i - n - 1 。每个节点x 有n 维坐标 ( x n - i + x n - 2 ， . . . ， x , ， x o ) 电子科技大学硕士论文 定义，其中，对于。 _ i - n - 1 ，有o s x ; s k , - l o x 和y 两个节点相邻的充 要条件是: 存在j 使得y i = x j 1 1 ， 而对任意的i * j 且 0 - i 2 ，所 有的节点都有 2 n 个相邻节点。当。 =1时，k 元n 立方变成了具有k 个 节 点的双 向环 。 另一种规整而对称的拓扑结构是超立方，记为n - c u b e ，它是n 维网 格和k 元n 立方的特例。关于n - c u b e 的结构和性质我们将在第二章专门 研究，此处不再讨论。 树也是一种流行的拓扑。这种拓扑具有一个根节点并连接在一定数 目的子节点上。这种结构的特点是: 除了根节点， 每个节点都只有一个 父节点，没有环路。如果所有叶节点到根节点的距离都相等，就称这棵 树是平衡的。 作为通用互联网络， 树结构的一个致命缺点是根节点及其 附近节点会成为网络瓶颈。 我们知道对任意一个连通图都有生成树， 故 均可利用树网络中的某些性质 以及路由算法 。 某些拓扑结构的目的是在保持较小直径的同时降低节点度。这些拓 扑大都可以认为是层次拓扑。 以立方连接环为例， 这种拓扑可以看作是 虚拟节点的n 为超立方结构，其中每个虚拟节点是具有n 个节点的环， 共有。 x 2 ” 个节点。 环中的每个节点连接到超立方的一维。 节点度均维 3 , 但网络直径与同规模的超立方是相同的。 图 1 -3是一个 1 6节点的立方 连接环网。立方连接环网是弱正交的，因为环是一维网络，环内的偏移 4 电子科技大学硕士论文 量不会改变其它维的位置。 与此类似， 超立方中某一维的偏移量也不会 影响环中的位置。而且，从一个节点不可能到达所有的维。有些拓扑提 出的目标是在给定节点数目和节点度的条件下，使网络直径达到最小， 其中有两个著名的网络: d e b r u i j n网络和星形图n - s t a r 。 在d e b r u i j n 网络中有d - 个节点，每个节点由一组以d为基的n 个数来表示。节点 ( x _ x n - 2 , . . .， x j ， x o ) ， 这里0 5 x ; - d - 1 , 0 x l ) 相连，0 5 p _ 5 时了 ( u , v ) 的计算是n p 一完全的; c )当1 5 4 时，h e u r i s t i c 方法是求1 , ( u , v ) 的最优方法: d )有例子表明p u ( g ) _ 1 , ( g ) 。 )对于边不交路，可以得到类似于d )的结论 s , ( u , v ) =s u p , g l , 少 , v ): 川 l 2 j - 2 , w是一个正数 ，若g 至 少 有 ( n - 1、 十 w 条 边 或 ; (g 、 一 n + w ， 那 么 g e l ( w ， ， ) 。 更 进 一 步 又2)”l 2 以上每个条件都不能再改进 。 定 理 3 .2 设 g , w , 如 定 理 ， 3 所 述 ， 若 k (g ) 罕 + w - 1 机若 那 么g e l( w存在图g 使得k ( g ) =n - w + w 一 1 ，且g ( i ) 定 理1 1 ) 3 .3设 w, 1 为两个正整数，g 是 n 阶k 连通图， _ _ 、 、 n 一 w 十 2 ac 行) 夕 r ， 二 - - ， ， 份 甲i 1 +w一2， 刀 n么 l t e上 l w ， ! ) l l ( 1 + 4 ) 1 3 j , k r i s h n a m o o r t h y和k r i s h n a m u r t h y 在 2 1 中提出了容错直径的概 念 。 定义 1 . 3 . 7 设g 是k 连通的，g 的k 一1 容错直径d k ( g ) 定义为 d k ( g ) =m a x ; d ( g 一 f ) : v f c v ( g ) , f i k ) 关于宽直径和容错直径显然有下面的结论: 1 ) d ( g ) = d , ( g ) _ d , ( g ) - 4 ， 则存在n 阶k 正则图g 使得d k ( g ) = n - k + 1 0 事实上，d k ( g ) 可以小到等于d ( g ) 。如果图g 是k +2阶完全图去 掉一条边得到的，则有d k ( g ) = d ( g ) = 2 另一方面，d , ( g ) 可以大到等 于。 一1 。比如对g =c . ( n 个节点的圈图)，就有d , ( g ) =。 一1 e 当我们就k 连通k 正则图来考虑d k ( g ) 的计算问题，情况就明了得 多。对满足 2 - k :5 n - 1 且k n 为偶数的自然数k ,” ，定义函数 f ( k , n ) = m a x 姚( g ) : g 为n 阶k 连通k 正则图 。 显然f ( 2 , n ) = n - 1 。由引理 1. 4. 1 ，对较大的k 有: 引理 1 . 4 . 2 如果k n 为偶数且5 _ n 1 2 + 2 - k :5 n - 1 或者n = 2 k - 2 则f ( k , n ) = n 一k +1 0 h s u和 l u z a k 在k 较小时的函数f ( k , n ) 进行研究，得到以下定理: 定理 1 . 4. 3 如果k n 为偶数且k 2 : 3 ，则f ( k , n ) s n / 2 o 一般说来，以上关于函数m a的上界是最好的。事实上，等式 f ( k ,n ) = l n l 2 j 对 无限 多 对k 和n 都 成 立。 h s u 和 l u z a k 在 2 2 中 构 造出 这样的图g ，当n = 2 k - 3 + i ( k - 2 ) ，其中，i = 0 ,1 , . . . ，且3 5 k - 8 且 n / 2 +2 - k _ 6 且k , / 4 n + 3 / 2 + 5 / 2 ; ( d ) f 帆， 2 n +1 ) 二 。 ，k ? 4 且k s -r 万+ 2 0 h s u 在 1 2 中提出了这样一个关于边扩张的问题。设吼为n 阶的圈 图，d , ( c) = n - 1， 在c ， 中添加t 条边得到的简单图的集合记为c ( n , t ) 显然其中的图都是2 连通的。 定义函数h ( n , t ) = m i n d , ( g ) : g e c ( n , t ) ) 。 作 者对该函数进行 了一些讨论 : 引理 1 . 4 . 5 若h 是g 的生成子图且均为k 连通的， 则d k ( h ) - d k ( g ) o 证明由于v ( h ) =v ( g ) , vu , v e v, h 中的( u , v ) 路必在g 中， 而g 中的( u , v ) 路不一定在h 中，有宽距离的定义知d k ( h ; u , v ) ? d k ( g ; u , v ) , 于是有宽直径的定义知d k ( h ) ? d k ( g ) o 定理 1 4. 6函数h ( n , t ) 是t 的单调减函数。 证明固定” ，当1 ; _ h ( n , t 2 )， 故 h ( n , t ) 是t 的单调减函数。 定理 1. 4. 7 n - 4时有 : 图1 - 5 ( a ) h ( n , l ) = ” 一 2 ; 电子科技大学硕士论文 ( b ) h ( n ,2 ) = i n + l ， 其 中 二 表 示 不 超 过 二 的 最 大 整 数 ; l 2 ( c ) t ? 2 伪一 4 ) 时h ( n , t ) 二2 0( 图 1 一 5 ) 证 明 见 4 5 1 1 5 宽直径与容错直径的关系 由于宽直径与容错直径都是衡量网络的容错能力与通信延迟的重 要参数，先后有f l a n d r i n，l i ，徐俊明等人对二者关系进行研究，取 得t一些结果:( 4 l , 5 1 , 2 4 1 ) 定理 1 . 5 . 1 若g 是一个直径为d ( _ 2 )的2 连通图，则当d =2 时，d 2 _ 3 时，d 2 ( d 一1 ) ( d 2 一1 )。 徐俊明等在 4 中改进了这个结果。 定理 1. 5. 2 直径为d的 2 连通图有 d s m a x ( (d 一 1 )(d ， 一 工 、 一 1) 十 i, d ， 十 11 。 2 定理 1 . 5 . 3 设g 时直径为2 的2 连通图， 则d 2 = d z - - 1 的充分必 要条件时d ， 二3 或d 2 =4 :且达到d 2 值的任何两个顶点必相邻。 定理 1. 5. 4 直径为 2的 3连通图有 、 _ m ax (d z 一 ，)(。 一 合 d z 一 ，) + 1,3 d 3 一 ，。 + 1) . 关于 3 连通图， 5 中还给出了以下的结论: 定理 1 - 5 - 5设g 是3 连通图， 若d 2 =2 ， 则d , - m a x 2 几- 2 , d , + 1 o 电子科技大学硕士论文 定理 1 . 5 . 6设g 时直径至少为2 的3 连通图，若d 2 ? 3 ，则 d , ( d 2 一 1 ) 2 ( d 2 一 1 ) ( 几一 1 ) 一 d , 一 2 + 1 。 1 6 限制故障集容错问题 网络的容错性对于判定一个网络的优劣非常重要，对于网络的设计 者而言容错直径或许是衡量容错性能的最好的指标， 但对于网络的实施 者，还有更为实际的问题需要考虑。由于容错直径 d , ( g ) = m a x d ( g - f ) : v f c v ( 叫川 k ( g ) ，在限制出错集的条件下，网络可以容许k ( g ) 一1 个点发生故障而保持连通。但接下来的问题是如何计算k ( g ) ?我们将 在超立方体，广义超立方体。s t a r 网络中分别进行讨论。 电子科技大学硕士论文 第二章 立方体网络 2 1 n维超立方体及其基本性质 n 维超立方体 ( n - c u b e )具有良好的拓扑性质，如正则结构，小的直 径， 容易实现多条平行路径信息传输等，己成为多计算机网络以及并行 分步式计算中的一个流行的网络结构，包括n c u b e - 2 , i s p c / 2 , c o s m i c c u b e以及 g g i o r i g i n 2 0 0 0 多处理器等商业以 及实验系统采用了 这个 结构。本节我们将比较系统地认识n - c u b e 及其相关性质。( 2 5 对n - c u b e 作了较为详细的描述，对其基本性质有较好的讨论。 定义 顶 点 用 2.1.1一个n - c u b 。 图是一个包含2 ” 个顶点的无向图。每个 0 一一2 ” 一1的二进制 串标识 ，两个点x = ( x x 2 , . . . x n ) , y = ( y i , y 2 , - y ) 邻接当且 仅当3 i 使x ; = y 且x i # y ， 对所有j x i e n - c u b e 的第一个重要的性质是它可以由低维的立方体构成。具体说 来， 两个相同的( n - 1 ) - c u b e s ， 其顶点由。 一一2 - 1 - 1 的二进制形式表示。 把两个立方体标识相同的顶点连接起来，就得到一个n - c u b e 。事实上， 在( n - 1 ) - c u b e s 中的顶点a ; ， 在n - c u b e 中可以重新标识: 第一个( n - 1 ) - c u b e 中的点a : 记为0 入 a ; ， 第二个( n - 1 ) - c u b e中的点记为1 a , 。 例如图2 -1 . 图 2 一 1 电子科技大学硕士论文 同样，一个n - c u b e 的全部首位为 0的点以及首位为 1 的点构成的子 图是两个( n - 1 ) - c u b e s 。类似，全部第i 位为 0( 或 1 )的点也构成n - c u b e 的一个划分，故，n - c u b e 具有以下一些简单的性质; ( 1 ) 有n 种不同的方式把n - c u b e 分成两个( n - 1 卜 c u b e s ，使它们相应 的顶点是一一对应的。如果像定义 2. 1 那样标记的话，每个不同的将 n - c u b e 分成两个( n - 1 ) - c u b e s 的拆分方式均有: 其中一个子图的顶点的第; 位均为 1 ，而另一个的顶点第i 位均为 0 . ( 2 ) n - c u b e 中任意两个邻接点a和b : a的邻接点与b 的是一一对 应 的。 我们可以定义点的奇偶性:如果一个点有偶数个 1 ，则该点记为正 的，否则记为负。则很容易得到以下结论: ( 3 ) n - c u b e 中没有奇圈。 证明:设n - c u b e 中的一个圈为a , , a 2 ,，.，鸿，其中a , = a , 。由于 从点a ， 到点再 + : ，1 5 i 5 t - l , 奇偶性改变一次， 而a , = a , ,故奇偶性经 过了偶数次的改变即圈长必为偶。 ( 4 ) n - c u b e 中任意两点的距离等于两点间的汉明距离 ( 即不同的二 进制位数 ) ( 5 ) n - c u b e 是直径为n 的连通图。 以上命题建立起n - c u b e 作为图的一些基本性质。我们接下来考虑的 一个重要的问题是如何以一种简单的方式来辨认一个超立方体， 即如何 用一些简单的规则来定义一个n - c u b e ?下面的定理回答了这个问题: 定理 2. 1 . 1 一个图。 = ( v , e )是一个n - c u b e ，当且仅当 1 ) v有 2 ” 个顶点， 2 )每个点的度数均为n , 3 ) g 是连通的， 4 )对两个邻接点a 和b 有: 与a 邻接的点和与b 邻接的点是一一 i 5 电子科技大学硕士论文 对应连接的。 由该定理，一个 2元 4立方就是一个 4 - c u b e 。任何一个多处理器系 统都应该允许其处理器与其他各节点交换数据。设a, b 为n - c u b e 上任 意两点，考虑从a到b 信息传递的问题。由于n - c u b e 中两个相邻节点有 且仅有一位不同，故很容易想到的传递方式是每一步改变a中的一位为 与b 相同，例如从左到右依次改变，不妨设a, b 前i 位不同:a= ( 7 ,a 2 a 3 . . . a ,a , , . . . a , )， b = ( b , 久 乞. - b ,a , , . . . a )， 则信息可通过以 下路 径传递 : a = n o d e 0 =( a , a 2 a , . . . a ,a ,. , . . . a) n o d e 1 = a= ( b , a 2 a 3 ， 二 a , a, n o d e 2 = a = ( b , b 2 a , . . . a , a, 二 a) 二 a) b = n o d e i =( b ,b , b ， . . . b ,a ,. , . . .a n ) 该路径的长度为i =h ( a , b ) ，显然这是a , b 之间的一条最短路，而 且a , b 的不同位不是前i 位时也有类似的路径， 故: d ( a , b ) = h ( a , b ) = i 显然n - c u b e 的直径d = n = l o g 2 n, n 为顶点数 以上只讨论了a, b 之间信息传递的最短路径， 但当传输的信息量大 时， 如果可能， 我们也可以将信息分包沿着不同的路径同时传输以减少 通信延迟，因此a , b 之间有没有平行路径，有多少，路径长度如何就 成为关键的问题。另一方面，当系统的处理器数量增多时， 难免会有故 障点出现， 这种情况下非故障点之间还能否保持连接状态， 以及其间信 号传递的时长为多少?这样就在n - c u b e 中提出了点对点的多路径传输 问题。 由上面讨论a, b 之间信息传递的最短路径的过程可见， 我们不必从 a中不同于b 的第一位开始修正，比如，设a, b 有 i 位不 同，我们可 以 从第j 位开始修正，然后往后j +1 位，j 十2位，.，i 位，再依次修 电子科技大学硕士论文 正第 1 ， j 一1 位，显然有i 条长为i 的平行路径。 一 引理2 , 1 2 z 设a , b 为n - c u b e 中的任意两点， 则a , b 之间有 h ( a , b ) 条长为h ( a , b ) 的平行路径。 引理 2 , 1 , 3 1 设a , b 为n - c u b e 中的任意两点， 设h ( a , b ) n ， 则a , b 之间有n 条长度不超过h ( a , b ) +2 的平行路径。 证明:引理2 . 1 . 2 中已经给出了i 条长为h ( a , b ) = i 的平行路径。 下面给出第i -1- 1到第n 条 路径;首先将a ， 修正为其补瓦 ( j 二 i + l , i 十 2 , . . , n )，于是新的路径从点 n o d e 1 : q u ) = a , a 2 . . . a , a ,+ , 瓦 a , + 一 a . 开始，然后如前i 条路径之一那样修正 1到i 为，第i 步之后，得到 点 n od e ， 瓦 a ,+ , 民 a ; a . . . a 最 后 ， i + l :6 (l ) = b ,b , 把a ; 修正为a , ，得到b点。 定理 2 , 1 , 4 1 1 ，在n - c u b 。 中，呱= n + 1 =d - 1 - t o 证明:由引理 2 . 1. 2 ，引理 2 . 1 . 3很容易得到结论。# 2.2n - c u b e网络中的容错问题 由于n - c u b e 网络是n 一 正则的， 且任意两点间都有n 条长度不超过n + l 的平行路径， 这使得n - c u b e 具有很好的容错性。 d a n i e l a f e r r e r o，c a r l e s p a d r o , s h a h a r a m l a t i f i , a b d o l - h o s s e i n e s f a h a n i a n ，刘长河等 对这一问题作了不同角度的讨论 6 1 7 1 1 0 1 ( 2 6 ) 0 定理2 . 2 . 1 n - c u b e 网络的n -1 容错直径几- , = n + l o 证明:由引理 2- i - 2 一引理 2- i - 4 容易证明上述定理。# 在n - c u b e 中d_ , = n + 1 =峨二 d +1 ， 可见n - c u b e 网络具有很好的容错 电子科技大学硕士论文 能力以及很短的通信延迟，正因为这样的优点，n - c u b e 网络得到广泛的 应用。 正如前面提到的， 容错直径所涉及的故障点最多为n -1 = 1 0 g 2 n- 1 ，而在一个大型的n - c u b e 网络中，由于处理器数目庞大，故障点往往 会更多，故在这样的网络中讨论限制故障的容错问题非常必要 6 l 7 1 1 0 1 2 6 1 0 定理2 . 2 . 2 记n - c u b e 为么，则k ( 么) = 2 n - 2 0 这样在限制故障集的情况下，q可以容许2 n - 3 个点发生故障而保 持连通口 那么么的2 n - 3 容错直径等于多少呢， s h a h a r a m l a t i f i 在 7 1 中使用组合分析的方法对e的2 n - 3 容错直径进行了计算， 得到如下的 结果 : 定理2 . 2 . 3 在规定限制故障集的n - c u b e么中姚_ 3 = n + 2 这个结果只比n -1 容错直径d_ 。 多 1 ，比 直径多2 , q的容错能力 得到进一步的证明。但是，如果故障点集合f 的规模增大，又会有怎样 的结果呢?首先，么-f 是否连通不能肯定。s h a h a r a m l a t i f i 进行了进 一步 的 讨论并 给出了 川 5 2 n - 2 时， 判断q- f 是 否 连通的 一 个算法。 引理2 . 2 . 4 设v 为么的任意顶点，f = a ( v ) u v 1 ，则q-f 是连 通的 。 引 理2 . 2 . 5 设 f 为 v ( q) 的 一 个 子 集 且 回= 。 ， 则q - f 不 连 通当且仅当f 是q . 中某点的邻接点集a ( v ) e 而且，当 f 是么中某点的邻 接点集a ( v ) 时，q n -f 只有两支。 对边 e = ( u , v ) e e ( 么) ，设 s ( e ) = a ( u 卜v ) u a ( v 卜u ) 。对 任意边 e 二 (u , v ) 。 e ( q ) 有s ( e ) 】 = 2 n 一 2 定 理2 . 2 . 6 设 f 为 v ( q . ) 的 一 个 子 集 且囚= 2 n - 2 , 且 任 意v e v , a ( v ) a f ， 则q n - f 不连通当且仅当存在边e = ( u , v ) e e ( q) 使得s ( e ) = f - 电子科技大学硕士论文 由 以 上引 理以 及定 理， s h a h a r a m l a t i f i 给出 了 1川 - 2 n - 2 时 ， 判 断q n -f 是否连通的一个算法: s t e p - 0 :如 果f i n ， 报 告q - f 连 通， 停 止。 s t e p - 1 : ( n - f- 2 n - 2 )检查是否有点， e v 使得v o f 但a ( v ) 二f, 如果有，报告q-f 不连通，停止。 s t e p - 2 :如 果川 2 n - 2 , 报告q h - f 连 通， 停止 s t e p - 3 : ( if ! 二 2 n - 2 ) 检 查 是 否 有 边e = ( u , v ) e e ( q ) 使 得s ( e ) 一 f 如 果有，报告q , -f 不连通，否则报告q - f 连通，停止。 该算法的时间复杂度分析如下:算法的主要计算步骤在s t e p - 1和 s t e