（计算机软件与理论专业论文）规则互连多计算机系统的容错性及诊断算法.pdf

至：! 达兰堕堂生丝塞 主苎塑墨 摘要 多计算机系统中的互连网络为处理器之间相互通信提供了一种有效的机制， 是决定系统性能的重要因素之一。本文使用概率方法对基于超立方体及其四种变 体结构的多计算机系统的容错性和故障诊断算法进行了研究。 多计算机系统的容错性可以用互连网络中出现故障时，隔离这些故障设备后 网络保持连通的概率来刻画。论文中分析了两种在多计算机系统中设备发生故障 的情况：一是只考虑处理器单元以一定的概率发生故障；另一种情况是让多计算 机系统中的处理器和通信链路都以一定的概率发生故障。通过仿真试验，得到如 下结论：基于超立方体及其变体结构的多计算机系统均具有较好的容错性，其中， 基于交叉立方体结构的多计算机系统具有最好的容错性。 在多计算机系统中，系统级故障诊断是确定系统中故障处理器的一个有效方 法。在基于测试的诊断方式中，相邻处理器之间通过相互测试而形成症候集，进 而根据症候集来进行故障定位。本文提出了一种新的概率诊断算法。该算法利用 h o p f i d d 神经网络迭代有限步收敛的性质，并充分考虑了症候的特点。算法分为 两部分：预处理阶段和神经网络算法迭代阶段。通过理论分析和计算机仿真，将 本算法与其它两种经典的概率诊断算法( 多数表决算法和d a r s 诊断算法) 进行 了对比，得到如下结论：神经网络诊断算法具有相对较高的正确诊断概率，并且 该算法的性能不明显依赖于系统的规模和处理器的故障率。因此，神经网络算法 具有定的实用价值。 关键词；多计算机系统，互连网络，容错性，连通性，系统级故障诊断，概率诊 断算法，h o p f i e l d 神经网络 兰塑翌苎塑生壁燮 茎壅塑型 a b s t r a c t 1 1 1 ei n t e r c o n n e c f i o n n e t w o r ku s e di nam u l t i c o m p u t e r s s y s t e mp r o v i d e s a l l e f f e c t i v em e c h a n i s mf o rt h cd a t ae x c h a n g eb e t w e e nt h e p r o c e s s o r sa n dh e n c ei so n eo f t h ed o m i n a t i n gf a c t o r so f p e r f o r m a n c eo ft h es y s t e m i nt h i sp a p e r ，t h ef a u l tt o l e r a n c e a n ds y s t e m l e v e ld i a g n o s i s a l g o r i t h m so ff i v er e g u l a r l yi n t e r c o n n e c t e dn e t w o r k sa r e e x a m i n e d t h ef a u l tt o l e r a n c eo fa l li n t e r c o r m e c t i o nn e t w o r kc a nb em e a s u r e db vt h e p r o b a b i l i t yo f c o n n e c t e d n e s so ft h es u r v i v i n gn e t w o r ki nt h ep r e s e n c eo ff a i l u r e s ，w e e x a m i n et h ef i v en e t w o r k su n d e rt w od i f f e r e n tf a i l u r er o o d e l s i nt h ef i r s tm o d e l ，i ti s a s s u m e dt h a ta l lt h ec o m m u n i c a t i o nl i n k sw o r k p r o p e r l ya n ds o m ep r o c e s s o r sm a y f a i l i nt h es e c o n dm o d e l ，h o w e v e r ，b o t ht h ep r o c e s s o r sa n dt h ec o m m u n i c a t i o nl i n k sm a y b r e a ko u t e x p e r i m e n t a lr e s u l t ss h o wt h a ta l lt h e s en e t w o r k sd i s p l a ye x c e l l e n tf a i l u r e t o l e r a n c e i np a r t i c u l a r ，t h ec r o s s e dc u b ee n j o y st h eh i 曲e s tp r o b a b i l i t yo f c o n n e c t i v i t y a m o n g t h e m s y s t e m l e v e l f a u l td i a g n o s i si s 柚e f f e c t i v e a p p r o a c h t o l o c a t i n g t h ef a u l t p r o c e s s o r s i nam u l t i c o m p u t e r ss y s t e m w i t h i nt h er e a l mo ft e s t - b a s e d d i a g n o s i s ， p r o c e s s o r s i nas y s t e mc o n d u c tt e s t so i l n e i g h b o r i n gp r o c e s s o r s ，a n dd i a g n o s i s i s p e r f o r m e db a s e do nt h et e s to u t c o m e s i nt h i sp a p e r , an e w f a u l td i a g n o s i sa l g o r i t h mi s p r o p o s e du n d e r a p r o b a b i l i s t i cm o d e l ，w h i c hc o n s i s t so f t w os t a g e s ：p r e p r o c e s s i n gs t a g e a n dn e u r a ln e t w o r ki t e r a t i o ns t a g e t h ec o n v e r g e n c eo fh o p f i e l dn e u r a ln e t w o r k e r l g u l - e st h ec o n v e r g e n c eo ft h i sn e w a l g o r i t h m ，t h ep e r f o r m a n c eo f t h i sn e wa l g o r i t h m i s c o m p a r e d 、析t h t w oc u s t o m p r o b a b i l i s t i cd i a g n o s i sa l g o r i t h m sb yc o m p u t e r s i m u l a t i o n so nt w ot y p i c a lt y p e so fi n t e r c o n n e c t i o nn e t w o r k s ( h y p e r c u b ea n dc r o s s e d c u b e ) e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sn e wa l g o r i t h mc a na c h i e v eas i g n i f i c a n t l y h i 曲e rp r o b a b i l i t yo f c o r r e c td i a g n o s i s i i la d d i t i o n 。t h ee f f e c t i v e n e s so ft h i sn e wf a u l t d i a g n o s i sa l g o r i t h md o e sn o ts i g n i f i c a n t l yd e p e n do nt h es i z e o ft h es y s t e mo rt h e p r o b a b i l i t y o fp r o c e s s o rf a i l u r e t h e r e f o r e ，t h i s d i a g n o s i sa l g o r i t h m i s p r a c t i c a l l y a p p l i c a b l e k e y w o r d s ：m u l t i c o m p u t e rs y s t e m ，l n t e r c o r m e c t i o n n e t w o r k ，f a u l tt o l e r a n c e ， c o n n e c t i v i t y ，s y s t e m l e v e l f a u l t d i a g n o s i s ，p r o b a b i l i s t i cd i a g n o s i s a l g o r i t h m , h o p f i e l dn e u r a l n e t w o r k i i j ! 璧盔兰堡主堂焦堕奎 ! 笪丝 1 绪论 1 1 引言 多计算机系统是由若干自治多处理器单元通过通信链路互连而成的集合。在 处理器单元之间，需要通过通信链路相互交换信息【，信息从一个处理器发出，要 经过中间若干个处理器到达目的地。这种系统通常被称为信息传递或点对点的互 连网络口j 。对多计算机系统进行理论研究时，通常用图g ( ed 表示，顶点集v 表 示处理器单元的集合，边集e 表示通信链路的集合。 互连网络为多计算机系统中处理器单元之间的通信提供了一种有效的机制， 互连网络的拓扑结构决定着多计算机系统中处理器单元之间协同工作的性能。因 此，选择或设计一种高速、可靠的多处理器互连拓扑结构已成为组建多计算机系 统的一个重要课题。 现有的多处理器互连网络模型主要有以下几种：网格、带回绕边的网格和超 立方体。含有矿个处理器单元的网格互连的多计算机系统，每个处理器单元位于 h 行n 列的网格上，处理器单元可以用其在网格上的坐标来标识。 根据与每个处理器单元相连的处理器个数，可以将网络拓扑结构分为：三度 网格、四度网格、六度网格和八度网格，分别见图1 1 ( a ，b ，c ，d ) 。在这些网格结 构中，如果将边界处理器相连，就形成规则互连网格拓扑结构，因为此时，与每 个处理器相连的处理器的个数相同，称为带回绕边的网格结构。 超立方体【3 1 互连拓扑结构是一种在实践中得到广泛应用的互连网络模型之一。 在n 维立方体中，两结点相邻当且仅当表示u 和v 的二进制字符串中有且只有一 位不同。图1 _ 2 ( 钆b ) 分别是n ；3 ，4 时立方体互连结构。 ，、，一。， 卜_ + 一 ￥ v - 一t ，一i ，_ _ - 、 、?( ? j 泛r ? 、 ? 、， - 一一 号l i 二二争s 女糕 j - ，7 ，j 一 代 ， t 廿一 v 一二卜蔗j ， 净_ ： ： ； 卜_ 十y 曩一￥麓：_ ( 囊 一 ( a ) 三发网格( b ) 四度网格( c ) 六度网橹 ( d ) 八度网格 ( a ) t r i a n g u l a rg r i dc o ) s q u a r eg r i d ( c ) h e x a g o n a lg r i d( d ) o c t a g o n a lg r i d 圈1 1 四种网格结构 f i g 1 1f o u rg r i ds t r u c t u r e s 重丛查兰堡主兰垡笙塞 ! 堕笙 a 三维立方体b 四维立方体 ( a ) t h r e e - d i m e n s i o n a lh y p e r c u b cc o ) f o u r - d i m e n s i o n a lh y p e r e u b e 阁1 2 立方体结构 f i g 1 2h y p e r c u b es t r u c t u r e 在设计和选择多处理器互连网络拓扑结构时，主要需考虑的两个因素是网络 实现的成本和互连网络中数据交换的有效性。网络实现的成本包括以下两个方面： 一是与每个处理器单元相连的处理器的数量，数量越多，成本越高；另一+ 方面是 网络在结构和功能上是否具有可扩展性。而网络中数据交换的有效性通常是由网 络中处理器之间数据交换的速度和可靠性来衡量的。在多计算机系统中，处理器 单元之间数据交换的速度反过来可以用多计算机系统中任意两个处理器单元之问 的通信时延来衡量，通信时延是同网络中任意两处理器之间的最短路径的最大值 成正比的，也既是说同网络的直径成正比。可靠性，也可以说成是容错性，是由 系统中允许设备( 多处理器单元或通信链路) 发生故障的最大数目来刻画的，此 时，要求多计算机系统仍然能够正常工作。 相比其它网络互连拓扑结构，超立方体互连拓扑结构已经在工程应用领域得 到了，“泛地使用p ，4 j ，鲥。这是因为基于超立方体的互连网络有很多优秀的性质，比 如：对称性，可递归构建性，结点总数的对数级直径和连通度，这些性质可以保 证许多优秀的平行算法的实旋。更重要的是基于超立方体的互连网络具有较强的 容错性【”。 对基于超立方体拓扑结构的多计算机系统的研究，很多学者已经做了大量的 工作。在本章下面两节中。将着重介绍基于超立方体拓扑结构的多计算机系统的 容错性和诊断性研究。 1 2 多计算机系统的容错性 1 2 1 基本概念 在设计或选择多计算机系统的互连拓扑结构时，其中一个需要考虑的基本因 素就是系统级容错。系统级容错中的系统级是指系统中发生故障的设备被局限在 多处理器单元和处理器单元之间的通信链路。当系统中出现故障设备，如果系统 2 里鐾盔兰塑主兰垡丝苎 ! 壁丝 仍然能够正常工作，此时称系统具有容错性。容错性的大小是在系统正常工作的 前提下，由系统能够所允许出现敌障设备的最大个数来衡量的。 对于系统的“正常工作”，有两种定义。其中一种是：在隔离出系统中的故障设 备后，如果在系统中台有一个确定的拓扑结构，则系统可正常工作。对于这种定 义，在并行算法设计和多处理器结构方面已经做了大量的工作引。在这些算法中， 确定的拓扑结构的存在性是决定算法性能的重要因素。因此，通过执行这些算法 来判断系统中是否能够“正常工作”。系统的容错性是利用系统的冗于性来重新组建 系统而实现的。另一种定义是；如果在任意两个非故障处理器之间存在非故障的 通信链路，则称系统可正常工作f g , f o f u 。换句话说，如果剩余的非故障设备是连通 的，就可以认为系统可正常工作。这种容错模型特别适用于那些执行共行程序的 大型多计算机系统，系统允许在性能上有一定的降级但对系统互连拓扑结构的改 变不是很敏感。本文中采用后一种定义，在以后的章节中，系统中处理器单元相 互保持连通和系统具有容错性是同一个意思。 1 2 2 系统级容错的方法综述 衡量多处理器互连网络系统容错性的方法已经有很多种【】2 ”“ 。总体上，可咀 把这些方法归为两类：确定性方法和概率方法。确定性方法通常是用网络拓扑结 构的连通度来衡量网络的容错性。对于一个多处理器互连网络，假设用g 表示， 假定其连通度为盯g ) ，则该多处理器互连网络系统最多可以允许h g ) 一1 个处理器 单元发生故障，因为在这种情况下，互连网络的连通性仍然可以保证。对于n 维 立方体互连网络，按照确定性方法，基于一维立方体结构的多计算机系统最多可 以允许n 一1 个处理器单元发生故障，因为n 维立方体拓扑结构的连通度是n ，如 果系统中发生故障的处理器单元个数大于一，则不能保证系统中的处理器单元相互 保持连通，因为，当与非故障处理器单元相连的”个处理器单元均发生故障时， 系统会不连通。很显然，这种衡量基于n 维立方体结构的多计算机系统的容错性 的方法有其很大的局限性，第一是因为，当系统中出现，t 个故障处理器单元，而 这n 个故障处理器恰好是某一非故障处理器单元的n 个相邻处理器时，系统才会 的不连通 t s a6 】，然而，出现这种情况的可能性非常小；另一原因是该方法确定的 容错性与基于月维立方体互连的多计算机系统中处理器的总数2 ”相比而言非常小， 即n 2 n 非常小，例如，当n = 2 0 时，平均每个处理器单元发生故障的概率不得超 过o 0 0 2 。 为了改变这种容错性定义的局限性，报多更现实的确定基于n 维立方体互连 的多计算机系统的容错性方法被提出。文章 1 7 ，1 8 ，1 9 1 4 定义了禁止错误集，文章 f 2 0 。2 1 1 中定义了簇容错模型。禁止错误集的定义是为限制那些可能性非常小的错误 模式的出现。k 安全网络是一种典型的禁止错误集的模型，指出与每一非故障处理 - 重堕查堂堡主堂笪笙苎 ! 堑堕 器单元相连的处理器中至少有k 个处理器单元不会发生故障 1 7 , 1 9 , 2 2 】。然而，在这种 模型下，系统路由算法的设计交得异常复杂，目前，仅对七= l 和k = 2 时提出了有 效的路由算法 1 7 0 “。k 安全网络模型下的n 维立方体互连多计算机系统的容错性是 2 k ( n p 一1 9 1 玎】，可以看出，系统的容错性仍然只是d ( n ) 的数量级。 另一种衡量多计算机系统容错性的方法是概率方法。在概率方法中，假定系 统中的处理器或通信链路是以一定的概率发生故障，然后来计算系统保持连通的 概率。可以看出，概率方法相对于确定性方法来说，更能反映实际情况。通常假 定处理器单元或通信链路发生故障的概率是统计独立的，然雨，多计算机系统中 各个设备发生故障的概率总体上是不同的 2 4 】，计算这种概率方法下的系统的容错 性是n p 难的 2 “。文章 2 6 ，2 7 】中使用一些启发式算法来计算概率方法下的系统窑错 性。 所以，使用概率方法束研究多计算机系统的容错性是种很具有挑战性的方 法，设计出种简单、有效的概率容错性分析算法对于多计算机系统，特别是规 则互连的多计算机系统的容错性研究很有价值。 1 3 多计算机系统的系统级故障诊断 1 3 1 基本概念 随着多计算机系统中处理器单元个数的增加，系统中出现故障处理器单元或 故障通信链路的可能性也随之增大。为确保多计算机系统的可行性和高效性，及 时地定位和更换系统中发生故障的设备变的非常重要。一个行之有效的方法就是 对多计算机系统进行系统级故障诊断【2 ”。关于系统级故障诊断的定义将在后续章 节中进行详细陈述。 现代集成电路技术的发展是故障诊断被定位在系统级的根本原因。因为，构 成计算机中或数字设备中的基本元件一芯片的功能越来越强大，以前需要若干条 电路实现的功能现在只需要几块甚至一块芯片就能实现，更重要的是芯片的体积 和价格都呈下降的趋势，所以多计算机系统的故障定位也随着实际需要发生着变 化。在故障诊断的发展过程中，特别是多计算机系统的故障诊断中，人们按敬障 定位的范围将故障诊断分为以下四类： ( 1 ) 门级故障诊断；识剐出发生故障的门电路 ( 2 1 芯片级故障诊断：识别出发生故障的芯片 ( 3 、子系统级数障诊断：识别出发生故障的功能模块 ( 4 1 系统级故障诊断：识别出发生故障的处理器或通信链路 根据故障定位的不同，将故障诊断进行层次划分，如图1 3 所示，实际应用时 根据不同的需要决定相应的故障诊断范围。 4 型塑里塑堂l 一 ! 堑堡 r + 低层 幽1 3 故障诊断层次结构 f i g 1 3h i e r a r c h yo f f a u l td i a g n o s i s 可以看出，系统级故障诊断是一种高级的故障诊断，它将诊断定位在系统级， 仅考虑系统中的处理器单元和通信链路，不涉及到处理器内部的芯片或电路，这 样就大大降低了故障诊断的复杂性。 在系统级故障诊断中，多计算机系统充分利用各个处理器单元的自治能力， 先让处理器单元之间相互测试，然后根据测试结果和拓扑结构等条件，得到正确 的诊断结论。 多计算机系统的互连网络通常用图q e 司表示，图中的顶点集矿表示所有处 理器单元的集合，边集e 表示连接处理器之间的通信链路集台。用来诊断的测试 状态集通常用有向诊断图d g ( v , 目表示，有向边 e 当且仅当处理器“测试 处理器y 。e 中的每条边用测试结果进行标记。对于系统图g 中的顶点“，我们用 a ( u ) = i 表示顶点”的状态为非故障；a ( u ) = o 表示顶点“的状态为故障。 对于诊断圈d g ( k 目中的任一有向边 。对于结点总数为m 的，规则 图，f e f = ，。i v l 2 ，所以算法在第一阶段的时间复杂度为训叫- i - r i v l 2 ) ，在第二阶 段的时间复杂度是o ( r ，t v l 2 ) ，所以该算法总的时间复杂度为o ( i v l + r - m ) 。对于，! 维立方体，= 1 1 ，m = 2 ”，所以其时间复杂度为d “厅+ 1 ) 2 ”) 。 3 3 2 仿真试验及结果分析 在仿真试验中，为了简化计算，结点和边以相同的概率p 发生故障，p 取值范 围是o 1 0 5 ，立方体的维数h 从3 到1 0 。对于每一种取值，做1 0 0 0 次试验，然 后统计非故障结点连通的次数。非故障结点连通的次数与总试验次数的比值作为 重庆人学硕士学位论文3 多处理器系统的容错性 该系统的概率容错性。 连 通 性 嘏 辜 呻 连 通 性 慨 塞 呻 连口 塾 嘏口 芝o fq 结点和边的蘸豫勤 连0 蓬。 溉0 专。 连口 藿。 播d 专d n = 5 ，结点和边的故障辜p 连0 毳。 报口 专。 阔3 6 连通性概率v s 结点和边故障率 f i g 3 6p r o b a b i l i t yo f c o n n 刨v i t y v s p r o b a b i l i t yo n o d e 姐de d g e 龇m 2 l 兰筮型苎望型兰墅塑窒l 一 ! 墨竺望堡至竺堕窒堕堡 连 通 性 嘏 塞 叫 莲 遭 性 懈 蛊 吲 连 逯 性 嘏 塞 呵 图3 7 连通性概率v s 结点和边故障率 f i g 3 7p r o b a b i l i l yo f c o n n e c t i v i t yv s p r o b a b i l i t yo f n o d ea n de d g ef a i r t r e 连 通 性 慨 室 吲 图3 8 连通性概率v s 互连网络维数 f i g u r e3 8p r o b a b i l i t yo f c o r t a e c t i v i t yv s t h ed i m e n s i o no f i n t e r c o n n e c t i o nn e t w o r k 图3 6 是q 。，c q 。，o m q 。，1 m q 。和l t q 。在维数 = 5 ，6 ，7 ，8 ，9 ，1 0 时，在不 同的结点故障率和边故障率p 下的连通性概率曲线。可以看出，当结