（应用数学专业论文）交错群网络的容错性分析.pdf

个人简历 福建师范大学学位论文使用授权声明 本人( 姓名) 挫塑霞学号2 q q 至互鱼2 专业座旦数堂所呈交的论文( 论 文题目：交错群网络的容错性分析) 是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果。本人了解福 建师范大学有关保留、使用学位论文的规定，即：学校有权保留送交的 学位论文并允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容；学校可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名聋邀整指剥撇 签名日期型立：盘 福建师范大学郑淑霞硕士学位论文 摘要 众所周知，信息社会的基础是计算机互连网络，信息交换的关键是通信算法。 寻找具有路由算法简单、容错性能高等良好性质的互连网络是实现各种通信算法和 协议的前提。自从s 且a k e r s , 且k r i s h n a m a r t h y 倡导把c a y l e y 图( 群图) 作为对称互 连网络模型之后，网络设计者和图论学者利用各种技巧提出并研究了一系列互连网 络模型，如超立方体q ，星图网络瓯及蝴蝶网络( b u t t e r f l yn e t w o r k ) ，蜂窝网络 ( h o n e y c o m bn e t w o r k ) 等。交错群图a q 作为星图可- 替代的网络，也在1 9 9 3 年由 z j w o , & l a n k s h m i v a r a h a n 和& kd d h a l l 首先提出来。冀有虎提出了一种新的 交错群网络丘m ，与a q 相比，州的每个结点的度大约是旧网络的一半且直径与 旧网络大致相同，优越性显而易见。进一步，陈宝兴给出了似的最优路由算法。 本文在此基础上，解决了如下问题： ( 1 ) 给出了交错群网络a n 的一条内点不交的并行路构造方法及所有路的长n n1 度，的上下界，进而求出了宽直径与直径的关系： d 。) + 1 sd n - 1 以) s d 。) + 2 ，同时确定了其连通度是n - 1 。 ( 2 ) 多处理器系统的容错计算的研究已有近半个世纪的历史，无论是在诊断策 略，诊断模型，还是诊断算法方面，都取得了一系列的成果。p r e p a r a t a ，m e t z e 和 c h i e n 首次提出了系统级的t 一可诊断的概念。继p m c 模型之后，他们又提出了比 较诊断模型。本文给出了交错群a n n 在p m c 模型和比较诊断模型下关于不同诊断 策略的诊断度。 ( 3 ) 另一方面，系统级故障诊断是针对一个系统的全局诊断度而言的，却忽略 了局部诊断问题。由于整个系统的部分子系统其故障节点的个数可能超出了系统的 诊断度。显然，讨论系统的局部诊断度可以得知更多的局部结点的连通度信息。本 文最后讨论了交错群网络的局部诊断度和强局部诊断性等相关问题。 关键词c a y l e y 图，交错群网络似，并行路，诊断度 福建师范大学郑淑霞硕士学位论文 a b s t r a c t i ti sw e l l - - k n o w nt h a tt h ei n t e r c o r m e c t i o nn e t w o r ki st h eb a s eo fi n f o r m a t i o n s o c i e t ya n dt h ec o m m u n i c a t i o na l g o r i t h mi st h ek e yo fi n f o r m a t i o ne x c h a n g e s e e k i n g n e t w o r kt o p o l o g i e sw i t hg o o dp r o p e r t i e ss u c ha ss y m m e t r yi si n d i s p e n s a b l et or e a l i z ea l l k i n d so fe f f e c t i v ec o m m u n i c a t i o n ，a l g o r i t h m sa n d p r o t o c o l s s i n c es b a k e r sa n db k r i s h n a m u r t h ya d v o c a t e du s i n gc a y l e yg r a p h ( g r o u pg r a p h ) 弱t h e m o d e l so f s y m m e t r i c i n t e r c o n n e c t i o nn e t w o r k s ，s o m ev e r s a t i l ed e s i g n e r sa n de x p e r t si ng r a p h t h e o r yi n t r o d u c ea n d r e s e a r c ho n as e q u e n c e o ft o p o l o g i e s ，s u c ha sh y p e r c u b e ，s t a rg r a p h ， b u t t e r f l yn e t w o r k ，h o n e y c o m bn e t w o r ka n ds oo n a sa l li m p o s s i b l es u b s t i t u t eo fs t a r g r a p h ，a l t e r n a t i n gg r o u pg r a p hw a sp r o p o s e db yj s j w o ，s l a n k s h m i v a r a h a ma n d s 。k d d h a l li n1 9 9 3 t h e yd e f i n e da l t e r n a t i n gg r o u pn e t w o r ka g , y o u h uj ip r o p o s e da n e wk i n do fa l t e r n a t i n gg r o u pn e t w o r ka n c o m p a r e dw i t ha g ，t h ed e g r e eo fe v e r y n o d ei sl e s st h a n 彳q ( a b o u to n eh a l fo f a g ) a n dt h ed i a m e t e ri se q u a lt oa g , w e c e n t r eo nt h ef o l l o w i n gp r o b l e m sb a s e do nt h eo p t i m a la l g o r i t h m sp r o p o s e db yb a o x i n g c h e n ： ( 1 ) w ec o n s t r u c t e dt h en - 1v e r t e xd i s j o i n tp a t h sb e t w e e na n yt w ov e r t i c e so fa n ， b o u n d e dt h el e n g t h o ft h e s ep a t h s ，a n dd e r i v e dt h ew i d ed i a m e t e r ： d ) + 1 sd 。一l ) so ( m v ) + 2 。a tt h es a m et i m e ，t h ec o n n e c t i v i t yo fa n , i s n - 1 ( 2 ) i th a s b e e nh a l fa n c e n t u r y s i n c et h es t u d yo ft h ef a u l tt o l e r a n c ea b o u tt h e m u l t i - p r o c e s s o rs y s t e m m a n yr e s u l t sw e r eo b t a i n e da b o u tt h ed i a g n o s t i cs t r a t e g y , d i a g n o s t i cm o d e l sa n dd i a g n o s t i ca l g o r i t h m s p r e p a r a t a ，m a z ea n dc h e np r o p o s e dt h e t - d i a g n o s t i ca n dt h ed i a g n o s t i cm o d e lw a sc a l l e d p m cm o d e l t h e nt h e c o m p a r e d d i a g n o s t i cm o d e lw a sp r o p o s e db yp r e p a r a t a , m e t z ea n dc h i e n i nt h i sp a p e r w ed e r i v e d t h ed i a g n o s t i cd e g r e eo fa n , u n d e rt h ep m cm o d e la n dc o m p a r e dd i a g n o s t i cm o d e l a b o u tt h ed i f f e r e n td i a g n o s t i cs t r a t e g i e s ( 3 ) s y s t e ml e v e lf a u l td i a g n o s i si sp r o p o s e df o l l o w i n gt h eg l o b a ld i a g n o s i sa b i l i t yo fa s y s t e mw h i l ei g n o r e ds o m el o c a ls y s t e m a t i cd e t a i l s i ti sp o s s i b l et ot h et h en u m b e ro fa l l n 祸处师范人学郑淑霞硕：l ：学位论文 f a u l t yn o d e s i ns o m ep a r to ft h es y s t e mgm a yb em o r et h a n te v e ni ft h ed i a g n o s a b i t y o ft h es y s t e mi st s ot h el o c a ld i a g n o s a b i l i t ys t a t e sm o r ec o n n e c t i o ns t a t u sa r o u n di t w e s t u d yt h el o c a ld i a g n o s a b i l i t yo fa l t e r n a t i n gg r o u pn e t w o r ka n dt h es t r o n gd i a g n o s a b i l i t y p r o b l e m s k e y w o r d s ：c a y l e yg r a p h ，a l t e r n a t i n gg r o u pn e t w o r k 刎l ，p a r a l l e l p a t h s ， d i a g n o s a b i l i t y i i i 福建师范大学郑淑霞硕士学位论文 中文文摘 超大规模集成( v l s l ，v e r yl a r g es c a l ei n t e g r a t e d ) 电路技术的出现和现代通信 技术的高速发展已给计算机的理论，技术和应用带来了深刻的革命，它使人们能够 构造出更复杂，更快捷而又更经济的计算机系统和互连网络。随着商业，电信，军 事等行业竞争的日益加剧，建造更大规模的系统共同平行交换和处理巨大的数据是 势在必行的。这就对网络设计者提出了严峻挑战：在选择设计这样的系统时，选择 什么样的互连网络拓扑结构是至关重要的。互连网络结构的选择不但要考虑系统的 性能，更要考虑系统的制造成木。冈此，高性能低成本始终是超大规模网络设计者 所必须遵循的两大壮木原则，也是网络设计析所追求的目标。由于一个互连网络的 拓扑就是一个图，我们可以用图的术语来介绍衡量高性能，低成本的基本度量： ( 1 ) 小的或固定的度( d e g r e e ) ( 2 ) 小的通信传输延迟( s m a l l c o m m u n i c a t i o nt r a n s m i s s i o nd e l a y ) ( 3 ) 简单的路由算法( r o u t i n ga l g o r i t h m ) ( 4 ) 均匀性( u n i o r m i t y ) 或对称性( s y m m e t r y ) ( 5 ) 高容错性( 廊u l tt o l e r a n c e ) ( 6 ) 可拓性( e x t e n d i n g ) 可嵌入性( e m b e d d a b i l i t y ) ( 8 ) 有效的布图( 1 a y o u t ) 算法 自从英国数学家凯莱( 彳c a y l e y ) 在1 8 9 5 年首先提出用群来构造图后，对凯莱 图的研究就持续不断，特别是s 且a k e r s 和且k r i s h n a m u r t h y 提出把凯莱图作为对 称互连网络模型之后，人们对凯莱图的研究更是有增无减。比如超立方体网络( q ) ， 星图网络( s t a rg r a p h ) ，蝴蝶网络( b u t t e r f l yn e t w o r k ) ，蜂窝网络( h o n e y c o m bn e t w o r k ) 等。冀有虎提出了一种新的交错群网络a n m ，此网络与彳g 比较，每个结点的度大 约是旧网络的一半且直径与旧网络大致相同。因而新交错群网络的优越性显而易见。 陈宝兴给出了此交错群网络的一个最优路由方案。在上述结果的基础上，我们讨论 了交错群网络a n 的并行路构造，宽直径问题，全局诊断度，局部诊断度研究以及 强局部诊断性讨论等问题。文章主要工作如下： 第一章主要叙述了本文的研究背娥及目_ j 】 国内外关于本文相关问题的研究情况 和1 ：婴纳粜，j l x , j 。水文的一帅j 小符呵f 1 ：了一些简i 丫1 说明，给f l l y , - 千棚必5 1 】! i i ! ： 福建师范大学郑淑霞硕士学位论文 第二章构造了交错群网络的玎一1 条并行路，并给出了每条路z 的取值范围，在此 基础上讨论了其宽直径与直径之间的关系。主要结果如下： 当3 是不变元时候，设p ；c l c 2 一& 巳乞弓，lc ll + ic 2l + iqi 一所 ( 1 ) p l 一1 p 2a2 时，共有m 条长度为d ( p ，e ) 一m + 七的路，n - m - 1 条长度为 d ( p ，e ) + 2 = m + 七+ 2 的路， ( 2 ) a = 2 , p 2 - 1 时，有m 条长度为d ( p ，e ) - m + 七- 3 的路，n - m - 1 条长度为 d ( p ，p ) am + 七- 1 的路， ( 3 ) ip l ，p ：) n 住2 1 - 1 r1 或2 是不变元素时，有m 条长度为d ( p ，e ) m m + 七的 路，n m 一1 条长度为d ( p ，e ) + 2 = m + 七+ 2 的路， ( 4 ) l 慨，见) n 仉芍l 暑1 且1 或2 属于同一个轮换，有m - 1 条长度为d ( p ，e ) 一所+ 七 的路，n - - 掰条长度为d ( p ，e ) + 2 = 掰+ 七+ 2 的路， ( 5 ) l 扫。，p ： n o , 2 l - 0 且1 ，2 属于不同轮换，有m - 1 条长度为d ( p ，e ) 一m + 七- 1 的路，n m 一1 条长度为d ( p ，e ) + 2 = m + 七+ 2 的路， ( 6 ) i 饥，p ：) n 仙2 1 - 0 且1 ，2 属于不同轮换，有m 一1 条长度为d p ，e ) mm + 七- 1 的路，n m 一1 条长度为d ( p ，p ) + 2 i m + 七+ 2 的路，1 条长度为d ( p ，p ) + 1 - m + 七+ 1 的 路。 当3 是变元时候，结点p , e 之间的距离是上述3 是不变元时候的每种情况减2 。 同时，该拓扑结构的宽直径与直径之间的关系是： d ) + 1 sd n - i 口m ) 一掣+ 2s 竿1 + 2sd ) + 2 。 第三章讨论了交错群网络彳m 的全局诊断度，主要结果如下： 交错群网络a n 在比较诊断模型下的诊断度是n 一1 ，在p m c 模型下的f f 一诊 断度是2 露一5 。 第四章讨论了a n 的局部诊断度和强局部诊断性等相关问题，得到如下结论：n 交错群网络彳m 的局部诊断度是珂一1 且在去掉一个阶是刀一4 的边集后仍能保 持强局部诊断性，同时；若去掉任意一个边集之后的交错群网络a n , 的结点最小度 6 佑) 一t 满足：t 苫3 ，那么拓扑结构在b g m 模型下的诊断度为t 。 v 第1 章绪论 第1 章绪论 1 1 课题背景 信息社会的基础是计算机互连网络，信息交换的关键是通信算法，寻找具有 路由算法简单、容错性能高等良好性质的互连网络是实现各种通信算法和协议的 前提。自从s 尼a k e r s 与最k r i s h n a m u r t h y h 倡导把c a y l e y 图( 群图) 作为 对称互连网络模型之后，网络设计者和图论学者利用各种技巧提出并研究了一系 列互连网络模型，如超立方体，d eb r u i j n 和k a u t z 网络，洗牌交换网络 ( s h u f f l e e x c h a n g en e t w o r k ) ，星图( s t a rg r a p h ) ，蝴蝶网络( b u t t e r f l y m e t w o r k ) ，蜂窝网络( h o n e y c o m b 脂t w o r k ) ，金字塔网络( p y r a m i d n e t w o r k ) 【3 - 】。 正如b e h r o o zp a r h a m i 在其专著【2 】中所言一我们已经迷失在互连网络的海洋。交 错群图a a 作为星图可替代的网络，也在1 9 9 3 年由z 5 ：j w o ，& l a n k s h m i v a r a h a n 和& 尼忍d h a l l 7 】首先提出来，紧接着，冀有虎1 8 】提出了一种新的交错群网络帆， 与a 瓯比较，每个结点的度大约是旧网络的一半且直径与旧网络大致相同，因此 优越性显见。陈宝判1 2 】给出了交错群图a n 的最优路由算法。 图论学者l b h u y a n ，d ra g r a w a l 、a 足d u b , g h c h e n , d eh s u 、kd i 矿z a ea l - a y y o u b 及y o s h i y a s ui s h i y a m u i 分别构造出了超立方体、广义超立方体、超圆 环面的点不交的并行路，还估计了它们的长度。另外，k h a l e dd a y 和a n a n d t r i p a t h i l l 0 1 构造了星图，7 条的点不交的并行路。最近，t s u n g - c h il 玩d y i - r o n g d u h i n 构造了研，七) 一s t a r s 的点不交的并行路。基于上述思想，本文试图构造交错 群图a n 的点不交并行路。 多处理器系统的容错计算的研究已有近半个世纪的历史，无论是在诊断策略， 诊断模型，还是诊断算法方面，都取得了一系列的成果。对任何基于网络互连的 多处理器系统，不管其拓扑性质如何，随着处理器数目的增加，处理器发生故障 的情形是不可避免的。这就带来了多处理器系统在可靠性和可使用性方面的问题。 尤其是在处理器发生故障而又不允许中断系统运行的情况下，这一问题的严重性 显得更为突出。解决这一问题的方法即为容错技术，它由两步组成：第一步，故障 诊断，将有故障的处理器识别出来；第二步，系统重构，即将第一步诊断出来的处 理器用无故障的处理器替代，其中第一步是关键。p r e p a r a t a ，m e t z e 和国蛔首 次提出了系统级故障诊断模型，也称为p m c 模型，在基于p m c 模型的f 一可诊断系 福建师范大学郑淑霞硕士学位论文 统中，假定故障处理器的总数不超过t ，每个处理器向另外几个处理器发出测试激 励并观察其响应是否与预期的响应一致，以此实现该处理器对这几个处理器的测 试，然后根据所有的测试结果确定故障处理器集。继p y c 模型之后，又有多个故 障诊断模型被提出，其中，由肠j e 忽c h w a ，h a k y m y 提出的基于比较的模型对于 多处理器系统来讲是最实用的。在比较诊断模型中，系统任务分别在两个处理器 中执行，由一个中央观察器( 仲裁者) 对其执行结果进行比较。中央观察器再根 据所有的比较结果进行诊断。随后，m a e n g 和施“钉完善了e a l e k 模型，允许多 个仲裁点参加检测，且每个仲裁点可以测试其任意两个相邻节点，称此模型为 甜 模型。s e n g u p t a 和b a h u r a 砸1 进一步修正了删模型，提出了脚模型。在这个新 的诊断模型中，若前一个节点与后两个节点相邻的话，那么前一个节点可以测试 后两个节点。这个模型给出了许多关键性的条件来判断一个系统是否是一可诊断 的，同时在确定一个系统是可诊断的条件下给出了一个多项式时间算法来识别故 障点。樊建席嘲，王大进研究了超立方体及其变形如交叉超立方体，广义超立方 体等在比较诊断模型下的诊断度。j u nz h e n ge t8 j 川讨论了星图网络在比较诊 断模型下的诊断度。砌钞一y u nc h a n g , g e r a r dzc h a n g , g e n - h u e yc h e n 位盯给出 了一类无三角形的正则网络分别在精确诊断策略和悲观诊断策略下的诊断度。本 文讨论了交错群网络矾。在比较诊断模型下的诊断度。由于它包含三角形，可看 成是上述结论的补充。系统级故障诊断是针对一个系统的全局诊断度而言，实际 上统的部分子系统的故障点数可能超出了系统的诊断度。因此，讨论一个系统的 局部诊断度可以得知更多的局部结点的连通信息。 1 2 基本概念及预备引理 计算机在人类社会的各个方面如商业，金融等社会生活方面发挥着越来越大 的作川。在计算机的迅猛发展l i i ，不断得击c l ! 山了许多重要的问题尚待解决。在并 行处理领域，研究并行机中处理器连接的方式( 互连网络) 与路由问题是一个很 重要而且很基本的问题。它对于系统之问的信息传输至关重要。网络中组件与组 件之间的连接方式称为网络的拓扑结构。在分析拓扑结构时，人们通常把网络中 的组件抽象成一个点，把通信新到抽象成两点之间的连线，那么该拓扑结构就被 抽织成一个图。研究网络的拓扑结构问题就归结为研究图的结构问题。换言之， 图是网络拓扑结构的数学模型1 3 1 。文章中把组件( n o d e s ) 与图的顶点( v e r t i c e s ) ， 2 第1 币绪论 通信信道( c h a n n e l s 或l i n k s ) ，图的边( e d g e s ) 与弧( a r c s ) 等同。并且，网络的 拓扑结构，网络，图这三者指的是同一对象，不加区分【3 1 。 我们将采用以下符号： 阻1 ：表示不大于】f 的最大整数，其中x e r ； i xi 表示不小于z 的最小整数，其中x e r ： 乙表示整数集合【0 ，1 ，2 ，n h ； 瓯表示万元集合( o ，1 ，2 ，n - 1 的全体冠换组成的对称群，且i 瓯i 一万! ： 4 表示鼠中的全体偶置换组成的子群，称为交错群，且有1 4i 一，嘭。 定义1 1 唧：设g 是有限群，( e 为g 的单位元) ，s 是g 的子集，且满足条件： ( 1 ) p 隹s ( 2 ) g 。1 s 且g e s 当且仅当g s 。则群g 关于子集s 的右c a y l e y 图 x - c a y l e y ( g ，s ) 定义为：v ( x ) g ，e ( x ) ( g ，g s ) ig g ，s s 】。 关于c a y l e y 图，有如下基本事实： 定理1 1 网：x c a y l e y ( g ，s ) 是群g 关于子集s 的c a y l e y 图，则： ( 1 ) x c a y l e y ( g ，s ) 是无环的，当且仅当e 诺s0 为群g 的单位元) ； ( 2 ) x 是无向图，当且仅当s s 。 定义1 2 鸭( 交错群网络哪蜘) 啪一护怯0 ：甜 历 ，且当i j f 时，p t 乒p ，即p 是 的一个置换。对于任意两个置换6 ，仃， 它们的积定甜m 邓，其中炬硼h 也就是说，若扣眩p 6 2 2 ：玢 6 t ( 三主：三) ，则砸一( 三主：爱) 。为了方便起见，我们用标准的一 维数组表示p ，即把p = ( 三主i 三) 写成p - a p ：见设鼠- 2 3 1 4 。埘， g 尺= 3 1 2 4 。以，乙2 1 i 4 ( i - 1 ) 3 ( i + 1 ) 。以，其中f 4 , 5 ，刀。交错群图a n , 是凯莱图 c a y ，丁) ，其中丁； 既，g r ，刁) 。 显然，似是一个度为万一1 的正则图，其边数为万。一，直径f 塑气垒1 ， o 3 ) 。特别地，对似中的任意一个元素p - a p ：。以，若岛一f ，则称只是不变元 素。任意一个元素p = p t p ：。以都可以写成如下形式：p = q c ：。& e 忾。白，其中q 为 长度大于等于2 的轮换。 如下图所示的分别是州。和允眠： 3 祸建师范大学郑淑霞硕：卜学位论文 图( 1 - 2 - 1 ) g 鲥v 4 图( 1 - 2 2 ) 批 定义1 3 删：对于图gg 的一个顶点子集k 称为是g 的点覆盖( 点控制集) ，若 g 的每一条边在k 中都有一个顶点与之关联。g 中的具有最小阶数的点覆盖称为 是g 的最小点覆盖。 4 第1 章绪论 定义1 4 n 町：图g ，e ) 的连通皮盯( g ) 定义如下：r ( g ) - m i n l s i ：scv ( g ) 且g s 是不连通的。 在并行计算机系统的网络巾，信息足通过若干条内点不交的路径平行地进行传 输。于是，仅孤立地考虑连通度和直径是不够的，因为网络虽然有大连通度和小直 径，但通过该网络中若干条内点不交的路平等地传输信息时，其中某些路径可能很 长。因而传输延迟大，信息到达时间间隔很大，影响整个系统的有效性。因此，在 并行计算系统中，将连通度和直径结合起来考虑是必要的，于是人们提出度量并行 计算系统网络的容错性的传输延迟的参数一宽直径。 定义1 5 h 们：设g 是k 连通无( 有) 向图( 即七( g ) 苫k ) x 和y 是g 中两个不同 的顶点。由m e n g e r 定理知，g 中存在k 条内点不交的( x ，y ) 一并行路系，记为 p 一识，只，丘) 亦称后一c o n t a i n e r 。p 中路的最大长度为 d ( p ) 一m a x i d ( e i ) l i - 1 ，2 ，七) 。记丑( g ；工，y ) 为g 中x ，y 之间的所有 k - - - c o n t a i n e r 组成的集合，g 中从顶点z 到顶点y 宽度为k 的距离，喀( g ；而y ) 定义 为d i ( g ；z ，) ，) - m i n d ( p ) p e p i ( g ；x ，) ，) ) 由定义知，盔( g ) 就是g 的直径d ( c ) ，而且有 d ( g ) 一d l ( g ) sd 2 ( g ) sd i ，( g ) sd 。( g ) 定义1 6 ：对于两个点集合f 1 和f 2 ，定义e a e 如下： 缸i x e e 啡e 或枷e 血喏互】 eu e ： x l x e 5 或者x e e 】 电子商务，电子货币，网上银行等关键性行业不允许存在安全隐患，或发生 错误时要以很小的代价排除故障。因此当计算机系统日益广泛应用于对安全性要 求很高的系统中时，对这种系统提供很好的容错能力是十分必要的。为了维护一 个系统的可靠性，故障处理器必须被诊断出来并排除。系统级故障诊断是保证网 络或多处理机系统的安全与稳定的方法之一，它通过相互测试，诊断，可确定系 统中的故障机。故障诊断主要研究的内容包括3 个方面：诊断的特性描述，诊断 能力及故障集诊断。其中诊断能力是决定某给定的系统中可诊断的故障集大小的 限度。对于某一给定的系统结构，一般研究该拓扑结构在不同诊断模型下运用不 同诊断策略的诊断度的大小，其中测试是诊断的基础。在一个系统的诊断过程中， 为了有效的进行诊断，必须假设测试结果能够为诊断提供足够的信息，这些信息 称为测试 5 ：f 型。土1 ) 2 i 一p r e p a r a t a 抛【的p m c 模型可用如下表格说明： 5 祸建师范火学郑淑霞硕士学位论文 “v o ( u ， ，) o00 o11 1o0 1 110 1 表( 1 - 2 1 ) p m c 模型 另外常用的一个模型即比较诊断模型可用一个图m = ( 以c ) 来表示，其中y 是系统中的所有处理机，c 是有标记的边集。若u ，v 通过结点w 来比较，则 ， ，) 。是 c 中标记为w 的一条边。由于两个结点可被不同的结点比较，因此m 是一个多重图。 对比较结果作如下规定：若u 和 ，的输出结果一致的话，则，( o ， ，) 。) 1 0 ，反之则 ，( ，l ，) ，) - 1 。若比较结果w 是正常结点，且r ( ， ，) 咿) 一0 ，则结点“，y 都是正常结点： 若，( ，y ) 。) = 1 ，$ w j u ， ，w 其中之一必是故障点。但若比较结点w 是故障结点的话， 那么比较结果是不可靠的。简明起见，可用下表说明： wu 和y ，( h 川) 正常都正常 0 故障都正常 0 1 正常不全m 常 1 故障不个币常0 1 表( 1 2 2 )比较诊断模型 定义1 6 【柏】：各种比较模型中的所有比较结果的集合可定义为一个函数s ： c - 0 ，1 】- ，这个函数称为诊断的症状群。对某一个给定的症状群口，v 的一个子集 fc y 同仃是相容的当且仅当f 中的点是正常结点，若对于每个症状群仃，v 中只 有一个子集fc 矿同仃是相容的，则称系统是可诊断的。当一个系统在可诊断的条 件下，故障点数不超过t ，称这个系统是t 一诊断。 定义1 7 删：给定一个系统g 和比较策略m 。，对于任一结点“矿，记 五一p i ，) e 或 ，v ) 。e e ) ，即以中的点或者同比构成的连边，或者通过五中 某结点w 同u 进行比较。定义图q = ( 邑，k ) ，其中k d ，呐l ，w e 丘，且 ，v ) 。c 。 定义1 8 ：对于g 的一个子集x ，r ( x ) 是不属于x 中的点，且通过x 中的另一 6 第1 章绪论 个结点进行比较构成的点集，即r 僻) 一扣l ， ，) ，e c ，y ，w e x ，u 弓t x ，如下图所示： 图( 1 - 2 - 3 ) t o o 下面给出一个描述系统在比较诊断模型下是t 一可诊断的充分条件： 引理1 1 删：在比较诊断模型下，多处理机系统g 是f 一可诊断的，( i g l 一) ，若 ( 1 ) n 2 t + 1 ： ( 2 ) 每个结点的阶至少为t ； ( 3 ) 对任意的xc y ，i xi n - 2 t + p ，0 s p 墨f 一1 i z ( x ) b p 。 引理1 2 t u ：在p m c 模型下，多处理机系统g g 以日是f f 一诊断的，当且仅 当对每个整数p ，其中1 s p 墨f 和每个阶为2 p 的点集u ( i u f z p ) ，集合u 的测试点 构成的集合的阶数不少于t p + 1 ，即l n ( u ) t - p + 1 。 引理1 3 乜盯：系统g ，e ) ( i v ( g ) i - ) 在p m c 模型下是f 诊断的的充要条件是 ( 1 ) n 苫2 + 1 ： ( 2 ) r ( g ) 苫2 t 。 定义1 9 ：称系统g ，e ) 的一个顶点y 是局部t 一可诊断的，若对于包含 ，的一 个故障点集f 产生的症状群听，每个同它相容的故障点集f 。都包含矿，且if b f 定义1 1 0 ：结点v 的局部诊断度p ) 定义为g 是局部t 一诊断的最大的t 值。 下y f j e j i 理阐述了系统g 的某一个顶点 ，是局部t 一诊断的充分条件： 引理1 4 1 2 s l ：g 的一个顶点 ，是局部t 一诊断的对v 的任一个子集s ， isl - p ，0 p r 一1 ，y e s ，y 在g - 3 r f l 的连通分支q j 的顶点个数至少为2 ( t - p ) + 1 下而介绍一些关于强局部诊断的相关定义。 定义1 1 1 ：若结点 ，的局部诊断度o ) 等于结点1 ，的度，称y 具有强局部诊断性。 定义1 1 2 ：若图g 的每个顶点具有强局部诊断性，则称g 具有强局部诊断性。 定义1 1 3 ：y 是系统g ，e ) 的一个点，k 为任意一个正整数，顶点y 的阶为k 的 子结构r o ，尼) 定义如下：r ( v ，七) = v ( v ，七) ，e ( v ，七) ，其中i y 卜2 k + 1 ，i e l - 2 k + 1 。如 下图所示： 7 福建师范大学郑淑霞硕士学位论文 ? 幻 i ，：， j 图卜2 _ 4 ：r ( v ，k ) 8 笫2 帝交铅群网络的”行路构造 第2 章交错群网络的并行路构造 2 1 前言 冀有虎提出了一种新的交错群网络a n , ，此网络与彳g 比较，每个结点的度大 约足i f = i 网络的一半且直径与旧网络大致相同。a n 和一一s t a r 网络有相同的度数，但 a k 比万一s t a r 的直径要小1 ，两者具有相同的容错性质，其中a k 是由交错群4 的 c a y l e y 图构造，而s t a r 网络是由对称群& 的c a y l e y 图构造的。同样由4 的c a y l e y 图构造的彳q ，在考虑几k 和彳q 的阶相同的情况下，a m 的度数要比彳q 小得多， 因此前者的性质要更好。因而新交错群网络的优越性显而易见。陈宝兴给出了此交 错群网络的一个最优路由方案。 下面是交错群网络似与常见的超立方体网络q ，星图网络& 及交错群网络 彳q 的一个比较： 网络顶点数度数直径连通度容错直径 q r 万甩万厅+ 1 【半j 玎一1【半j + 1 邑 力!靠一1 n1 【竿j 2 ( n 一2 ) 【半j + 2 a q 2 2 ( n 一2 ) 打l 【半j 万一】【竿j + 3 2 a n 月一1 表( 2 1 1 ) 四个常见拓扑结构的性质比较 图论学者l 2 7 = b h u y a na n dd 只a g r a w a l 、d 兄d u h , g h c h e n , d eh s u 、kd a y 1 7 1 , 允ea l - a y y o u b 及y o s h i y a 蹦i s h i y a m i t l 1 分别构造出了超立方体、广义超立方体、超圆 环面的点不交的并行路，还估计了它们的长度。另外，k h a l e dd a y 和a n a n dt r i p a t h i 1 0 】 构造了星图疗一1 条的点不交的并行路。最近，t s u n g 锄f l 魄功f - r o n g d u h o 。l 构造了 伽，七) 一s t a r s 的点不交的并行路。基于上述思想，本文试图构造交错群图戤的点不 交并行路。 定理2 1 1 超立方体并行路性质n 町 对于超立方体网络包的任意两个结点p 、q ，结点p 与结点q 间存在以一1 条内点 不交的并行路，具体来说，如果d ( p ，g ) i b d ，则有d 条并行路的长度为d ，其余n d 条并行路的长度为d + 2 。 定理2 1 2 星图的并行路性质n 们 9 福建师范大学郑淑霞硕士学位论文 对于星图最的任意两个结点p 、q ，结点p 与结点q 之间存在万一1 条点不交的并 行路，可以作以下的约定，因为星图的点对称性，因此只需构造任一结点p 到元置 换结点e ( e 一1 2 3 以) 的并行路。 设结点p 表示为pc t c 2 c k e 。e 2 白一p l 几见，其中k 个轮换共有忉个变元素， 构造结点p 到结点已的刀一1 条点不交的并行路如下： 1 若p t - 1 ，则有k 条长为d p ，e ) = m + 七的路；掰- k 条长为d p ，e ) 一m + 七的路； 刀一历一1 条长为d 0 , ，e ) + 2 a 聊+ 七+ 2 的路； 2 若a 譬1 ，则有k 条长为d 0 ，e ) - m + 七的路；历- k 条长为d q ，e ) + 2 一肌+ 七+ 2 的路，甩一m 一1 条长为d 0 ，p ) + 4 一m + 七4 - 4 的路； 定理2 1 3 伽，k ) 星图的并行路性质1 1 l 对于o ，k ) 星图中的两个结点p ，q ( q 为单位结点) ，构造这两点之间的之间的 刀一1 条点不交的并行路，假设结点p 中有c 个轮换，聊个变元素，且c 刀 一k 中 的元素个数为e ，那么： 1 若a ；1 ，则有胁+ 勉条长为d ( 瓯j ) 的路；k 一历一e 一1 条长为d ( 瓯j ) + 1 的路； 万- k p 条长度为d ( j ) + 2 的路； 2 若a 乒1 ，则有小+ 勿一1 条长为d ( 瓯j ) 的路；k 一朋一e 条长度为d ( 墨j ) + 1 的路： n - k e 条长为d ( 瓯j ) + 2 的路； 本节在此基础上构造结点p 与e 之间的n 一1 条内点不交的并行路。 2 2 关于交错群的已有相关引理 引理2 2 1 h 町：p e a n 且p 的轮换表示为c l c 2 气，这里q 是一个长度为i q i 苫2 的轮换，f l 2 ，七，若轮换含有( 1 2 ) ，则当p 的其他轮换排序好后，轮换0 z ) 也将 自动地排序好，即不必专门对轮换( 1 2 ) 进行排序。 由上述引理知，在构造并行路过程中，元素1 、2 总是最后回归正确位置，于是， 若p 的轮换表示中含有对换( 1 2 ) ，可令q 一0 2 ) 。 引理2 2 2 h 耵：p 似r p 的轮换表示为c 气，这里c f 是一个长度为j c jj 苫2 的轮换，i = l 2 ，k ，令历一i c l i + i c ：i + + i q l ： ( 1 ) 若3 是不变元素，则 d ( p ，e ) 一肌+ 七当a - 1 且仍r o l l2 ： 2 t n + 七- 3 当a 一2 r p 2 1 ； 1 0 第2 帝交锚群网络的j f ：行路构造 = m + k 当i 扫，p ：) n 扎2 1 1 - 1 ，而且1 或者2 是不变元素； = r e + k - 1 当i 协，p ： n l l 2 l - 1 ，而且1 ，2 属于同一个轮换c l ； = m + 七 当l a ，p ：i n l 2 | o ，而且1 ，2 属于同一个轮换q ： = m + k - 1 当i a ，p 2 i n l 2 i 一0 ，i f i r1 ，2 属于不同的轮换； ( 2 ) 若3 不是不变的元素，则 a ( p ，e ) = ，行+ 七一2当a 一1 且见一2 ； 2 m + 七- 5 当a 一2 且办一1 ； = m + k - 2 当i 协，p ： n 1 , 2 1 i 一1 ，而且1 或者2 是不变元素； = 小+ 七一3 当i a ，p ：) n n 芍i _ 1 ，且1 ，2 属于同一个轮换c l ； = m + k - 2 当i a ，p ：1 n 1 , 2 i 一0 ，i f i f 1 1 ，2 属于同一个轮换c | ； = r e + k - 3 当l 协，p ： n 1 , 2 1 i - o ，而且1 ，2 属于不同的轮换： 由于矾的点传递性，不妨假设单位元e = 1 2 3 n 是任意节点p a p 2 见的 目的结点，p 是从pn e 的路由上的第一个结点，下面是从p 到e 的一个路由算法描 述，其中定义z 3 是将只放回正确位置的一个变换： r o u t i n ga l g o r i t h m ： ( 1 ) i f p 3 3 ，t