（计算机软件与理论专业论文）基于torus网络的容错性研究.pdf

基于t o m s 网络的容错性研究 摘要 互连网络是改善并行计算机性能的一个关键因素。t o r u s 网络作为直接 网络中典型的拓扑结构之一，具有很多优越的性质。随着处理器数目的增 多，网络容错性成为一个不可回避的研究课题。因此本文主要研究t o r u s 网 络的容错性及容错路由算法。 首先，本文基于k t o m s 子网及概率模型研究t o r u s 网络的容错性，给出 一个简单的容错路由算法。在节点出错概率相互独立的假设下，计算出容 错路由算法成功返回由正确节点组成路径的概率。对于几十万个节点以上 的t o r u s 网络，提出的容错路由算法找到由正确节点组成路径的概率可达 9 9 ，从而说明了t o m s 网络是一个容错性很强的网络拓扑结构。 然后，本文研究t o r u s 络中基于局部故障信息容错路由算法的实现， 即给出一个基于标志位的容错路由算法。存储于t o r u s 网络中各节点的标志 位记录了系统中的故障信息，用于判定消息的源节点和目的节点之间是否 存在最优通路。标志位的赋值是通过与邻节点之间的信息交换来完成，因 此所提的容错路由算法本质上是基于局部故障信息的。 最后，本文改进了一个针对超立方体网络提出的防止消息往返的容错 路由算法。对于任意给定的源节点和目的节点，改进后的容错路由算法均 能够找到一条路径长度接近于两个节点之间最优路径长度的容错路径。算 法仍然只需要知道其邻节点的信息，而无须知道整个网络的情况。 关键词：互连网络t o r u s 网络k - t o r u s 子网概率分析局部故障信息 容错路由 n r e s e a r c ho ff a u l tt o l e r a n c eb a s e d0 nt o r u s n e t w o r k s a bs t r a c t t h ei n t e r c o n n e c t i o nn e t w o r k su s e di nm a s s i v e l ym u l t i p r o c e s s o rp a r a l l e l s y s t e m sa r eo n eo ft h ed o m i n a t i n gf a c t o r sw h i c hm a d et h ep e r f o r m a n c eo ft h e s y s t e m sb e t t e r t o m sn e t w o r k sa sak i n do ft h et y p i c a lt o p o l o g i e so fd i r e c t n e t w o r k sh a v eal o to fa d v a n t a g e o u sc h a r a c t e r s w i t ht h ei n c r e a s i n gn u m b e ro f p r o c e s s o r s ，f a u l tt o l e r a n c eo fn e t w o r k sh a sb e c o m ear e s e a r c ht o p i ct h a tc a i ln o t b ea v o i d e d s ot h ef a u l tt o l e r a n c eo ft o m sn e t w o r k sa n dt h ef a u l t t o l e r a n t r o u t i n ga l g o r i t h m sa r em a i n l yr e s e a r c h e di nt h i sp a p e r i nt h i sp a p e r , f i r s t l y , b a s e do nt h ec o n c e p to fk - s u b t o r u sa n dp r o b a b i l i t y m o d e ，t h ef a u l tt o l e r a n c eo ft o m sn e t w o r k si sr e s e a r c h e da n daf a u l t t o l e r a n t r o u t i n ga l g o r i t h mi sp r o p o s e d u n d e rt h ea s s u m p t i o nt h a te a c hn o d eh a sa n i n d e p e n d e n tf a i l u r ep r o b a b i l i t y , i ti sa b l et oc o m p u t et h ep r o b a b i l i t yo ft h e f a u l t - f r e e r o u t i n gp a t hw h i c hf o u n db yt h er o u t i n ga l g o r i t h m f o rt h et o m s n e t w o r k so nw h i c ht h e r ea r em o r et h a nh u n d r e d so ft h o u s a n d sn o d e s ，i ti sa t l e a s t9 9 t h ep r o b a b i l i t yt h a taf a u l t - f r e er o u t i n gp a t hc a nb ef o u n db yt h e r o u t i n ga l g o r i t h mp r e s e n t e di nt h i sp a p e r , t h u st os h o wt h a tt h ef a u l tt o l e r n a c eo f t o m sn e t w o r k si sv e r yg o o d i i i s e c o n d l y , t h ef a u l t t o l e r a n tr o u t i n ga l g o r i t h mf o rt o m sn e t w o r k sb a s e do n l o c a li n f o r m a t i o ni sr e s e a r c h e d af a u l t - t o l e r a n tr o u t i n ga l g o r i t h mf o rt o m s n e t w o r k sb a s e do nt h ec o n c e p to ff l a gb i ti sp r o p o s e d f l a gb i ts t o r e do ne a c h n o d eo ft o m sk e e pf a u l t yi n f o r m a t i o na n di n d i c a t ew h e t h e rt h e r ei sa no p t i m a l p a t hf r o mt h es o u r c et ot h ed e s t i n a t i o n t h ev a l u eo ff l a gb i tc a nb ed e t e r m i n e d b b 7e x c h a n g e i n gi n f o r m a t i o nb e t w e e nn e i g h b o r s ，s ot h ep r o p o s e df a u l t - t o l e r a n t r o u t i n ga l g o r i t h ma c t u a l l yb a s eo nl o c a li n f o r m a t i o n f i n a l l y , a f a u l t - t o l e r a n t r o u t i n ga l g o r i t h m f o r h y p e r c u b eb y w h i c h m e s s a g ec a nb ep r e v e n t e df r o mo v e r l a p i n gi si m p r o v e d f o rt h eg i v e np a i ro f s o u r c en o d ea n dd e s t i n a t i o nn o d e ，t h ei m p r o v e da l g o r i t h mc o u l df m da b e t t e r - p a t h t h el e n g t ho ft h er o u t i n gp a t hc o n s t r u c t e db yt h i sa l g o r i t h mi sv e r y c lo s et ot h eo p t i m a ll e n g t h t h ei m p r o v e da l g o r i t h ma l s on e e d st ok n o wo n l yi t s n e i g h b o r s s t a t u s ，a n dd o e sn o th a v et ok n o wt h eg l o b a li n f o r m a t i o no ft h e n e t w o r k s k e yw o r d s ：i n t e r c o n n e c t i o nn e t w o r k s ；t o m sn e t w o r k s ；k s u b t o m s ； p r o b a b i l i s f i ca n a l y s i s ；l o c a li n f o r m a t i o n ；f a u l t - t o l e r a n tr o u t i n g a l g o r i t h m ； 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：霹碳 学位论文使用授权说明 夕彩肛6 月多弓r 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发红时j 日j ： 凼f 】时发布口解密后发伟 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：孪银 导师签名： 工护节年乡月2 弓r 辫群 广西大学硕士掌位论文 基于t o r u s 网络的容错性研究 1 1 论文的选题背景及意义 第一章绪论 随着科技与经济的快速发展，在太空、国防、科学和制造业等各个领域已经出现了 大量具有巨大挑战性的应用问题，它们要求计算机的浮点运算达到每秒钟万亿次级，甚 至更高。一种解决方法是设计一种性能提高一个数量级的处理器。由于处理器正变得越 来越复杂，设计成本不断提高，因此此方法并不实际。另一种可行的解决方法是利用商 品化部件( 处理机、存储器、磁盘、互连网络，等等) 来构建并行计算机。在并行计算 机中，一个大型问题可以由多个处理器来共同解决。 我们知道，并行计算机需要某种通信子系统来连接处理器、存储器、磁盘和其他外 围设备。因此，能否设计高性能的互连网络已经成为改善并行计算机性能的个关键问 题。一个好的互连网络拓扑结构，应该具有较小的网络直径，从而可以节省通信步；具 有较高的连通度，从而提高互连网络的可靠性和容错性；具有较好的可嵌入性，从而提 高模拟其他网络拓扑结构的能力等等。根据网络拓扑结构的不同，可以将现有的互连网 络分为四大类：共享介质网络、直接网络、间接网络和混合网络。其中，直接网络是一 种很流行的网络拓扑结构，不仅伸缩性好而且支持大数量的处理器。而本文所要研究的 t o m s 网络是直接网络中非常典型的网络拓扑结构，它是一种严格正交的网络拓扑。严 格正交拓扑的一个优势是路由简单，那么就可以使用硬件来实现高效的路由算法。此外， t o m s 网络还有很多优点：具有较小的网络直径；所有节点的度数相同( 均为2 n ) 使之 规整且对称；递归的结构；路径多样性等等。总之y o r u s 网络是一种结构简单、可扩展 性好、容易实施、在很多的并行计算应用中能约简消息的延时及网络通信能力可扩展的 网络拓扑结构。因此许多并行计算机系统体系结构采用了t o m s 网络拓扑结构作为处理 机之间的互连网络结构，如c r a yt 3 d 1 1 1 、c r a y t 3 e 2 1 、i w a r p 3 1 、j - m a c h i n e 4 1 等。 互连网络的性能主要依靠网络拓扑、路由算法及消息交换方法【5 】。互连网络中的许 多处理机同时高速运行着，它们之间经常要进行消息传送。随着处理机数目的不断增多 和系统规模的不断增大，网络中节点和链路出现故障是不可避免的。怎样确保互连网络 中无故障的处理器之间在某些处理器( 或链路) 发生故障的情形下仍能进行可靠的消息 传送，这就涉及到互连网络的容错性问题。网络容错可以通过两种方式实现，一是通过 广西大掌硕士掌位论文 基于t o r u s 网络的容错性研究 增加冗余节点或链路来实现【5 】。二是设计并使用容错路由算法，当出现故障时，寻找另 一条通信路径【6 j 。第一种方法改变了网络拓扑，很难实施并且代价很高，因此此方法并 不实用。而第二种方法利用拓扑结构本身路径多样性的特点，不需要增加多余的组件， 网络拓扑也不需要改变，因此实现网络容错的关键就是设计高效的容错路由算法。 国内外已经有很多学者对直接网络的容错性及其上的容错路由算法进行研究，但主 要以超立方体、m e s h 网络为主，而基于t o m s 网络的容错性研究并不多见，由于t o m s 网络具有结构简单、可扩展等许多优点，可以预见其应用前景十分广泛，而开展t o m s 网络容错性研究对推动t o m s 网络的发展具有重要的学术意义和实际意义。 1 2 国内外研究现状 目前，国内外已经有很多学者对直接网络的容错性进行研究，但主要集中于超立方 体及m e s h 网络。由于实现网络容错的关键是设计高效的容错路由算法，而容错路由算 法的提出是基于某种模型的，下面将从容错模型及容错路由算法两方面介绍国内外的研 究现状。 在容错模型方面，以不断增强网络容错能力为目的，国内外研究者提出了基于m e s h 或超立方体网络的多种容错模型，它们在容错性、简单性及是否需要网络的全局状态信 息等方面各有侧重，下面是一些m e s h 或超立方体网络上容错模型的简单介绍。 文献 7 最先提出转弯模型，该模型通过限制某些方向的转弯来阻止环的产生，从而 找到最小和高度自适应性的路由；文献 8 提出最为典型的容错模型：错误块模型，所有 的错误节点分别包含于一些不相交的“矩形块”中，后来文献 9 扩展了这一概念，错误区 可以是非矩形的实心错误块，如十字形、l 形、t 形等凸形；与凸形错误区域不同，文 献f 5 ，1 0 1 1 1 提出了凹形错误区域；之后根据错误区域位置的不同，基于凸形错误区域和 凹形错误区域又有重叠错误区域与非重叠错误区域之分，文献 1 2 给出了相应的解决办 法。为了改善建立故障块时非错误节点失效的情况，文献 1 3 ，1 4 】提出了局部安全性信息 以及扩展局部安全性信息模型，w a n g t l 5 , 1 叼提出了最小连通部件故障模型，该模型与块 状模型相比，有更少的非故障节点失效。 文献【1 7 提出了一种新的模型：安全向量模型，安全向量用于记录与其他任意节点 之间是否存在最短距离通路；文献 1 8 】在文献 1 7 】的基础上修改了安全向量的定义，提 出了扩展安全向量模型；文献 1 9 】在文献 1 8 的基础上改用矩阵来表示各邻节点的每条 链路是否存在链路故障，提出了最优通路矩阵模型；文献 2 0 在文献 1 9 的基础上修改 2 f - 西大掌硕士学位论文基于t o r u s 网络的容错性研究 了最优通路矩阵的定义，提出了扩展最优通路矩阵模型；对最优通路矩阵进一步扩展， 文n 2 1 提出了最优通路集( o p t m gp a t hs e t ) 模型。由于文献 1 7 - 2 0 模型所能记录到的 最优通路信息有限且存储开销较大，王雷等在此基础上提出了安全通路向量 翻、极大安 全通路向量【2 3 】和极大安全通路矩阵【2 4 1 ；文献【2 5 提出了极大安全链路矩阵，它是安全 向量、扩展安全向量、最优通路矩阵、扩展最优通路矩阵以及极大安全通路矩阵的扩展。 为了避免信息迂回，文献 2 6 提出了安全矩阵。与安全向量不同，a i s a d i t 2 7 】等提出了非 安全向量( u n s a f e t yv e c t o r s ，u s v ) 的概念，非安全向量中第k 位的值表示与该节点距离为 k 的节点的非安全程度。2 0 0 2 年a i s a d i t 2 8 】等将u s v 模型应用到超立方体网络拓扑结构 上，提出了一个基于非安全向量的超立方体容错模型。jw u 提出了e x t e n d e ds a f e t y l e v e l 容错模型 2 9 , 3 0 。考虑到网络可能同时存在节点故障与链路故障，jw u 在文献 3 1 】 中提出了有向安全级别。为了提高容错能力，文献 3 2 ，3 3 运用最长导出路( t h el o n g e s t i n d u c e dp a t h ，l i p ) 容错模型，该模型能够容许大量的错误节点，在很多情况下，错误节 点数可多于2 小l 【弘j 。为了提高路由算法的寻径能力，文献 3 5 提出了节点通路向量模型。 一些研究者采用了概率论的研究方法【3 8 1 。文献 3 9 提出了两类局部连通性的概 念，给出了超立方体互连网络的连通性概率容错模型，对容错超立方体互连网络的连通 性概率进行了研究；文献 4 0 1 改进了两类局部连通性概念，提出了两类局部连通性条件 更弱的子连通性概念：k 维子连通性和任意子连通性概念；王高才f 4 h 3 】将划分子网思想 运用于m e s h 网络，提出了k - m e s h 子网连通的概念，给出了m e s h 网络基于子网结构的 概率容错模型。而专门针对t o m s 网络提出的容错模型很少，只有少量涉及矩形错误块 等凸形模型【4 4 , 4 5 】。 在容错路由方面，基于各种容错模型，提出了大量针对m e s h 或超立方体网络的容 错路由算法，包括单播容错路由算法、多播容错路由算法及广播容错路由算法。如文献 7 】基于转弯模型提出了自适应容错路由算法；文献 8 】基于矩形错误模型在错误链不能 重叠的前提下提出了一个只使用两条虚通道的容错路由算法；后来，他们又在文献【9 中扩展了该算法，错误块形状可以是十字形、l 形、t 形等，在没有错误链重叠的情况 下算法需要4 条虚通道；文献 1 7 提出了基于安全向量的容错路由算法，该算法通过安 全向量可以知道某节点与与之距离为一定数值的节点之间是否存在最优通路，但其所能 记录的最优通路信息十分有限：文献 18 在文献 1 7 的基础上，改进了距离为2 时安全 向量的定义，提出了基于扩展安全向量的容错路由算法，该算法同样只能记录有限的最 优通路信息；为了能够记录更多的最优通路信息，文献 1 9 】改用矩阵来表示各邻节点的 广西大学硕士掌位论文基于t o r u s 网络的容错性研究 每条链路是否存在链路故障，提出了基于最优通路矩阵的容错路由算法，但该算法存储 开销大于文献 1 7 ，1 8 ；文献【2 0 提出了基于扩展最优通路矩阵的容错路由算法，其存储 开销与文献【1 9 卜一样；为了记录更多的最优通路信息且减少存储开销，文献 2 2 2 4 提出 了改进的容错路由算法；文献 3 9 基于子立方体的局部连通性容错模型提出了一种超立 方体互连网络的单播容错路由算法；文献 4 0 在文献 3 9 的基础上提出了改进的容错路 由算法，该算法能够容纳更多的错误节点。而针对t o m s 网络，国内外只基于矩形错误 块等简单的模型提出了相应的容错路由算法，如文献【4 6 把文献【8 的算法扩展到t o m s 网络中，在不出现重叠错误区域的情况下算法需要6 个虚通道；文献【4 5 基于矩形错误 块和凹形错误块提出了自适应虫孔路由算法，此算法同样需要6 个虚通道；文献【4 7 】提 出了只需要4 个虚通道的基于矩形错误块和局部消息的自适应虫孔路由算法；考虑到网 络流量问题，文献【6 基于错误环提出了平衡环，从而提高了容错路由算法的性能。 从以上文献的分析结果可以看出，国内外对直接网络的容错性进行了大量的研究， 但大多针对m e s h 及超立方体网络，而针对t o m s 网络的容错性研究极少。然而通过对 比发现t o m s 网络具有比m e s h 及超立方体网络更加优越的性质，更易于实现容错。一 方面，t o m s 网络直径几乎是m e s h 网络的一半，链路数也大于m e s h 网络，连通性更好； 另一方面，t o m s 网络结构简单，各节点度数低且相同，无论从制造技术或是扩展性方 面来看都优于超立方体网络。因此本文选择对t o m s 网络进行研究。 此外，国内外对直接网络的容错性研究仍存在一定的局限性。基于一定形状限制的 容错模型会牺牲相当多的正确节点；基于向量或矩阵容错模型的容错路由算法没有能够 很好的处理时间、空间开销与沿最优路径路由之间的矛盾，最优路径是以大量的时间与 空间开销为代价的。综上所述可知，t o m s 网络的容错性还有待深入研究，这为本课题 的研究提供了契机。本文将以提高网络容错性为目的，运用概率模型来研究t o m s 网络 的容错性；以用更少时间与存储开销记录更多最优通路为目的研究t o m s 网络上容错路 由算法的实现。 1 3 论文的主要工作 本文首先对直接网络容错性的理论、实现网络容错的方法进行研究，通过分析基于 超立方体及m e s h 网络的容错性及在其上实现容错的方法，完善对t o m s 网络容错性的 分析及其上实现容错的方法。论文主要完成了以下几个方面的工作： 1 、分析传统与当前对网络容错性的定义，指出了传统对于网络容错性定义的缺陷， 4 广西大掌硕士学位论文 基于t o r u s 网络的容错性研究 实现了对t o m s 网络容错性的正确分析，证明t o m s 网络是一种具有很强容错能力的网 络拓扑结构。 2 、研究直接网络中基于局部故障信息的各种容错路由算法，为实现t o m s 网络的 容错路由提供理论支持。 3 、研究了基于局部故障信息容错路由算法在t o m s 网络中的实现，并改进了一个 针对超立方体网络提出的防止消息往返的容错路由算法。 1 4 论文的组织结构 本文在网络容错性基本理论的基础上，借鉴针对超立方体及m e s h 网络提出的容错 路由算法，逐步展开对t o m s 网络容错性的深入研究。本文各章节的安排如下： 第一章绪论 首先介绍了论文的选题背景；阐述了论文的选题意义，并对国内外针对直接网络拓 扑结构容错性的研究现状进行了介绍。 第二章预备知识 对t o m s 网络拓扑结构及其特点进行了概述；对网络容错性的衡量方法、网络容错 的实现方法进行概述；最后讨论了容错模型及容错路由算法。 第三章t o m s 网络的容错性分析 基于k - t o m s 子网和概率模型研究t o m s 网络的容错性，提出了一个简单的容错路 由算法。在节点出错相互独立的假设条件下对算法进行概率分析，给出算法成功构造路 径的概率公式。 第四章t o r u s 网络中基于标志位的容错路由算法 首先介绍了针对超立方体及m e s h 网络提出的基于局部故障信息的容错路由算法； 然后针对t o m s 网络给出标志位的定义及赋值算法，并讨论了标志位的性质；最后给出 基于标志位的容错路由算法，该容错路由算法本质上是基于局部故障信息的。 第五章超立方体网络中防止消息往返容错路由算法的改进 本章在第四章的基础上继续研究基于局部故障信息的容错路由算法。首先介绍了一 个针对超立方体网络提出的防止消息往返的容错路由算法，然后通过例子说明该算法的 不足，最后对算法进行了改进，并对其进行举例证明及实验验证。 第六章总结 对论文工作进行了总结，对后续研究进行了展望。 s 广西大掌硕士掌位论文 基于t o r u s 网络的客错性研究 第二章预备知识 弟一早 耿亩天h 。以 2 1t o r u s 网络拓扑结构及其表示 根据图论的知识，网络拓扑结构可以用一个图g ( n ，c ) 来表示，其中顶点代表节 点集合，边c 代表链路集合。 定义2 1 ( n 维t o m s 网络) 用瓦。局”。表示n 维t o m s 网络，由岛x 砖一，个 节点构成，其中k i 表示第i 维的节点数。用一个n 维向量( ，五，x 川) 来标识网络上的 每一个节点，其中o _ 砖一1 。节点( ? 五，一1 ) 和节点( y o ，m ，咒一。) 互为邻节点的条 件是：3 i 使一= ( ”+ 1 ) m o d k , ，而w i ，有0 = 乃。 为方便陈述令= j 2 1 = = b 一，= 尼，如不特别声明下文所说的n 维t o m s 网络都属 于这种情况。本文主要研究二维t o m s 网络( 其方法很容易扩展到高维网络中) ，下面再 给出二维t o m s 网络的精确定义： 定义2 2 ( 二维t o r u sn n ) 二维t o m s 网络乙。由n ；f t m 列共m 力个节点构成， 每个节点用二维坐标序列( x ，y ) 标定，其中x = o ，1 ，2 ，m - 1 ，y = o ，1 ，2 ，n - 1 。两个节 点( 五，m ) 与( x 2 ，y 2 ) 相邻当且仅当满足下列两个条件之一( 1 ) x i = x 2 且，、= ( y 2 + 1 ) m o d n ( 2 ) y 1 = y 2 且五= ( x 2 + _ 1 ) m o d m 。 图2 - 1 是一个二维t o m s 网络艮6 的例子，共：n 6 x 6 个节点。 6 广西大掌硕士掌位论文基于t o r u s 网络的容错性研究 6夺 、 ，i o丫年圆 n 弋，v i 上、 ，上、 du弋。广 一、一 ，上、 厂l 、 心v弋，卜一广 上、 n八 心u 一l 一 厂l 、 “ln 心u 一l 一 h 厂l 、 n 心弋。广u 图2 - 1 二维t o m s 网络瓦。6 f i g 2 12 - d t o r u s w i t l l6 6 n o d e s 从图2 一l 可以看出，t o m s 网络与m e s h 网络结构相似，t o m s 网络是m e s h 网络的 变形，它们的不同点在于对相邻节点的定义，t o m s 网络使用了求模运算，这就给t o m s 网络提供了环绕链路。对于二维t o m s 网络而言即为在每一行及每一列提供绕边链路， 使每一行每一列形成一个环，从而降低了网络的直径。下面将系统的研究t 0 m s 网络的 性质。 2 2t o m s 网络拓扑结构的性质 互连网络性能直接影响并行计算机性能，因此人们对互连网络的要求越来越高。具 体说来，一个好的互连网络应该具备以下六个要素： 1 、网络中各节点编址简单合理。这使得路由算法设计相对简单，容易实现。 2 、网络的度要小。小顶点度意味着少的物理连接，可以降低网络的搭建成本，进 而节省开支。 3 、网络的直径要小。直径小意味着小的消息传输延迟，这不仅能降低网络的建造 和维护费用，而且能确保网络的有效性。 4 、网络的对称性要好。对称网络的负载比较均衡，通信相对不拥挤，从而能够减 少出现在顶点或链路上的阻塞。 5 、网络连通度要大，应有较高的路由冗余度。这意味着网络具有较强的容错能力 及较高的可靠性。 6 、网络的扩展性要好。这使得较大规模的网络可以简单的由较小规模的网络改造而 成，而其网络拓扑结构仍然能够保持不变。 广西大掌硕士掌位论文基于t o r u s 网络的容错性研究 在这些要素中，网络的度和直径是最重要的两个要素。下面将综合以上六个要素讨 论t o r u s 网络的性质。 显然，从t o r u s 网络的定义及图2 1 可以得出，z 维t o m s 网络具有以下性质： 1 、网络结构简单，高维网络的构造是一个递归的过程，因此对节点的编址比较简单、 容易。 2 、网络具有正则性、对称性、可扩展性、路径多样性等特性；所有节点的度数相同 均为2 n ，网络的直径为n k 2 。 下面给出t o m s 网络与超立方体及m e s h 网络的性能指标，以便进行比较。 表2 1 直接网络的性能指标【4 8 】 t a b l e2 1p e r f o r m a n c eo f t h ei n t e r c o n n e c t i o nn e t w o r k s 与常用的超立方体网络拓扑结构相比，方面，从制造技术上来说，t o m s 网络中 节点度低且均相同，结构简单，而超立方体网络中节点的度是随维数( 或节点数) 的增 加而增加的。因此，t o m s 更易于v l s i 实现。另一方面，从扩展性方面来看，当网络需 要增加节点时，t o m s 网络在边缘上增加，因此只影响少量边缘上的节点。而超立方体 网络只有通过增加维数来实现，增加维数将会影响每一个节点，使每一个节点通信的端 口数增加。 与结构相似的m e s h 网络相比，由于增加了环绕链路，t o m s 网络直径几乎是m e s h 网络的一半，链路数也大于m e s h 网络，因此t o m s 网络拥有更多路径长度更小的通信 路径，连通性更好。此外t o r u s 网络是对称性的网络，而m e s h 并不是。因此在容错方 面，t o r u s 网络将是一种更好的选择。 8 广西大掌硕士学位论文基于t o r u s 网络的容错性研究 2 3 网络容错性介绍 2 3 1 网络容错性的衡量方法 任何系统的故障都可以划分为两类：硬件发生故障和软件发生错误。大部分的硬件 故障是由物理原因引起的，比如元件使用过程中产生的磨损和外界产生的干扰等等。软 件错误则是由设计的不完善而产生的。为了实现高性能而设计的大规模并行计算机也不 例外，而且随着处理器数目的不断增加，系统发生故障的概率也在不断的增加。因此网 络是否具有容错性已经成为设计或选择互连网络拓扑结构考虑的基本问题之。本文主 要针对硬件发生故障进行研究。 衡量网络容错性的方法已经有很多种f 4 9 巧1 1 。大体上可以分为两类：确定性方法和概 率方法。 ( 1 ) 确定性方法 大部分作者利用图论概念来研究网络容错性的确定性度量。用图来表示互连网络拓 扑结构已被计算机科学工作者和工程技术人员广泛接受和运用，而且，在实践上已被证 明，图论是设计和分析互连网络拓扑结构的一个非常有用的数学工具【5 2 1 。显然，互连网 络可以用图来表示。系统中的元件用图的顶点来表示，元件之间的物理连线用图的边来 表示，其中单向通信连线用有向边来表示，双向通信连线用无向边来表示，而元件之间 的连接方式由关联函数指定。这样的图称为互连网络拓扑结构，或者称网络拓扑。反之， 图也可以看成是某个互连网络的拓扑结构。从拓扑上讲，图和互连网络是一回事。因此， 在用图论研究互连网络的时候将混淆“图”和“互连网络，将网络、元件和连线说成 是图、顶点和边，反之亦然。以下介绍图论中用来研究容错性的确定性度量参数。 连通度：连通度是最主要的图论概念。如果用图g 表示互连网络的拓扑结构，那么 g 的连通度r ( g ) ( 或者边连通度力( g ) ) 指致使网络瘫痪所必需的最小元件个数( 或者 连线条数) 。换句话说，为了确保网络的正常运行，最多能容许r ( g ) 一1 个元件( 或者 力( g ) 一l 条连线) 同时出错。因此，如果图g 的连通度或边连通度越高，那么它所代表 的互连网络容错性越强。另一方面，如果图g 是功正则国连通的，那么图g 有最优连通 度和最小的边数。因此，缈正则缈连通图代表了最经济最可靠的网络拓扑结构。由此可 知，连通度和边连通度是网络容错性最重要的确定性度量参数。 9 广西大掌硕士掌位论文基于t o t l i s 网络的容错性研究 边容错直径：在图论中，链路故障的出现意味着在g 中去掉一些边，这必然会影响 图的直径。这就涉及到文献中提到的边减少问题。即给定直径为k 的图g 和正整数 k ( k 尼) ，能从g 中最多去掉多少条边后得到的图g 有直径不超过后? 文献 5 3 】已经证 明这个问题的解是n p 完备的。因此边的容错直径考虑与这个问题稍微不同的问题，即 设g 是f 边连通图，则从g 中任意地去掉t 一1 条边后得到的图日有确定的直径，那么日 的直径到底有多大? 与边容错直径相应的有点容错直径，点容错直径主要讨论节点出现 故障的情况。 宽直径：宽直径是度量网络性能的重要参数。网络的可靠性和容错性可以用图的连 通度来衡量，网络的通信延迟可用图的直径来衡量。图的这些参数在分析计算系统网络 的容错性和通信延迟中起了重要作用5 4 1 。但是在并行计算机系统中，信息是通过许多条 不存在相交内点的路径相互平行地传输，仅考虑连通度或仅考虑直径是不充分的，因为 虽然网络可能有大的连通度和小的直径，但是通过许多条不存在相交内点的路径进行消 息传递时，可能会有些路径其路径长度很长。因此有必要将连通度和直径结合起来考虑， 于是提出一个度量并行计算系统网络的容错性和通信延迟的新参数宽直径，它是连 通度和直径概念的结合和推广【5 5 1 。对于给定正整数0 和国连通图g ，确定最小数l 使得 g 中任何两顶点之间存在缈条内点不交且长度都不超过重的通路，其中最小数z 即为图 g 的宽直径。 ( 2 ) 概率方法 另一种衡量多计算机系统容错性的方法是概率方法。当故障发生时，在网络中每个 节点或者每条边出错概率己知的前提下，系统正常运行的概率是一个主要的概率度量参 数。设网络拓扑结构g 中每个节点( 或每条边) 出现故障的概率为p ，( 或p e ) 。那么， g 的点和边故障概率足( g ，a ) 和r ( g ，见) 可分别表示为：矗，( g ，a ) = l ，( 1 一a ) ”和 r ( g ，p e ) - - - - c i - - 见) 卜7 ，其中l ，( e ) 是g 中由f 个顶点( 边) 组成的点分离集( 边 截) 的数目，并且所有点( 边) 的出错是相互独立的。于是，l - r , ，( g ，p 。) 或者1 - r 。( g ，p 。) 是该网络可靠性的度量参数。计算r ，( g ，p ，) 或者疋( g ，见) 的主要困难在于对1 ，和c ，的计 算。当v 和占相当小时，可以通过枚举来计算l ，和c ，。否则，只有通过近似算法得到1 ，和 广西大掌硕士掌位论文 基于t o r u s 网络的容错性研究 c ，的近似值了。 可以看出，概率方法相对于确定性方法来说，更能反映实际情况。对于一个多处理 器互连网络，假定其连通度为茁( g ) ，为了最大限度的确保互连网络的连通性，该多处 理器互连网络系统最多可以允许“g ) 一1 个处理器单元发生故障。按照此方法，1 1 维t o m s 网络连通度为2 n ，因此最多可以允许2 n 1 个处理器发生故障。显然这个方法是有缺陷 的，因为当系统中出现2 n 个故障处理器，而这2 n 个故障处理器又恰好是其2 n 个邻节 点时，系统才会不连通，然而，出现这种情况的可能性非常小，实际上，k ( g ) 一1 相对 于互连网络的规模一般是很小的。为了更加准确的衡量网络的容错性，提出了边容错直 径与宽直径。边容错直径从直径方面来衡量网络的容错性，宽直径则将连通度和直径结 合起来考虑，但是它们的容错能力还是相当有限。事实上它们仍然假定网络中错误节点 的数目是o ( n ) 。因此确定性方法并不能准确的衡量网络的容错性。 多计算机系统中各个设备发生故障的概率总体上是不同的【矧，在用概率方法衡量网 络的容错性时通常假定处理器单元或通信链路发生故障的概率是统计独立的。文献 【5 7 ，5 8 中使用一些启发式算法来计算概率方法下系统的容错性，文献 5 9 1 指出概率方法 下计算系统的容错性是n p 难的。因此，设计出一种简单、有效的概率容错性分析方法 对于研究多计算机系统特别是规则互连的多计算机系统的容错性将很有价值。本文将在 划分子网的基础上对t o m s 网络连通性进行概率分析，从而证明t o m s 网络具有很强的 容错性。 2 3 2 网络容错的实现方法 文献 6 0 已简明扼要地定义一个计算机的容错性为“正确地执行指定算法的能力， 无论硬件故障和程序错误是否发生”。然而，不可能对被执行的算法进行简单的分类。 此外，许多大规模超级计算机系统在时间和存储空间许可的范围内都可以执行任何算 法。确定物理故障对算法的影响也是困难的，因为这些算法都是由程序或者框图给定的。 因此，文献 6 0 】关于容错性的定义无法应用到大规模超级计算机系统。 容错系统的性能应该包含两个方面：计算上的有效性和可靠性。一方面，由于故障 的存在必然产生对计算速度的影响，进而降低系统的处理性能。大规模超级计算机系统 中，计算的有效性是指当故障发生时系统以小的吞吐量继续运行。系统保持可接受的低 性能运行的能力被认为故障弱化。另一方面，为了确保系统的可靠性，当系统中的一个 广西大掌硕士掌位论文 基于t o r u s 网络的容错性研究 元件或者连线发生故障时，它的职责应该由该系统中其他的元件或者连线来完成。如果 这些元件或者连线的存在不影响系统的计算性能，而仅仅是为了修改系统的可靠性，那 么这些元件或者连线被称为是冗余的。 按照文献【6 1 的定义，如果超级计算机系统在故障发生时仍具有功能，那么称该系 统为容错的系统。有两个基本的功能性准则已引起人们的足够注意。根据第一个准则， 系统中的网络拓扑结构只要在逻辑上包含某个拓扑结构，那么该系统被认为是有功能， 这就涉及到结构嵌入问题。在图论中，所谓嵌入是一个拓扑结构到另一个拓扑结构的映 射，它保留某些被要求的性质。用数学表示即为：给定两个图g 和日，从图g 到图日的 嵌入是一个从g 到的同态。从g 到h 的同态是一个映射，顶点一一对应，并且图g 中 的任何边对应图日中一条路。利用这种功能性准则来达到系统容错性的方法是通过系统 的冗余元件和重组来实现的。这个准则在文献 6 2 中首先提出。第二个功能性准则，如 果网络中任何两个非故障元件之间存在非故障通信路线，就认为该系统具有功能。换句 话说，尽管故障出现，但网络中剩余的非故障元件仍保持连通。一般情况下，满足这一 功能性准则的系统是允许故障弱化的。 以上两种方法都能实现系统的容错，但是从它们的方法定义可知，第一种方法需要 冗余元件和重组，代价高且不易实现，因此在实现系统容错中一般都不使用此方法。而 第二种方法认为只要任何两个非故障元件之间存在非故障通信路径，那么该系统就具有 功能，是容错的。从实际中可知，任何两个元件之间存在不止一条通信路径，那么就可 以利用拓扑结构本身所提供路径的多样性，通过设计并使用容错路由算法来实现系统的 容错，而不需要增加多余的组件。由于以上特性，在考虑网络容错时大都采用此方法。 因此容错路由算法将是本文研究的主要内容。 2 4 容错路由 只要网络中任何两个非故障元件之间存在非故障通信路径，就认为该系统具有功 能。如果超级计算机系统在故障发生时仍具有功能，那么称该系统为容错的系统。因此 容错路由的选择是研究网络容错性的关键。 广西大学硕士掌位论文 基于t o r u s 网络的容错性研究 2 4 1 故障模型 故障模型的特点影响容错路由算法的能力和灵活性。下面列出故障模型收集的主要 信息【6 3 。 失效类型：当故障发生时首先注意到的是故障的类型。通常检测机制可以识别通信 通道失效和整个处理部件( p e ) 及其相关的路由器失效这两种类型的故障。前者称之为 链路故障，后者称之为节点故障。如果一条物理链路出现故障，那么这条特定物理链路 上的所有虚通道都标记为故障。如果节点出现故障，那么连接此节点的物理链路都标记 为故障。 失效状态：节点或链路出现的故障也许是静态的，也许是动态的。所谓静态故障指 只要网络通电那么故障就存在，而动态故障则指故障的发生是在系统运行时随机发生 的。通常认为这两种故障都是永久性的，即假定故障一直存在于系统中，直到它们被修 复。 故障邻接域：故障模型确定了一个节点可用的故障信息的范围。一种极端情况是节 点知道网络中每个节点的状态，另一种极端情况是节点只知道相邻节点的状态。对于第 一种极端情况而言，在当前故障状态下消息可以沿最短的可行路径传递。然而，及时更 新全局故障信息实际上是很困难的，不仅需要一定硬件支持，而且需要复杂的同步协议 来处理可能在更新期内发生故障这一复杂的情况。因此第一种极端情况将需要更多的存 储空间与时间消耗，而这些对系统性能会产生明显的影响。对于第二种极端情况而言， 节点只需要知道邻节点的状态，更新相邻节点的信息相对来说比较简单，计算速度也较 快。但是由于路由决策只使用本地故障信息，消息有可能会路由到带有故障部件的网络 中，从而导致较长的路由路径。 失效时