（计算机软件与理论专业论文）mesh网络容错性及容错路由算法研究.pdf

m e s h 网络容错性及容错路由算法研究 摘要 多计算机系统作为当今最流行的并行计算机，具有广泛的应用领域。 m e s h 网络拓扑是迄今为止并行计算机系统研究中最重要和最有吸引力的网 络拓扑结构之一，随着计算机互联网络规模的扩大，结点出错的可能随之 增加。因此，研究具有出错结点的m e s h 网络的容错性和容错路由不可避免。 容错性是多计算机系统非常重要的研究主题。目前，从概率角度分析 m e s h 网络的容错性，是假定网络每个结点具有独立均匀的出错概率。本文 基于结点随机出错概率研究多计算机网络m e s h 的容错性，采用子网划分方 法，将网络划分为相互独立且不相交的子网，假设每个结点具有随机出错 概率，通过分析子网的连通性，得到整个网络的连通概率。数值和模拟结 果表明，网络连通概率随时间的增大而减小，在给定的时间内，网络规模 越大，连通概率越低。与假定网络每个结点具有独立均匀的出错概率的结 论相比较，本文提出的方法和结论更能体现出网络结点出错的真实性，所 以也具有更好的理论和实际意义。 其次，本文基于最小连通分量模型( m c c ) 提出了启发式自适应容错 路由算法( 简称h a r 算法) ，该算法采用自适应路由，是在消息传递的过 程中动态建立的，因此，该算法能容许相当多的错误结点。实验结果表明， 对于较高的结点出错概率，不同规模的m e s h 网络中，h a r 算法得到的平均 路径长度与最小容错路由算法得出的平均路径长度非常接近。h a r 算法的 意义还在于：多计算机系统中某对特定源和目的结点间的路由被应用的次 数极少，因而在路径长度和时间开销间寻找折衷比穷尽搜索最短路径更有 实际意义。相对最小容错路由算法，h a r 算法为多计算机m e s h 网络容错路 由提供了一个非常重要的选择。 关键词：m e s h 网络随机出错概率容错性容错路由算法 l l s t u d yo nf a u i j rt o l e r a n c ea n df a u l r r - t o l e r a n t r o u t i n ga l g o r i t h m si nm e s hn e t w o r k s a b s t r a c t m u l t i c o m p u t e r sa r er e g a r d e da st h em o s tp o p u l a rp a r a l l e lc o m p u t e rs y s t e m s ， t h e yh a v eb e e na p p l i e di nm a n yf i e l d s m e s hn e t w o r kt o p o l o g yi s o n eo ft h e m o s ti m p o r t a n ta n da t t r a c t i v en e t w o r kt o p o l o g i e si np a r a l l e lc o m p u t e rs y s t e m s s of a r w i t ht h ei n c r e a s i n go fc o m p u t e rn e t w o r k i n gs i z e ，n o d ef a i l u r ep r o b a b i l i t y w i l li n c r e a s e ，s oi ti sn e c e s s a r yt or e s e a r c ho nf a u l tt o l e r a n c ea n 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 m si nm e s hn e t w o r k s f a u l tt o l e r a n c ei sav e r yi m p o r t a n t t o p i ci nm u l t i c o m p u t e rn e t w o r k s i nl i t e r a t u r e ，t h i st o p i cw a ss t u d i e db a s e do nw h i c he a c hn o d eh a si n d e p e n d e n ta n d u n i f o r mf a i l u r ep r o b a b i l i t y i nt h i sp a p e r , w es t u d yi tb a s e do nw h i c hn o d eh a s s t o c h a s t i cf a i l u r ep r o b a b i l i t y s u b n e tc o n c e p ti su s e dt od i v i d et h em e s hn e t w o r k i n t od i s j o i n ta n di n d e p e n d e n ts u b m e s h e s ，i nw h i c he a c hn o d eh a ss t o c h a s t i c f a i l u r ep r o b a b i l i t y , a n dt h e nt h ec o n n e c t i v i t yo fm e s hn e t w o r k sc a nb eo b t a i n e d t h en u m e r i c a la n ds i m u l a t i o nr e s u l t ss h o wt h a tt h ec o n n e c t i v i t yo fm e s hn e t w o r kw i l ld e c r e a s ew h e nt i m ei n c r e a s e s w i t h i ng i v e nt i m e ，t h ec o n n e c t i v i t yw i l l b el o w e ri ft h es i z eo fm e s hi n c r e a s e s c o m p a r e dw i t ht h ec o n c l u s i o nb a s e do n w h i c he a c hn o d eh a si n d e p e n d e n ta n du n i f o r mf a i l u r ep r o b a b i l i t y , t h em e t h o d a n dc o n c l u s i o ni nt h i sp a p e rc a nr e p r e s e n tm o r ea u t h e n t i c i t yo fn o d ef a i l u r e ，s oi t h a sm o r et h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e s e c o n d l y , w ep r o p o s e ah e u r i s t i c a d a p t i v 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 m ( h a r ) w h i c hi sb a s e do nm i n i m a l c o n n e c t e d c o m p o n e n t ( m c c ) i ti sa n a d a p t i v ea l g o r i t h m ，w h i c hm e a n s t h ep a t hi sa d a p t i v e l yc o n s t r u c t e di nt h ep r o c e s so fm e s s a g ed e l i v e r y a sar e s u l t ，t h ea l g o r i t h mc a nt o l e r a n tm o r ef a u l t y n o d e s f o rg i v e nn o d ef a i l u r ep r o b a b i l i t y , s i m u l a t i o nr e s u l t ss h o wt h a tt h ea v e r - 1 1 1 a g ep a t hl e n g t ho ft h eh e u r i s t i ca l g o r i t h mi sc l o s et ot h a to fm i n i m a lf a u l tt o l e r a n ta l g o r i t h mi nd i f f e r e n ts i z e sm e s h e s t h es i g n i f i c a n c eo ft h i sa l g o r i t h me x p o s e st h ef a c tt h a tar o u t ef o ras p e c i f i cs o u r c e d e s t i n a t i o nm a yr a r e l yb eu s e di n am u l t i p r o c e s s o rc o m p u t e rs y s t e m ，s oi ti sm o r es i g n i f i c a n tt os e e kf o ra t r a d e o f fb e t w e e np a t hl e n g t ha n dt i m ec o s t c o m p a r e dw i t ht h em i n i m a lr o u t i n g a l g o r i t h m s ，t h ep r o p o s e da l g o r i t h mp r o v i d e s a n i m p o r t a n to p t i o n f o r f a u l t t o l e r a n tr o u t i n g k e yw o r d s ：m e s hn e t w o r k s ；s t o c h a s t i cf a i l u r ep r o b a b i l i t y ；f a u l tt o l e r - a n c e ；f 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 m i v 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除己注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均己在论文中明确说明并致谢。 论文作者签名：王j 晶 学位论文使用授权说明 加。c 年6 月2 二同 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 囹即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：王器 导师签名 如刁年6 月沈日 g - 西大掌硕士学位论文m e s h 网络容错性及容错路由算法研究 第一章绪论弟一早三百t 匕 作为本文研究内容的一个基本背景，本章首先简单介绍了m e s h 网络容错研究的背 景和意义，简要概括了m e s h 网络容错模型、容错路由算法、概率分析的研究现状，阐 明了课题的研究目标及内容。最后给出了论文结构及各章的研究概要。 1 1m e s h 网络容错研究的背景与意义 现在许多领域的研究都直接依赖于计算能力的提高。例如，在物理、化学、材料科 学、生物学、天文学和地球物理等研究领域中，并行计算机都是必不可少的工具。并行 计算机系统在工程实践中也被广泛使用【o 。例如，在石油勘探、航空航天( 如机翼设计、 引擎设计等) 、制药、大规模集成电路设计等领域都依靠高性能并行计算机系统。对一 个商业企业来说，有时可能需要处理成千上万个同时发生的用户交易及数以百万计的订 单，这些工作一般都需要并行计算机系统来处理 0 2 1 。多计算机系统作为当今最流行的并 行计算机，无疑具有广泛的应用领域和发展空间，因而具有很强的研究意义。 由于m e s h 网络拓扑是递归的结构，因此具有结构简单、易实施、及在很多的并行计 算应用中能约简消息的延时等优点0 3 1 ，深受研究者和实践者的欢迎。作为大规模并行计 算机系统研究中最重要的网络模型之一，m e s h 网络不仅成为许多理论研究的基础模型， 而且也是国内外许多并行计算机系统所采用的拓扑。一些商用的并行计算机系统体系结 构女1 i l l i a c 【0 1 1 、i n t e lt o u c h s t o n ed e l t a o 1 、g o o d y e a rm p p 0 3 】、i n t e lp a r a g o n f 0 2 1 、s t a n f o r d d a s h t 0 3 1 、b l u eg e n es u p e r c o m p u t e r t 0 2 0 3 1 、m 1 ta l e w i f e 0 3 0 4 1 系列和国内的国家智能机中 心的曙光系列机器】等都采用了m e s h 网络拓扑结构作为处理机之间的互联网络结构。因 此，本文主要对m e s h 网络进行研究。随着计算机互联网络规模的扩大，某些结点出错的 可能也随之增加，研究m e s h 网络容错问题是这一领域中非常必要和重要课题。因此，本 课题无论从理论上还是从实践上都具有很强的研究意义。 1 2 胎始网络容错的研究现状 在具体介绍本文所做的m e s h 网络研究内容之前，以下对近年来有关m e s h 网络的国 内外研究现状从m e s h 网络容错模型、m e s h 网络容错路由算法和m e s h 网络容错模型和容 错路由算法的概率分析研究等几个方面进行综合评价和分析。 广西大掌硕士掌位论文m e s h 网络容错性及容错路由算法研究 1 2 1m e s h 网络容错模型研究现状 现已提出的m e s h 网络上的多种网络容错模型，在简单性、容错性、是否需要全局网 络状态信息等方面各有特点。有的容错模型只考虑边，即链路的容错性，有的容错模型 只考虑结点容错性，有的容错模型则同时考虑结点和边的容错性。实际上，在结点容错 模型中，边的错误可用连接该边的两个结点中的任何一个出错进行模拟0 5 】；在边容错模 型中，结点的错误可用与该结点相关的所有边出错进行模拟。下面给出现已提出的一些 m e s h 网络容错模型的简单介绍。 近年来的国内外研究学者在研究m e s h 网络容错路由算法时，提出了大量的容错模 型。拐弯模型( t u r nm o d e l ) 0 9 3 0 3 1 3 2 是最先提出的，该模型通过分析消息路由时拐弯 的方向和拐弯形成的环，找到最小且高度自适应路由。基于原点( o r g i n b a s e d ) 的路由 策略【1 0 3 4 3 5 ，3 6 1 中，网络通道分为：入子网( i ns u b n e t w o t k ) 和出子网( o u ts u b n e t w o t k ) 】，且两个子网是互不相交的。在该模型中，任意一个结点被定为原点，其它结点坐标 按位置依次给出。此模型能在每维有k 个结点的n - m e s h 网络上容许至少( k - 1 ) 加1 个错误 结点。 m e s h 网络中最为典型的容错模型是错误块模型( f a u l tb l o c km o d e l ) 1 2 1 3 1 7 】，是由 r v b o p p a n a 和s c h a l a s n i 提出的。此模型将所有的错误结点包含在一些不相交的“矩形 块”中。这一概念后又得以扩展，包含的错误区可以是非矩形的实心的错误块，如十字 形、l 形、丁形等凸多边形错误块【l4 1 。d j w a n g 对错误块模型加以改进，提出最小连通分 量模型1 1 2 1 8 4 6 1 ，使得错误块包含更少的非错误结点。还有如a a c h i e n 币i j h k i m 提出的 平面路由策略1 5 , 3 7 】；还有负优先路由策略；j w u 提出基于安全向量的路由策略1 7 3 8 - 4 5 。 根据结点或边的错误行为的不同，还可以区分最常研究的两种错误类型：一种称为 f a i l s t o p 类型0 6 1 0 8 嗍( 也称为c r a s h 类型) ，对于此类型，错误结点或错误边不能传输任 何信息；另一种称为b y z a i l t i n e 类型f 0 7 】，错误结点或边可能对传输经过该结点或边的信息 进行任意的改变。容错模型在考虑对错误进行分类时，另一个很重要的特征是错误持续 时间的长短，根据此特征可将错误分为静态( 或永久性) 错误类型和动态( 或瞬态) 错 误类型两类【o 引。 按照传统的容错性定义，z 一维m e s h 的容错性是玎1 ，所以，m e s h 网络的容错性是非 常低的。如在二维m e s h 网络中，只要2 个结点出错即可破坏m e s h 的连通性。在三维m e s h 网络中，3 个结点也就足够了。尽管人们现已提出了多种m e s h 网络容错模型，但是它们 2 广西大学硕士学位论文m e s h 网络容错性及容错路由算法研究 的容错能力都相当有限。因此，人们在研究m e s h 网络容错性时，大多采用一定的模式和 限制，但限制错误模块的形状要牺牲相当多的正确结点。 文献【2 9 】提出“k - m e s h 子网”概念，在假定网络每个结点具有独立均匀的出错概率 的情况下，证明当结点的出错概率固定时，网络规模的增大将不可避免地导致网络连通 概率下降，并运用严格的数学方法推导得出网络结点的出错概率与网络连通概率之间的 关系，证明以m e s h 为网络拓扑的并行计算机网络具有相当高的可靠性。 本文第三章提出一种新的不同的方法来度量m e s h 网络的容错性，应用一种更为真实 的模型即假定每个结点具有随机的出错概率，然后研究m e s h 网络的容错性。本文研究表 明m e s h 网络可容许相当多的错误结点而仍能确保正确结点的具有较高的连通概率。 1 2 2m e s h 网络容错路由算法研究现状 在并行计算机系统中，结点间的通信常常是影响系统性能的主要因素1 9 2 0 2 1 1 。因此， 研究有效的通信策略是并行计算机系统中最为重要的主题之一。一些研究人员对m e s h 网络上的各种路由算法进行了大量的研究，主要集中于对单结点的通信操作2 2 1 ，基于单 结点操作主要有三种算法。 o n e t o m a n y l j p 多播( m u l t i c a s t ) 该问题是研究一个结点散布信息到其它结点。 o n e t o o n ee ! p 单播( u n i c a s t ) ：该问题主要研究两个结点间的通信方式2 3 】：即单结 点间路由问题。可看作多播的一种特殊形式，如果消息的目的结点集合减少到一个结点， 则该问题就成为单播路由问题2 5 1 。这些路由必须满足交换方式( 存储转发、电路交换、 虚切通和虫孔路由) 和路由功能( e c u b e 、x y - r o u t i n g 、p r e f i xr o u t i n g 、i n t e r v a lr o u t i n g ) 的一些限制 2 4 】。 o n e t o a l l , r 广播( b r o a d c a s t ) 这是一个或全部的结点并行地执行一种通信模式， 该问题用来解决全局信息散布问题。例如g d 5 s 咖加g f 2 钟和s c a t t e r i n g m 2 8 1 。广播也是多播的 特殊形式，如果消息的目的结点集合由所有其它结点组成，则该问题成为一个广播路由 问题。 随着网络规模的增大，网络中无论是结点或边出错的可能性也越来越大。研究网络 的容错性，并提出具有一定容错能力的容错路由算法很有必要。很多容错路由算法的研 究中，都是基于上述容错模型，通过对无容错能力的算法设计和改进，获得容错的能力。 所以，下面在介绍的一些出现结点或边错误的情况下的一些容错路由算法时，我们也给 出一些无容错能力的路由算法的介绍。 广西大学硕士掌位论文m e s h 网络容错性及容错路由算法研究 b o p p a n a 矛d c h a l a s a n i 给出了一个只使用两条虚通道的容错路由算法【2 8 3 1 】。该算法要 求错误块是矩形，且错误链( 环绕错误区的非错误边) 不能重叠。该研究结果后来得以 扩展，包含的错误区可以是实心的错误块，如十字形、l 形、研；等凸多边形错误块，但 该算法在没有错误链重叠的情况下需要使用4 条虚通道。c c h i u 等使错误链重叠时，只 需要3 条虚通道1 2 引。 x l i n 等提出一种基于虫孔( w o r m h o l e ) m e s h 网络上的消息流模型，并应用于研究 双向】，通道的m e s h 网络容错路由算法【l9 1 。该模型不同于拐弯模型，很容易产生路由算 法。g l a s s 和m 提出了拐弯模型( t u r nm o d e l ) 的自适应容错路由算法 3 0 , 3 1 1 。d u a t o 提出的 自适应算法在，2 维m e s h 网络上能容许聆1 个错误，而在每一物理通道上要求有四条虚 通道【1 6 。文献【2 1 】提出3 维m e s h 网络上的容错平面自适应路由算法【2 。他们的算法在 不使用重叠的f - r i n g 的情况下，能容许矩形错误块。文献【2 2 】提出一个低代价的完全自 适应路由算法。该算法需要的虚通道数少，具有代价低、自适应性强的特点。r l h a d a s 等提出了基于原点( o r i g i g n b a s e d ) 的m e s h 网络容错路由算法陋3 6 1 。文献【5 4 提出了基于 错误块模型的二维m e s h 网络上的无死锁容错路由算法，该算法将网络分为两个虚拟网 络，消息根据源与目的结点的相对位置判断进入哪一个虚拟网络，消息在没有遇上故障 时经由最短路径路由，算法的容错技术是基于故障环和故障链的概念。现有单播容错路 由算法大量使用了虚通道( v i r t u a lc h a n n e l ) 或牺牲相当多的正确结点。 文献 4 9 1 基于k - m e s h 子网的概念提出了两个简单的基于局部信息和分布式的m e s h 网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假 设条件下，推导出路由算法成功返回由正确结点组成的路径的概率。该文运用严格的数 学推理，证明了m e s h 网络结点出错概率只要控制在1 8 7 以内，则对于多达几十万个 结点的m e s h 网络，提出的路由算法具有9 9 的概率确保找到正确结点组成的路径。路 由算法的时间复杂性是线性的，模拟结果表明路由算法所构造的路由路径长度非常接近 于两结点之间的最优路径长度。 文献 5 5 1 提出了一种三维m e s h 网中的无死锁路由算法，在应用于m e s h 网的平面自 适应路由算法中，每条物理通道只需三条虚拟通道就可以有效地在三维以及更高维的 m e s h 网中避免死锁的产生，然而采用该算法，网络拓扑一维和三维分别有两条和一条 虚拟通道始终处于空闲状态，该文所提出的算法针对三维m e s h 网，每条物理通道只需 两条虚拟通道就可以有效地避免死锁。 文献 5 6 】在m e s h t o r u s 结构上提出了一种基于死锁恢复策略的容错路由算法，基于 4 广西大学硕士掌位论文m e s h 网络容错性及容错路由算法研究 各非故障结点周围链路的状态，能容错任意形状的故障模型且所需虚拟通道数少，通过 在凹形区域表面节点中设置该凹形区域内结点位置信息表，该算法能避免消息进入与其 目的节点无关的凹形区域以使绕道路径最短。 人们在研究m e s h 网络容错路由算法时一直受到以下困扰：如前所述，因为m e s h 网 络结点的度很低，以维m e s h 的容错性是n 1 ，在最坏情况下，对于二维m e s h 网络，只要 两个结点出错即可破坏m e s h 网络的连通性，因此研究最坏情况下m e s h 网络容错路由算 法没有实际意义。而由于m e s h 网络中连通形式相当多，在一般结点出错情况下研究m e s h 网络连通性相当困难。因此，人们在研究m e s h 网络路由算法时，大多采用以下模式或限 制：( 1 ) 限制错误块的形状；( 2 ) 采用大量的虚通道；( 3 ) 采用其它的模型及限制。但 是，这些方法总是存在一些不足之处。例如，一方面，限制错误块的形状可能要牺牲相 当多的正确结点；使用虚通道会增加结点的缓冲空间，使逻辑控制更复杂，这些虚通道 也使得结点变得更容易出错；另一方面，增加和删除结点或要求修改链路或网络的拓扑 结构，代价可能会非常昂贵，且操作起来也相当困难。另外，这些扩展是通过增加网络 中的虚通道，因为这些虚通道常常是用于网络容错的目的，因此，当网络中没有错误时， 虚通道就没有得到有效的利用。 1 2 3m e s h 网络概率分析容错性的研究现状 在这一部分，对容错性的概率分析研究进行介绍，根据错误分布情况，有两类最常 使用的错误分布模型，即界限模型( b o u n d e dm o d e l ) 1 6 5 0 1 和概率模型( p r o b a b i l i s t i c m o d e l ) 【2 9 1 。在界限模型中，要求给错误结点或边设定上界值，并且假定以最坏情况进 行考虑。在概率模型中，错误的发生是随机的并且是相互独立的。 n a j j a r $ 1 g a u d i o t 基于均匀独立的结点错误概率研究了规则网的容错性【5 1 1 。假定q 是 一个包含错误结点的有j 个结点的玎规则的网络。一个h 一簇( 办一c l u s t e r ) 是一个q 中所有错 误结点被移去之后有h 个结点的连通子图。他们推测网络由1 一簇引起的不连通的概率比 网络由h 簇引起的( 对任何h 1 ) 不连通的概率要大【5 1 5 2 1 。基于这个推测，他们研究了 1 簇引起的不连通的概率，使用1 一簇引起的不连通的概率去近似表示网络不连通的概率。 他们假设每一个h 一簇的错误邻结点的数目不超过o ) 并且可能的h 簇的数量不超过 o ( m 。然而，他们的方法不适用于m e s h 网络和大多数具有层次结构的网络。 文献【3 7 】首次将概率模型研究应用于超立方网络，提出了局部连通性这一网络容错 的全新的概念。给出了两种类型的局部连通性：局部k 维子立方体连通性和局部子立方 5 广西大掌硕士学位论文 m e s h 网络容错性及容错路由算法研究 体连通性，并给出了超立方体网络中二个满足局部连通性条件的单播容错路由算法；文 献 2 7 】基于子立方体提出了具有大量错误结点的超立方体网络中基于局部信息的并行容 错路由算法。文献 2 9 】在假定网络每个结点具有独立均匀的出错概率的情况下，基于提 出的“k - m e s h 子网”概念，证明当结点的出错概率固定时，网络规模的增大将不可避免 地导致网络连通概率下降，并运用严格的数学方法推导得出网络结点的出错概率与网络 连通概率之间的关系，证明以m e s h 为网络拓扑的并行计算机网络具有相当高的可靠性。 1 3 课题研究目标以及内容 1 3 1 研究目标 本论文的研究目的：基于并行计算机系统互联网络中结点具有随机出错概率的情况 下，研究多计算机m e s h 网络的容错性，讨论多计算机m e s h 网络连通概率随时i 日j 的变 化情况，及受不同网络规模的影响。基于目自 广泛应用的最小连通分量容错模型，就多 计算机系统中某对特定结点间的路由被应用的次数极少这一实际情况，提出时间开销更 小的m e s h 网络肌尺算法。 总体目标是寻找出一种更真实的度量多计算机胁妇网络容错性的概率模型，假设 每个结点具有随机出错概率，运用严格的数学推理及运算分析多计算机m e s h 网络的容 错性；基于最小连通分量模型的多计算机m e s h 网络中，就不存在曼哈顿路径的情况， 给出启发式自适应容错路由算法，切实地利用多计算机系统中结点间的消息传递特点来 提高系统的性能，包括降低系统的开销、增大消息传递效率等。 1 3 2 研究内容 论文总结多计算机m e s h 网络容错模型、容错路由算法已取得的研究进展，分析多 计算机m e s h 网络的特点以及实际应用中性能评价的参数，重点研究结点随机出错概率 下整个网络的容错性。主要针对最小连通分量模型下结点间消息传递的不同机制，重点 研究不存在曼哈顿路径情况下结点间的自适应路由解决方案，并验证该路由方案的性能 表现。研究内容包括以下几个方面： ( 1 ) 研究结点随机出错概率下m e s h 网络的容错性 针对目前从概率角度研究m e s h 网络容错性的容错模型，限定结点具有固定的出错 概率这一局限性，考虑实际的应用场景，对概率模型加以改进，假定每个结点具有随机 6 广西大学硕士学位论文m e s h 网络容错性及容错路由算法研究 出错概率并服从指数分布，运用k - m e s h 子网划分方法，研究不同规模的m e s h 网络连通 概率随时间的变化情况。侧重解决实际应用中遇到的问题，考虑系统本身的运行过程中 结点出错情况的变化以及不确定因素带来的影响等。 ( 2 ) 基于m c c 的m e s h 网络启发式容错路由算法h a r 针对最小连通分量模型这一目前m e s h 容错路由研究中应用广泛的的容错模型，重 点解决目前的算法穷尽搜索最小路由导致时间开销过大的问题，考虑到多计算机系统中 某对特定结点间的路由被应用的次数极少这一实际情况，侧重关注降低系统总体开销， 提高系统性能的这一现实需求，提出更具实际意义、效率高、开销小的启发式容错路由 算法。 就结点间是否存在曼哈顿路由的两种情况，提出完全的容错路由解决方案。基于增 强算法的容错性这一基本出发点，提出的h a r 算法采用自适应路由，是在消息传递的 过程中动态建立的，可以允许消息通过任何无错中间结点实现预定传递，具有更强的容 错性。 1 4 论文结构 本文对结点随机出错概率下多计算机m e s h 网络容错性进行分析，研究不同规模的 m e s h 网络连通概率随时间的变化情况；根据基于最小连通分量模型的多计算机m e s h 网 络的实际应用特点，提出了启发式自适应容错路由算法。论文共分为五章，各章的内容 安排如下： 第一章：绪论，简单介绍了m e s h 网络容错研究的背景和意义，简要概括了m e s h 网 络容错模型、容错路由算法、概率分析的研究现状，阐明了课题的研究目标及内容。 本章可以作为本文研究内容的一个基本背景。 第二章：多计算机m e s h 网络。介绍并行计算机系统，m e s h 网络拓扑结构以及讹砌 网络的定义。本章是本文研究的工作基础。 第三章：结点随机出错概率下的m e s h 网络容错性分析。主要分析结点出错概率服 从指数分布情况下的网络连通性，给出了实验结果，并与理论结果做了比较，证明了提 出方法的可行性。 第四章：基于m c c 的m e s h 网络h a r 算法。对最小连通分量这一容错模型做了简 单介绍，给出了曼哈顿路径存在的充要条件，并基于曼哈顿路由存在与否的两种情况， 7 广西大掌硕士学位论文m e s h 网络容错性及容错路由算法研究 提出了启发式容错路由( 泓尺) 算法。最后得出实验结果，证明该算法得出的平均路径长 度与最小容错路由算法得出的平均路径长度非常接近，与曼哈顿路径长度偏离也较小。 第五章：总结与展望，总结本文所做的工作，对m e s h 网络的容错性及容错路由算 法的研究提出一些探讨性的意见。 8 广西大学硕士掌位论文m e s h 网络容错性及容错路由算法研究 第二章多计算机m e s h 网络 多计算机系统是一种重要的并行计算机系统类型，本章先对并行计算机系统做一简 单介绍，包括并行计算机的分类，并行计算机系统互联网络以及高性能计算机研究概况。 接着，对m e s h 网络拓扑结构进行阐述，着重分析m e s h 网络的优点，如它的结构简单、 规则及良好的扩展性，易于v l s i 实现。 2 1 并行计算机系统 2 1 1 并行计算机分类 并行计算是相对于串行计算来说的，是指使用多个处理机同时执行多个任务和指 令，或同时对多个数据项进行处理。并行计算可分为时间上的并行和空间上的并行。时 间上的并行就是指流水线技术，即将每条指令分解为多步，并让各步操作重叠，从而实 现几条指令并行处理的技术。程序中的指令仍是一条条顺序执行，但可以预先取若干条 指令，并在当前指令尚未执行完时，提前启动后续指令的另一些操作步骤。这样显然可 加速一段程序的运行过程。而空间上的并行则是指用多个处理器并发的执行计算。并行 计算科学中主要研究的是空间上的并行问题。从程序和算法设计人员的角度来看，并行 计算又可分为数据并行和任务并行阱】。一般来说，因为数据并行主要是将一个大任务化 解成相同的各个子任务，比任务并行要容易处理。 完成并行计算的计算机系统称为并行计算机系统，它将多个处理机( 可以从几个到 几万个不等) 通过网络互连，并且以一定的方式有序地组织起来。根据指令流和数据流 的不同组合，并行计算机系统可分为：单指令流多数据流( 姗) 并行机和多指令流 多数据流( m i m d ) 并行机 0 8 5 3 。单指令流多数据流( s i m d ) 并行机用同一控制器同步 地控制所有处理器阵列执行相同操作来开发空间上的并行性【0 8 1 ；多指令流多数据流 ( m ，7 i 彳d ) ，则用不同的控制器异步地控制相应的处理单元执行各自的操作。对于后者， 其中，如果各处理单元通过公用存储器中的共享变量实现相互通信，则称为多处理机 ( m u h i p r o c e s s o r s ) 0 8 , 1 4 ；如果处理单元之间使用消息传递的方式来实现相互通信，则 就称为多计算机( m u h i c o m p u t e r s ) ，它是当今最流行的的并行计算机【i4 1 。对于我们常用 的串行机也叫做单指令流单数据流( 册d ) 。m i m d 类的机器又可分为以下常见的五类 4 j ：并行向量处理机( p v p ) 、对称多处理机( 跏伊) 、大规模并行处理机( m p p ) 、工 9 广西大学硕士学位论文m e s h 网络容错性及容错路由算法研究 作站机群( c o w ) 、分布式共享存储处理机( d s m ) 。 自上世纪7 0 年代世界首台巨型机i l l i a ci v 问世至今，高性能计算机发展的历史已经 接近4 0 年了。期间，出现了各种不同类型的并行机。大型并行机系统一般可以分为以下 六类【1 4 】：单指令多数据流机s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ) 、对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 、并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) 、工作站 集群c o w ( c l u s t e ro f w o r k s t a t i o n ) 、大规模并行处理机脚p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 和分布共享存储d s m ( d s t r i b u t e ds h a r e dm e m o r y ) 多处理机。s m p 、m p 尸、c d 晰口d 跏 现在流行的四种主要的并行计算机系统。通过对并行计算机的研究现状分析，无论是在 并行计算机系统的体系结构方面还是在并行算法方面，发展水平都还相对比较低。因此， 加强并行计算机系统体系结构和并行算法的研究有助于加速该领域的发展。 2 1 2 并行计算机系统互联网络 并行计算机体系结构是对通常意义上的计算机体系结构的扩展，即扩展了通信体系 结构。根据处理机间传递数据所使用的方法，并行计算机可分为两种不同的通信模型【3 5 】： 一种是通过共享地址空间进行通信，通过加载和存储操作传递数据；另种是通过发送 和接收消息进行处理机之间的数据传递。通信体系结构是并行计算机体系结构的核心， 通信体系结构的核心则是并行计算机系统互联网络。目前，主要的并行计算机系统是建 立在互联网络基础上的。互联网络用来实现计算机系统内部多个处理机或多个功能部件 之间( 如处理机与存储器之间) 的相互连接。通常互联网络由链路( 如导线、光纤等能 够携带信息的物理介质) 和开关组成。互联网络可以分为静态网络和动态网络两种睁”。 静态网络的连接通路是固定的，一般不能实现任意结点到结点之间的互联。静态网 络通常使用以下参数来描述5 3 】：网络规模、结点度、距离、网络直径、等分宽度、对称 性。典型的一维静态网络是线性阵列结构，二维的静态网络有环、星型、树、网格等结 构，三维的有立方体等结构，三维以上的有超立方体等结构。以下是常见的静态并行计 算机系统互联网络常见的网络拓扑结构，如一维线性连接，网孔连接，超立方体连接， 全连接，树连接和立方环连接等。 动态连接由开关及通信链路构成，可按应用程序的要求动态地改变连接通路。动态 网络主要有总线连接( b u s ) ，交叉开关( ，多级互联网络( m u l t i s t a g ei n t e r c o n n e c t i o n n e t w o r k ，m i n ) 。 并行计算机系统互联网络的研究作为当今的一个研究热点，国内外现已对各种主要 1 0 广西大学硕士学位论文m e s h 网络容错性及容错路由算法研究 的并行计算机互联网络拓扑结构女h r i n g ( 环) ，m e s h ( i 网t l ) ，t r e e ( 树) ，t o r u s ( 环绕) ， s t a r ( 星型) 署 i h y p e r c u b e ( 超立方体) 等进行了大量研究，并且对其中的一些拓扑结构 已研制出了相应的商用和研究用的并行计算机系统0 3 1 。 并行计算机系统互联网络的拓扑结构、容错路由算法、基本通信操作、交换方式和 流控机制等是当今并行计算机系统互联网络的主要研究方向。 2 1 3 高性能计算机研究概况 高性能计算机领域的研究和发展水平是衡量一个国家的科技发展水平和综合国力 的重要标志。在医学、军事、能源勘探、工程设计和自动化以及基础理论等领域研究中 都对计算提出极高的具有挑战性的要求【o 。美国、日本、欧洲各国政府都高度重视高性 能计算机领域的研究。1 9 9 3 年，美国提出“高性能计算和通信计划( h p c cp r o g r a m ) 9 9 9 即美国总统科学战略项目；“加速战略计算创新计划( a s c ip r o g r a m ) ”【0 3 】和“千万亿次 计算机计划( p e t a f l o p sp r o j e c t ) ”是美国于1 9 9 6 年提出的更高性能并行计算机系统的研 究计划。日本提出的“真实世界计算计划( r w cp r o g r a m ) ”，欧洲提出的“力亿次计算 机计划( t e r a f l o p sp r o g r a m ) 9 9 9 两者的主要目标都是研制万亿次量级的高性能并行计算 机系统。我国的高性能计算机的发展起步也比较早。国内主要有国家智能机中心的曙光 系列( d a w n i n g l ，d a w n i n g 1 0 0 0 ，d a w n i n g 一1 0 0 0 a ，d a w n i n g 一2 0 0 0 一i 和d a w n i n g 3 0 0 0 ) 计算机和国防科大银河系列( y h l ，y h 2 ，y h 一3 和y h 4 ) 计算机o 等。2 0 0 1 年l o 月1 3 同，我国高性能计算机芯片“龙芯”问世。2 0 0 7 年1 2 月2 7 日，高性能计算机( h p c ) “k d 一5 0 一i ”在中国科技大学问世，彻底结束了中国h p c 的“空芯时代”。这是首次采用 我国完全自主的高性能芯片研发成的万亿次机，这台被命名为“k d 一5 0 一i ”的机器，采 用的芯片就是代表了当前国内高性能通用处理器设计最高水平的6 4 位“龙芯2 f ”芯片。 2 2 m e s h 网络拓扑结构 2 2 1 网络拓扑结构的概念 网络拓扑是网络形状，或者是它在物理上的连通性。构成网络的拓扑结构有很多种。 网络拓扑结构是指用传输媒体互连各种设备的物理布局，就是用什么方式把网络中 的计算机等设备连接起来。它的结构主要有星型结构、环型结构、总线结构、分布式结 构、树型结构、网状结构、蜂窝状结构等。 广西大掌硕士掌位论文m e s h 网络容错性及容错路由算法研究 计算机网络的拓扑结构是引用拓扑学中研究与大小，形状无关的点，线关系的方法。 把网络中的计算机和通信设备抽象为