（计算机软件与理论专业论文）广度优先搜索算法在互连网络通信中的应用.pdf

摘要 y7 3 8 五1 9 在互连网络中进行通信，由网络拓扑决定的网络延迟是一个静态量，直接受到 网络直径的影响。在网络有故障发生的情况下，故障直径反映了网络的容错能力， 而故障直径的求解本身比较困难。网络寻径是网络通信必须考虑的一个重要方面。 本文针对以上情况研究了广度优先搜索算法在这些方面的应用。作者作出的研 究成果主要体现在以下三个方面： 首先利用广度优先生成树的树高不会高于其他任何同根生成树树高的特点，时 不同的网络进行了。度优先搜索分析，给出了超立方体，交叉立方体，螺旋立方体 等网络的直径与故障直径。并且进步给出了b c 互连网络直彳争的一个界限。这为f i ) f 究新的递归式网络拓扑的直径与故障直径的研究提供了一种新的途径。 其次考虑了至多可以删除多少个顶点才能保证网络的连通，给出了网络的容错 能力。由m e n g e r 定理可以得到b c 互连网络之间至少存在”条内部节点互不相交的 路径。利用广度优先搜索的思想，本文给出了求任意两个节点之间的”条内部节点 互不相交，且在两点问所有路径中是最短的 条路径的算法。该算法为例络故障直 径的提供了依据。而目，在故障存在但是网络连通的情况f ，可以求得网络巾任意 两节点问的n 条最并行路径，提高了网络的容错能力。 最后，通过分布式的广度优先搜索算法给出了互连网络在正常或者有故障存在 但是网络仍然连通的情况下单源广播算法，给出了给定两无故障节点f h j 的最短路径 算法的思想。 本文刈提出的方法及算法的正确性进行了证明，为研究互连网络的性质提供了 新的研究方法。，对于直径与故障直径的算法，我们也已经在低维b c 网络上通过， 验证了算法的正确性。 关键词互连网络：广度优先搜索算法：直径；故障直径；最短路径 a b s t r a c t t h ee r i e c t i v ec o m m u n i c a t i o ni sac r u c i a ic r i t e r i o nr e f l e c t st h ep e r f o r m a n c eo ft h e m u l t i p r o c e s s o rs y s t e m t h e n e t w o r kd e l a yt i m ed e t e r m i n e db yt h et o p o l o g yo ft h e i n t e r c o n n e c t i o ni sas t a t i cm e a s u r e i ti sa f f e c t e dd i r e c t l yb yt h ed i a m e t e ro ft h en e t w o r k w h e nf a i l u r e h a p p e n s 。w e n e e dt or e s e a r c ht h e r e l i a b i l i t y o ft h e s y s t e m 劢e f a u l t d i a m e t e ri n f l e c t st h ef a u l t t o l e r a n tc a p a c i t ya n di ti sh a r dt ob ea t t a i n e d i ti sa l s oa m a i nt a s kt of i n dt h es h o r t e s ta n dr e l i a b l ep a t hw h e nf a i l u r eh a p p e n s i nt h i s p a p e r w eu s e t h eb r e a d t h - f i r s ts e a r c ha l g o r i t h mt o s t u d ya l l t h ea b o v e q u e s t i o n sw e h a v em e n t i o n e dw h a tw ed oi sg i v e na sf o l l o w i n g ： f i r s t ，ab r e a d t h f i r s ts p a n n i n gt r e e i st h es h o r t e s to n ea m o n ga l lt h es p a n n i n gt r e e s h a v i n gt h es a m en o d ea st h e i rb o o tn o d e a c c o r d i n gt ot h i sw eg o tt h ed i a m e t e ro f t h e h y p e r c u b e ，c r o s s e d c u b e ，t w i s t e dc u b ea c c o r d i n g t ot h et h e o r y f u r t h e r m o r ew eh a v e s h o w nt h ed i a m e t e ri i m i to f t h eb cn e t w o r k i t san e wm e t h o dt or e s e a r c hm ed i a m e t e r a n df a u l td i a m e t e ro ft h en e t w o r k n e x t ，w ec o n s i d e r e dt h ef a u l t t o l e r a n tc a p a c i t y w es h o w h o wm a n yn o d e sa n dl i n k a r er e m o v e dc a l lm a i n t a i nt h eg r a p h sc o u n e c t i v i t yb a s e do nm e n g e rt h e o r e m ，w eh a v e f o t , n dn d i s j o i n e dp a t h sb e t w e e na n yt w on o d e si n ag r a p hb yu s i n gt h eb r e a d t h f i r s t s e a r c hm e t h o d t h e r ei sn op a t hs h o r t e rt h a nt h e s e d i s j o i n e dp a t h s t h e nw eg e tt h e f a u l t d i a m e t e ro fan e t w o r k l a s t ，w ed i s c u s s e dt h ed i s t r i b u t e db r e a d t h f i r s ts e a r c ha l g o r i t h m i nap r a c t i c a l p a r a l l e ls y s t e m ，t h ed i s t r i b u t e db r e a d t h f i r s t s e a r c ha l g o r i t h mc a ng i v et h eo d e t o a l l r o u t i n gp a t h s ，e v e nt h e r e e x i s tf a u l t yi nt h en e t w o r k w ea l s og i v eas i m p l ea l g o r i t h m u s i n gt h eb r e a d t h f i r s ts e a r c hi d e a b yt h ea i g o r i t l u nw e c a ng e tt h ep a t hb e t w e e na n y t w og i v e nn o d e sw h e nt h en e t w o r ki sc o n n e c t e d t h em e t h o da n da l g o r i t h mg i v e ni nt h i sp a p e rh a v eb e e np r o v e dc o r r e c t i t san e - v m e t h o dt os t u d yt h en e wi 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 , a n di th a v et e s t e di nt h el o w d i m e n s i o nb ci n t e r c o n n e c t i o nl i e t w o r k k e y w o r d s i n t e r c o n n e c t i o nn e “v o r k ；b ci n t e r e o n n e c t i o nn e t w o r k ；b r e a d t h f i r s t s e a r c h a l g o r i t h m ；d i a m e t e r ；f a u l t d i a m e t e r ；s h o r t e s tp a t h 引言 引言 并行处理系统是当今计算机科学研究的热点之一。多处理机互连网络 ( i n t e r c o n n e c t i o nn e t w o r k s ) 是指由若干个处理器按照一定方式相互连接构成的网络。 简称互连网络。在一个互连网络中，每个处理器都有本地内存储器和资源，处理器 之间通过通讯路线相连。它们之间通过通讯路径传递信息，协作完成任务。互连网 络是随着信息技术与计算科学的发展而产生的一个跨数学与信息科学的研究领域。 互连网络的研究在图论、算法设计与分析、计算机体系结构、并行与分布计算、计 算机网络与通信以及超大规模集成电路的设计等诸多方面都起着非常重要的作用。 特别是近几年以来，随着计算机与通信技术的密切结合，对互连网络的研究也越来 越受到重视。在一个多处理嚣系统中，处理器之间的有效韵通信是衡量系统性能的 一个重要标准，相关的研究已成为当今研究的一个重要方面。 现在，网络的超大规模化必将导致对网络的抗破坏能力、通信算法的有效性、 网络的易扩展性以及可重构性等的要求越来越高，因此，如何在多种因素的影响下 进行网络的优化设计变得十分重要。影响网络设计的因素有很多方面，如：费用、 时延、可靠性等。而这些因素表现在对网络图本身参数的限制，如：连通度、直径、 容错度等。 目前对互连网络进行研究通常将其抽象为图，将每个处理器看作图中的节点， 处理器之间的连接看作图的边。从而把对互连网络进行的研究转化为对相应的图进 行研究。一个好的互连网络具有以下性质：小的网络直径、高连通度、处理器的低 连接数：并具有可嵌入性、可扩展性、可诊断性与容错牲、正则性和好的通信算法 等。网络中延迟包括网络延迟和通信算法引起的动态延迟。由网络拓扑结构决定的 网络延迟是一个静态量，直接受到网络直径的影响，因此在提出新的互连网络的拓 扑结构时，直径是首先要研究的一个最基本的属性。 在并行系统中，高速运行的处理器发生故障是不可避免的。处理器之间的连接 也会出现故障。在故障存在的情况下，需要研究系统的可靠性，也就是怎样在网络 发生故障的情形下仍能保证互连网络中无故障的处理器之间进行可靠的信息传送， 这是互连网络的容错性问题。连通度的高低是衡量一个互连网络容错性优劣的重要 标志。互连网络容错度越高，其容错性越好。 在网络中，处理器之间需要不断地通过通信，进行信息的传递，从而协作完成 任务。在一个多处理器网络中，信息的传送方式有两种。一种是“一对一”的传 送方式，即出一个源处理器将信息送至另一个目标处理器。另一种信息传送方式是 多点传送方式( m u l t i c a s t ：o n e t o m a n y ：m a n y t o m a n y ) ”3 4 1 ，它可通过基于单 青岛大学硕士学位论文 点传送的算法来实现或单独设计模型和算法来实现。信息的传送要求快速可靠。在 传递过程中信息每经过一个中间处理器就有一段时间的延迟，因此，两个处理器之 间的最短路径就成为它们之间的最优通信路径，如何寻找处理器之间的最短路径就 是路径选择。有关路由的设计包括两个基本方面：决定最优路径和传送消息群。其 中传送消息远不如路径选择那样困难，前者属于n p 问题。因此如何找到一条最优路 径是研究路由算法的目标。 在网络故障存在的情况下，设法找到不经过故障节点和故障边的可靠的且尽可 能短的路径进行信息的传送。容错路径的选择也存在两种情况以保障可靠的信息传 送，即一到一的容错路由选择和多点( 到多多到多) 容错路由选择问题。后者可 以通过前者实现。因此一到一的容错路由选择算法是最基本的路由选择算法。 根据m e n g e r 定理：一个图的节点连通度( 简称连通度) 为月，当且仅当该图的 任意两个节点间存在至少疗条内部节点互不相交的路径”】，设一个图的连通度为n ， 只要该互连网络中故障处理器个数不超过 一1 ，该互连网络中任何两个无故障处理 器间就一定至少存在一条可靠性路径。如何在较短的时间内求出该路径并使该路径 尽可能短? 近年来，这个问题引起了广泛关注并有了一些解决方法，例如禁止故障 集 6 】方法，容错虫洞路由算 去【7 ，8 1 等。在网络有故障发生的情况下，任意两个无故障 节点之间不经过故障节点和故障边的距离的最大值称为故障直径f 5 1 。故障直径也是 网络性质的一个重要衡量标准，其求解很困难【9 j o ，“j 。 国际上已提出了许多种互连网络，其中超立方体互连网络成为系统设计者们的 主要选择。它具有许多优越的性质，如它具有对数级的直径和最高连通度( 从而也 具有最高容错度) 等等，因而已研制出了许多超立方体并行机，如n c u b e ，c m 一2 ， i p s c 一8 6 0 ，而这些并行机的研制和使用叉引起了人们对超立方体深入研究的兴趣。 在对各种互连网络的研究成果中，关于超立方体的研究成果占很大的比重【i “。但是， 超立方体并不是各方面性质都最好的互连网络，研究者开始对超立方体的一些变型 及性质进行研究，如：交叉立方体0 3 1 ，c c c s ( c u b e c o n n e c t e d c y c l e ) ”， s u p e r c u b e i 科，t w i s t e d c u b e 【1 6 】。b r i d g e dh y p e r c u b e s l l 7 】，g e n e r a l i z e dh y p e r c u b e s ， e n h a n c e dh y p e r e n b e s t l 9 】，m f b i u s 立方体【2 0 1 等。 超立方体的直径已经被证明为n 2 h 。关于超立方体故障直径，则只在文献 2 2 1 中 给出了在故障节点不超过2 n 一2 的情况下的一个上界为 + 2 ：另外一种拓扑结构一 r，1r 螺旋立方体于1 9 8 7 年提出1 ，直径为i 冬 l 1 6 l ，故障直径为l 昙 + 2 ，大约也是 1 li z1 超立方体的一半。交叉立方体于1 9 9 1 年提出来旧2 。它是通过改变超立方体的一些 边的连接得到的。它具有超立方体大多数好的性质，其拓扑结构的改变使其具有了 一些比超立方体优越的性质，其直径大约是超立方体的半【2 4 1 ，更精确地表示为 引言 字 立方体 这使得一些并行算法只需要大约超立方体一半数量的通信步：对于m 6 b i u s 文献已经证明在h ：4 时，0 - 型为螋1 ，在 = l 时，卜型为阻竺尘1 。 i 2 ii 2 l 上述所提到的互连网络直径的获得都是通过在给出具体的寻径算法以后得出的，特 别是故障直径的求解是比较困难的。文献中求故障直径的算法都是研究者针对不同 的网络拓扑给出不同的路由算法，然后对算法的正确性进行证明分析得到的。 本研究将根据以下广度优先生成树的特点，即广度优先生成树的树高不高于其 他任何同根生成树的树高，来研究互连网络的直径故障直径，这对研究互连网络的 性质是一个新的探索，具有一定的意义。 广度优先搜索算法( 又称广度优先搜索) 是最简便的图的搜索算法之，在许 多教科书中都已经出现。这一算法也是很多重要的图算法的原型，例如d i j k s t r a 的 单源最短路径算法和p r i m 最小生成树算法都采用了和广度优先搜索类似的思想。可 以证明通过广度优先搜索算法得到的广度优先生成树的树高是所有同根生成树树高 最小的，保证了根到各个节点的距离是最短的，从而得到网络的直径。而且从根至 叶结点的路是最短路径。根据互连网络的直径故障直径定义我们知道利用广度优先 搜索算法研究互连网络的直径故障直径是可行的。而在有故障发生的情况下，我们 对故障节点以及故障边的研究也是有重要意义的。本研究将广度优先搜索算法应用 到网络通信中，研究在无故障和有故障发生的情况下单点传送以及多点传送算法。 作出的研究成果主要在以下三个方面： 首先本文利用广度优先生成树的树高不会高于其他任何同根生成树树高的特 点，对不同的网络了进行广度优先搜索分析，给出了超立方体i i “、交叉立方体”、 螺旋立方体、m o b i u s 立方体t 2 0 等的真径。并且进一步给出了b c 互连网络 2 s l 直径 的一个界限。这为研究新的递归式网络拓扑的直径与故障直径的研究提供了一种新 的途径。 其次本文考虑了至多可以删除多少个顶点才能保证网络的连通，给出了网络的 容错能力。出m e n g e r 定理可以得到b c 互连网络之间至少存在h 条内部节点互不相 交的路径。利用广度优先搜索的思想，本文给出了求任意两个节点之间的h 条内部 节点互不相交，且在两点间所有路径中是最短的”条路径的算法。该算法为网络故 障直径的提供了依据。而且，在故障存在但是网络连通的情况下，可以求得网络中 任意两节点间的n 条最并行路径，提高了网络的容错能力。 最后，本文通过分布式的广度优先搜索算法给出了互连网络在正常或者有故障 存在但是网络仍然连通的情况下单源广播算法，给出了给定两无故障节点间的最短 路径算法的思想。 青岛大学硕士学位论文 本文对提出的方法及算法的正确性进行了证明，为研究互连网络的性质提供了 新的研究方法。对于直径与故障直径的算法，我们也已经在低维b c 网络上通过， 验证了算法的正确性。 本文分六个部分讨论了广度优先生成算法在互连网络中的应用。在第一章中给 出了关于互连网络的基础知识和几种立方体互连网络的定义。第二章讨论了广度优 先搜索算法与立方体互连网络的直径。第三章讨论了广度优先搜索算法与网络的故 障直径。第四章给出了在无故障或有故障情况下两点间最短路径的算法。在文章的 最后，我们对所述问题进行了总结与展望。 第一章预备知识 第一章预备知识 1 1 图论基础知识 新型并行机的研制依赖于对新型互连网络的设计以及对甄连网络的内在性质的 研究，互连网络的设计是一个多目标最优化问题，这些目标包括小的网络直径，高 连通度，每个处理器与其他处理器间的低连接数，可嵌入性，可扩展性，可诊断性 与容错性，正则性和好的通信算法等等。互连网络的不同性质问是相互制约的。一 般来说，不可能存在一种各方丽性质都最好的互连网络。由于很难使每个目标都达 到最优，因此，在互连网络设计中总是根据具体情况选择几个晟基本的目标使其最 优。 网络直径是互连网络的一个最基本的，重要的目标因素。在并行处理系统中，处 理器之间的通信是非常重要的。小的网络直径可以节省并行处理的通讯步，缩短信 息的传输时间，提高通讯效率。是不同的互连网络必须考虑的一个重要方面。 目前，国际上已提出了许多种互连网络，其中超立方体互连网络因为具有相对小 的直径及其每个处理器与其它处理器之间较小的硬件连接数而成为最流行的互连网 络之一，关于超立方体的研究成果占很大的比重【1 2 1 。一个力维超立方体多计算机系 统，包括2 ”个独立的有本地存储器的处理机。每个处理机被指定一个唯一的胛位地 址。当且仅当两个处理机地址中只有一位不同时就将它们连接起来。这样一个处理 机就有n 个处理机直接相连与之相连，超立方体是具有2 ”个顶点和玎2 ”条边的，z 一 正则图。 但是，超立方体并不是直径最小的互连网络，研究者开始对超立方体的一些变型 及性质进行研究，1 9 9 1 年，k e m a le f e l 提出了超立方体的一个变形一交叉立方体 ( c r o s s e dc u b e ) 1 1 3 】。它具有和超立方体相似的性质，如”维交叉立方体l 蟛，是具有2 ” 顶点和n 2 ”1 条边的 正则图。但其拓扑结构的改变使其具有了一些比超立方体优越 r1 的性质，如其直径大约是超立方体的一半1 3 , 2 4 1 ，更精确地表示为11 生 这使得某些第 1 2 l 法，例如半群计算，矩阵乘法，排序等，只需要大约超立方体一半数量的通信步。 交叉立方体还具备了其他如嵌入【1 3 , 2 6 , 3 0 ，可诊断性【2 7 】，h a m i l t o n 连通性等一砦优 越的性质。 1 9 9 5 年，c u l lp a u l 提出了另外的一种超立方体的变型莫比乌斯立方体( m b b i u s c u b e ) 2 0 l ，它也具有和超立方体相似的性质，如f 维交叉立方体c q 是具有2 ”个顶 点和，2 2 川条边的胛正则图。它的直径大约是超立方体的一半，l - 型莫比乌斯立方体 青岛大学硕士学位论文 具有比超立方体，螺旋立方体更好的动态信息传递性能，且任一长度为，( 4 ，2 一) 的圈能以扩张f 嵌入珂维莫比乌斯立方体( 胛2 ) f 2 9 】。 1 9 9 9 年，c pc h a n g 等在文献 1 6 , 2 3 l 中详细给出了螺旋立方体的定义以及对其性 质的研究。并且给出了其直径为f ! 世的算法。 i 2 1 对互连网络的性质进行研究时，我们通常将其抽象为一个图g 。这里我们采用文 献【5 】中的图论术语。设g ( v ，e ) 表示一个无向图，v = v ( o ) 表示图中顶点的集合， e = e ( g ) 表示图中边的集合。图的顶点度数和边连接数分别用符号v ( g ) 和e ( g ) 表 示。若图g 中的一条边e = ( 甜，v ) ，她称”与v 是邻接的。边e 称为与顶点“，v 关联， “，v 称为边e 的端点。若g = g ( ，e ) ，v e v ( g ) ，e e ( g ) ，且e i 中边所关联 的顶点在v 中，则称g 为g 的子图。g f 表示从g 中删去边集e 的子集f 所得到 的予图；g v 表示从g 中删去顶点集v 的子集v 。以及它们的关联边所得到的子图； n ( v ) 表示在图g 中所有与顶点v 相邻接的顶点的集合，( v ) 表示在图g 中所有与v 关 联的边的集合，n o ) 和j ( d 分别称为邻接集和关联集。 定义1 ，1 i s 网络直径的定义： 图g 中节点“，v 之间最短路径的长度为图g 中节点“，v 之间的距离d i s t ( g ，吖，v ) 。 网络直径是指该网络所对应的途中任意两个顶点之间距离的最大值，即图g 的直径 d ( g ) = m a x d i s t ( g ，“，v ) l “，v 矿( g ) 。 定义1 ，2 t 5 1 图g 中与顶点v 关联的边数称为g 中顶点v 的度，用d 。( v ) 表示，显然 正i ( v ) 刊，( v ) | 。若对所有v g ，d 。( v ) = n ，则称图g 是”正则的。图g 的最小顶 点度数用3 ( g ) 表示。 1 2 交叉立方体 定义13 1 1 3 , 3 1 1 长度为2 的二进制串x = x i x 0 和y = y l y o 是关联对，当且仅当 ( x ，y ) ( 0 0 ，o o ) ，( 1 0 ，l o ) ，( o l ，1 1 ) ，( t l ，0 1 ) ) ，我们记作x ya 反之x 与y 不关联。 定义14 c 】交叉立方体的递归定义： c q , 是两个节点标识分别为0 ，1 的完全图c q 。由两个子立方体c 鳞0 1 和 c 噬一l 组成，2 1 节点“= “。一l 。一2 “o r ( c 酢1 ) ，v = v n l k 2 ，v o ( c 残一1 ) ， 其中“，。= 巧。：0 ，节点“，v 在c q 中是相邻的，当且仅当 l ，“，2 = v n 一2 ，若 是偶数；并且 第一章预备知识 2 1 1 2 f + i u 2 f v 2 f + l y 2 f ，o - i l ( n 一1 ) 2 j 图1 1 给出y - + 3 维交叉立方体吧。 图1 1 3 维交叉立方体c q 3 定义1 5 p 设 ，v ) e ( c g ) ，当节点“= y n - i n - 2 3 d 。v ( c g ) ， v = y n - i y n - 2 - y o v ( c o n ) 的最左不同比特位的下标为i 时，令v = “并且称v 是“ 的f 一邻接点，边 ，v ) 是i 维的或称 ，v ) 为i 维边( d i m i e d g e ) ，记做d i m ( u ，y ) = i 根据上述定义，当节点“和 l d 在门一1 位有最左不同比特位时，v 表示为“” 例如，鄢= 0 0 1 l l ，d i m ( u ，订= 4 ，则甜的一1 ) 一邻接点v = 砧( n - 1 ) = 砧( 4 ) = 1 1 1 0 1 。 1 3 螺旋立方体 螺旋立方体记为7 该，是疗维超立方体的一个变体。螺旋立方体和超立方体具 有相同的结点数和边数。以下的讨论限定在奇数维螺旋立方体中。令n = 2 m + l ，为 了构造螺旋立方体，我们移走超立方体的一些边，代之以跨两维的边，这样就保留 了原有的n 2 ”。条边。为精确起见，令“= u n _ l u 。一2 “l “。作为觋一个顶点。我们定 义一个奇偶函数p f ( ) = 蚱o “0 o 。如果p 2j _ 2 ( “) = o ，1 ，m ，我们就将 第 f 2 一1 ) 一拍 的边转到定点 v ，这早 v 2 y v 2 ，一1 = u 2 j u 2 j l ，a n dv i = l , l i ，f 2 j ，i 2 j l ，这样的边称为t w i s t e d e d g e s 。 定义1 6 ：螺旋立方体的递归定义 一个一维螺旋立方体7 n 是一个具有两个顶点的完全图。h 为个大于3 的奇整数。 我们将殛的节点分为四个子集s 0 , 0s o ，- ，s 1 , 0 s 1 ”，s i , ，由这样的顶点“组成， “川= f ，“。一2 = j 。对于每一对( f ，) ( 0 ，0 ) ，( 0 ，1 ) ，( 1 ，0 ) ，( 1 ，1 ) ) ，由此得到的矸b 的 子图s u 同构于r q ，。连接四个子图的边可以定义如下：任何一个顶点 青岛大学硕士学位论文 u n - 1 “h 一2 u 1 “。如果只z 一3 ( 甜) = o ， 则“与定点一u n - 1 1 , 1 2 u n 一3 “1 和 云n i 一2 u 。一3 “l ；如果n 一3 ) = 1 ，则连接“与u n l u ，2 u n 一3 “1 和 g i n l b l n 一2 一3 z t l u o 。 图1 2 给出了一个3 维螺旋立方体飓。 图1 2 3 维螺旋立方体z 骇 定义1 。7 5 1 6 】“= “。一i 群。一2 确u o 的i 确一邻接点记为z f ( 。) 1 4m b b i u s 立方体 定义1 8 t 3 2 11 维m 6 b i u s 立方体是具有两个顶点0 和1 的完全图。对门2 ，行维 m o b i u s 立方体 包含一个。一型h 一1 维予m o b i u s s 立方体j j i 罐l 和- - + 1 一型h 一1 维 予m o b i u s 立方体职一l 。埠i 的每个顶点的第一位均为0 ，碑一的每个顶点的第 一位均为i 。对两个顶点x = 吃砀矿( m 墨1 ) 和_ y = m 虼y 。矿( 弼一1 ) ， 这里_ = 两= 0 ， ( 1 ) ( x , y ) e ( o m n ) 当且仅当而= 雎，i = 2 ，3 ，门。 ( 2 ) ( x ，y ) e e ( 1 一m 。) 当且仅当t = 一y i ，i - - - 2 ，3 ，肝 图1 3 就分别是一个0 型4 维m o b i u s 立方体和一个1 型4 维m o b i u s 立方体 磊i；o | l _ 囊 爻 粪 旷、卿i。嘲 f 0 8 第一章预备知识 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 ii 1 0 0 1 0 0 n 、1 1 0 1 ：a l o o o - , i o n 图1 34 维m o b i u s 立方体 1 5 b g 互连网络 通过以上对超立方体，交叉立方体，螺旋立方体以及m o b i u s 立方体等的介绍， 我们将一类连通度为h 的n 正则网络定义为n 维b c 互连网络。 定义1 9 2 5 l一个1 维的b c 网络置是具有两个顶点的完全图。一维b c 图族定 义为厶= ( 墨) 。假设g 是一个，l 维b c 图记为瓦，如果存在，kc y ( g ) 使得以下 条件成立： ( 1 ) 矿( g ) = y o u r , ，a ，k o ，a n d n v l = a ；a n d ( 2 ) v o 卜旦斗k ，g 【】厶+ a f l d g 【k 】l 一- 7 维b c 图族记为l = g i g 是一个n 维b c 图) 根据定义1 9 ，如果有以e l , ，则必然存在，ke l , _ l ，使得y ( ) 卜五_ 矿( ) 图1 4 给出了两个三维b c 图，其中第一个类似交叉立方体，第二个类似超立方体的 连接。 图1 4 两个三维b c 图 0 0 1 第二章广度优先搜索算法与互连网络的直径 第二章广度优先搜索算法与互连网络的直径 2 。l 互连网络上的广度优先搜索算法 广度优先搜索算法( 又称宽度优先搜索) 是最简便的图的搜索算法之一，这一 算法也是很多重要的图的算法的原型。在许多的教材中都已经介绍了这种搜索算法 的基本原理。d i j k s t r a 单源最短路径算法和p r i m 最小生成树算法都采用了和广度 优先搜索类似的思想。根据互连网络的直径故障直径定义我们知道如果已经知道互 连网络中任意两个处理机之间的最短路径的长度，就可以得到该互连网络的直径 故障直径。可以证明广度优先搜索算法能够正确地计算出给定处理器之间的最短路 径。 广度优先搜索算法的原理是，设图中一个顶点s 为源节点，广度优先搜索算法以 一种系统的方式探寻g 的边，从而发现s 所能够到达的所有未访问过的节点，并且 计算j 到这些节点的距离，然后以j 的邻接点为新的节点继续搜索。该算法在完成搜 索的同时，生成一棵根为s 包括所有可达节点的广度优先生成树。可以看出算法首 先搜索和s 距离为k 的所有节点，然后再去搜索和s 距离为k + 1 的其他可达节点v ， 因此广度优先生成树中的从s 到v 的路径就是图g 中从s 到v 的最短路径。树中每个 节点至多有一个父亲节点。 在网络中进行通讯时，由网络拓扑属性决定的网络延迟是一个静态量，直接受 到网络直径的影响，因此网络直径是互连网络的一个重要属性。广度优先搜索算法 ( b r e a d t h f i r s ts e a r c h ) 是最简便的图的搜索算法之一。传统的广度优先搜索算 法在实现图的搜索方面具有很大的局限性，不能够应用于实际的并行系统中。但是， 我们利用广度优先搜索的特点结合一类互连网络的特征，通过分析广度优先生成树 给出了一类互连网络的直径求解方法，为研究互连网络的性质提供了新的方法。在 广度优先搜索过程中会生成一操广度优先树，简单记为b f s t 。一个图的广度优先 生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，本文以b c 互连 网络为主，通过分析各种立方体的广度优先生成树的特征，给出了网络直径的另外 一种求解方法。为研究新的互连网络的直径故障直径问题提供了一条新的思路。 互连网络通常被抽象成一个图来对其性质进行研究，设g 是一个图，我们用 既g 1 和e ( g ) 分别表示图的节点集和边集。我们绘出网络节点以二进制字符审标识的 h 维互连网络上的广度优先搜索算法。 算法2 1 青岛大学硕士学位论文 给定节点 = u o l l l u n _ 2 9 l v ( g ) 数据结构：每个节点是具有”个指针的结构体类型 | t 节点的访问情况由队列控制 p u t “i n t oq u e u eo w h i l eqi sn o te m p t y b e g i n v = g e t t o p ( q ) ：j = 0 ： f o ri = 0t o 拧一l 搜索v 的 个邻接点 b e g i n w = v ( ：“的i 一邻接点 i fwh a sn o tb e e nv i s i t e d v 1 i n k j + + 】= w ：l i n k 为指向其孩子节点的指针 wi sm a r k e dv i s i t e d ： w p a r e n t = v ：w 的父节点为v p u s h wi n t oq ： e n d ： d e l e t evf r o mq ： e n d ： 2 2b f s 与交叉立方体的直径 图2 1 是我们假定源节点是其标识位全为0 的节点，将算法2 1 应用到1 维到4 维交叉立方体上后得到的广度优先生成树( b r e a d t h f i r s ts p a n n i n gt r e e ) ，简记为 b f 双。 引理2 1 【1 3 1 交叉立方体的连通度为n ，记k ( c q ) = n f o r a l l 珂l 由引理2 1 知交叉立方体是一个n 一正则图，从而交叉立方体的节点对称。由节 点的对称性我们知道任意一个节点为源点得到的b 船，与以0 标识为源节点得到的 b f s t 是同构的。 下面我们对文中用到的符号进行定义： 用u = h o u l 甜p 2 甜n 一1 ，v = v o v l y n 一2 “h l 来表示c q 中的节点。二进制串 h o w l l l k _ 1 称为“的尼一前缀，记为p k ( u ) 。 第二章广度优先搜索算法与互连网络的直径 c o + 2 中以b l = t l o h