（电路与系统专业论文）基于胚胎细胞阵列容错系统的实现[电路与系统专业优秀论文].pdf

基于胚胎细胞阵列容错系统的实现摘要 摘要 在电子技术迅猛发展并且目益成熟的今天，电子产品已经深入人类生活的各 个层面，d , n 个人大到企业甚至国家。随着电子系统日益复杂，若仅仅依靠提高 元件质量或采取人为的维护手段，无疑都不能真正解决问题。如何实现电路维护 的自动化才是未来发展的一大趋势。 遵循这一思路，人们从生物界中找到灵感，将生物体中的胚胎细胞的特性应 用于电子系统，建立起一种全新的基于胚胎细胞阵列的容错结构。阵列中每个细 胞执行很小的一部分功能，互相联合完成最终逻辑。当有细胞损坏后，冗余细胞 可以实时替代其工作，使整个系统重新正常运作。由于其特殊的结构，使其很有 可能被将来的v l s i 所采用。 本文主要工作是研究胚胎阵列的组成、容错机制，并探求更进一步的改进， 增强其实际应用的可能性。 本文首先介绍了故障诊断的基础知识，胚胎阵列整个想法的提出以及意义。 接着对胚胎阵列的构成，原理以及细胞内部结构作了详细阐述，在此基础上设计 完成个完整细胞，并用其构成个5 5 的胚胎阵列，完成搭建容错系统平台 的工作。 为了验证此容错结构的可行性，以x i l i n x 公司的s p a r t a n 1 i e 系列f p g a 为 实现硬件，使用b d d 方法将一位全加器置于此阵列中，实现了一位全加器的容 错，完成验证。 鉴于目前的细胞功能模块完成功能有限，实现逻辑的规模有限，最后我们对 细胞结构作一增强，使功能模块不仅能完成2 1 选择器的功能，也可配置为一位 全加减器，以便实现复杂逻辑，增强其实用性。利用此新的细胞结构，我们使 用了相近的细胞数实现了二位全加全减器。 关键字：容错系统，胚胎阵列，f p g a 基于胚胎细胞阵列容错系统的实现 e v o l v a b l eh a r d w a r e ： i m p l e m e n t a t i o no ft h ef a u l t t o l e r a n ts y s t e m b a s e do l ie m b r y o n i cc e l la r r a y b y h a o l i a n gr o n g at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo fm a s t e ro fs c i e n c e i n t h e s c h o o lo f l n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y o f t h e f u d a nu n i v e r s i t y a b s t r a c t t o d a y , w i t h t h e r a p i dd e v e l o p m e n ta n dg r e a tm a t u r i t y o ft h ee l e c t r o n i c t e c h n o l o g y , t h ee l e c t r o n i cp r o d u c t sh a v ea l m o s te n t e r e d i n t o e v e r ya s p e c to fo u r l i f e y o uc a ns e ei te v e r y w h e r e ，f r o mas i n g l ep e r s o nt oab i gc o r p o r a t i o ne v e nt h e g o v e r n m e n t a st h ed e p e n d e n c eo nt h ee l e c t r o n i cs y s t e mg r o w i n gm o r ea n dm o r e i t s o b v i o u s l yn o tae f f e c t i v ew a y t os o l v et h ep r o b l e m ，i f w eo n l yr e l yo nt h eq u a i l t yo f t h e c o m p o n e n t so rm a i n t a i nt h e mb yo u r s e l f , o n eo ft h em a i nt r e n d e n c yo ft h ee l e c t r o n i c d e s i g ni nt h ef u t u r ei sh o w t or e a l i z et h ea u t o m a t i z a t i o no f t h ec i r c u i t s f o l l o w i n gt h ei d e a ，p e o p l eg o tt h ei n s p i r a t i o nf r o mt h en a t u r e w ec a nc o n s t r u c ta b r a n dn e wf a u l t t o l e r a n ta r c h i t e c t u r eb a s e do nt h ee m b r y o n i cc e l la r r a yf u s i n gi t s c h a r a c t e r si n t ot h ee l e c t r o n i cs y s t e m e a c hc e l li nt h ea r r a yp e r f o r map a r to ft h e f u n c t i o n ，w h i c hc o m b i n et o g e t h e r t of i n i s ht h ew h o l el o g i c w h e nac e l l d i e ，t h e r e d u n d a n tc e l ln e a r b yw i l lr e p l a c ei tt oe n s u r et h es y s t e mc a l ls t i l lw o r kw e l l i ti sv e r y p o s s i b l et h a tt h i sn e wi d e aw i l lb ea d o p t e di nt h ev l s im a n u f a c t u r ei nt h ef u t u r e b e c a u s eo fi t sa p p r o p r i a t es t r u c t u r e t h ea i mo ft h i st h e s i si st or e s e a r c ho nt h ec o m p o s i n g ，f a u l t t o l e r a n tm e c h a n i s m a n dt oe x p l o r ep o s s i b i l i t yo fp u t t i n gt h i ss y s t e mt ot h ep r a c t i c eb yd o i n gs o m ef u r t h e r i m p r o v e m e n to v e ri t 2 基于艇胎细胞阵列容错系统的实现a b 啦t a c t f i r s t l y , t h eb a s i ck n o w l e d g eo ft h ef a i l u r ed i a g n o s i st h ed e r i v a t i o na n dm e a n i n go f t h e t h o u g h t s i s p r e s e n t e d 、t h e n w e g i v e ad e t a i l e d e x p l a n a t i o n o nt h e c o m p o s i n g ，p r i n c i p l eo ft h ee m b r y o n i cc e l la r r a ya n dt h e s t r u c t u r eo fa s i n g l e c e l l b a s e do f ft h er e s e a r c h ，w ef i n i s h e da5 5e m b r y o n i cc e l la r r a ya st h ep l a t f o r mo f t h es y s t e mu s i n gt h ei n t a c tc e l ld e s i g n e d ， i no r d e rt ov a l i d a t et h ef e a s i b i l i t y , w eu s i n gt h eb d dt oi m p l e m e n tao n e b i tf u l l a d d e ro nt h es p a r t a n - i i es e r i e sf p g ad e l i v e r e db yx i t i n xc o d u et ot h el i m i t a t i o no ft h ee e l lf u n c t i o n ，w ed e c i d e dt oe n h a n c et h ef u n c t i o nu n i t s ot h a ti tc a nf u l f i l ln o to n l yt h e2 - lm u x ，b u ta l s oc a ni m p l e m e n to n e - b i tf u l l a d d e r s u b t r a c t e r s ot h ep r a c t i c a b i l i t yi si n c r e a s e d w eu s i n gs i m i l a rn u m b e ro fc e l l s a c c o m p l i s h e dat w o b i tf u l la d d e r s u b t r a c t e rb a s e do n 也en e ws t r u c t u r ec e l l k e y w o r d s ：f a u l t t o l e r a n ts y s t e m ，e m b r y o n i cc e l la r r a y , f p g a 基于胚胎细胞阵列窖错系统的实现第一章概述 第一章概述 1 1 引言 随着电子技术的飞速发展和日益成熟，人类对于电子产品的需求和依赖程度 也与日俱增。无论是大规模的企业、公司或是分散的家庭和个人，都必须承认高 集成度的电子系统对提高生产利益和生活质量起着举足轻重的作用。 但是无论是元件还是电路和系统，由于制造工艺的限制、使用寿命以及工作 条件等影响，故障的产生是不可避免的。早期的系统故障主要依靠技术人员凭借 自己的经验和理论知识，并借助一些常规工具来完成，但随着电子系统功能和规 模的不断增加，基于先验知识和设计规则的故障检测方法已逐渐难以应付，一旦 系统遭到损坏，在庞大的系统中人为的找寻错误和修正往往事倍功半。因此系统 可靠性成了不可忽视的指标。 提高系统可靠性的技术途径有很多，但归纳起来大体可分为两大类：一是提 高元部件本身可靠性的技术，即避错技术：二是用给定元部件构成商可靠性系统 的技术，即容错技术。然而避错技术无论是从实现还是效用都有一定的限制。因 此想要进一步提高可靠性。就必须采用容错技术。随着计算机与电子科技的不断 进步，容错技术已成为当今和未来电路设计中不可缺少的部分。 1 2 容错技术概述 由于数字化已成为电子系统设计的趋势，因此本文主要讨论的都是数字系统 的容错技术。 容错是靠资源的冗余和对资源的精心组织来实现的，容错技术的优越性在 于：使用线性增加的冗余资源可以换取指数增长的可靠性，它不仅能补偿因系统 的规模大而造成的可靠性损失，而且能使系统的可靠性极大提高。 1 2 1 容错技术的内容【 容错技术主要包括下列三个方面的内容： 1 故障检测与诊断技术 故障检测的目的是回答系统是否发生了故障。故障诊断则是在故障检测的基 础上进一步回答系统中哪里发生了故障、发生了什么性质的故障实现故障的定 位和定性。 基于胚胎细胞阵列容错系统的实现第一章概述 故障检测与故障诊断不提供对故障的容忍，只提供对故障的告警。故障检测 与诊断可以联机进行，也可以脱机进行。 2 。故障屏蔽技术 故障屏蔽技术是通过增加冗余资源的方法来换取可靠性，使系统在出故障时 仍能维持正常功能。根据冗余资源的不同，通常有硬件冗余、软件冗余、信息冗 余、时间冗余之分。实际应用中，这几种冗余方式可以单独使用，也可以混合使 用。 故障屏蔽技术也叫掩蔽冗余技术。主要用于可靠性要求较高且在一段时间内 既要保持连续运行又无法修理的地方，如航空、化工等场合。但是单纯的故障屏 蔽只能容忍故障，不能给出故障警告且受静态冗余配置的限制。 3 系统重组与恢复技术 重组是指在检测、诊断出故障后，用后援备份模块替换掉失效模块，或者切 除失效模块，改变拓扑结构，实现系统重新组合。恢复则是在重组后，使系统操 作回到故障检测点或初始状态重新开始。如果是回到初始状态从头开始运行则叫 重新启动，简称“重启”。 对重组时切除或替换掉的失效模块，往往要联机或脱机进行修理使之复原， 称为修复。将修复了的模块重新加入系统则称为重构。修复和重构也属于系统重 组与恢复的范畴。 1 2 2 容错技术的主要实现方法1 对于容错来说，无论是故障检测、故障屏蔽或是系统重组，它们都是建立在 资源冗余的基础上的。因此下面分别介绍资源冗余的实现方法： 1 信息冗余 信息冗余是指通过在数据中附加冗余的信息以达到故障检测、故障屏蔽或容 错的目的。信息冗余的例子有检错码及纠错码，它们是通过在数据中附加冗余的 信息或通过把数据字映射至含有冗余信息的新的表示而形成的编码。 信息冗余通常要按比例增加部分硬件( 主要增加存储设备、数据通路、处理 器的复杂性以及编码器和解码器) ，也要消耗一定的时间( 编码和解码的延时) ，主 要是用增加信息的冗余度来提高可靠性的。 常用的编码方式有：奇偶校验码、循环冗余码、汉明码、算术码、伯格码等 等。选择什么样的码剁来对信息进行编码，主要取决于码的特性和实际应用需要。 表1 1 是几种常用码的特性和应用。 基于胚胎细胞阵列容错系统的实现第一章概述 码的特性 码制 主要应用场合 冗余度编译码电路检，纠错能力 奇偶码一般异或树通常检单错和 存储器：异步串 奇数位错行通信；总线 循环码低线性反馈移位寄检多位错海量存储器：同 存器步串行通信链路 汉明码低 硬件、软件均可纠单错、检双错存储器 伯格码低简单 检多位单向错存储器：通信 表t i 常用码的比较 2 时司冗余 时间冗余利用附加的时间执行系统的功能，实现容错。基本思想是重复进行 计算以检测故障。 ( 1 ) 对于瞬时故障，相同的计算重复进行两次或更多次并比较结果以检测是 否有差错。如检测到差错可再计算次看是否仍有差错。但这种方式只对瞬时故 障有效，无法测试永久故障造成的差错。 ( 2 ) 若配以少量的硬件，时间冗余也可用来检测永久故障。基本思路是将第 一次计算结果存储起来。在进行第二批数据计算之前，选择特定的编码方式将数 据进行编码，对编码后的数据执行计算，结果经译码与第一次的结果作比较。常 用的方法有交替逻辑、移位重算、交换重算和双机比较重算。袭l ，2 对这几种方 案做了比较。 方案硬件增加时间增加 双机比较1 1 4 2 8 ，8 移位熏算1 6 9 1 2 2 6 7 双机比较重算 9 4 0 2 7 表l ，2 解决永久故障方案的比较 3 软件冗余 软件冗余主要可分为两类：一致性校验和能力校验。 ( 1 ) 一致性校验应用事前知道的信息特征来检验信息的正确性。一般有如下 几种类型：信息越界检查、非法指令检查、系统性能与预期性能比较和字技术溢 出检验。 ( 2 ) 能力校验用来证实系统具有预期的能力。包括存储器测试、逻辑部件测 基于旺胎细胞阵列容错系统的实现第一章概述 试和多处理机系统中处理机间通讯测试。 4 硬件冗余 硬件冗余是指通过应用附加硬件来实现故障检测及容错的技术。真正实现系 统容错，达到连续处理且不降低性能的必须采用完全硬件冗余。硬件冗余从实现 形式上可以分为被动冗余、主动冗余及混和冗余三种。 ( 1 ) 被动冗余又称静态冗余，是指冗余结构并不随故障情况变化的冗余形式。 被动冗余应用了故障掩蔽的概念，将发生的故障隐蔽起来，防止故障造成差错。 基本机理是通过多数表决掩蔽发生的故障。 晟简单也是最常用的形式是三模冗余( t r i p l em o d u l a rr e d u n d a r c y ，简称 t m r ) ，结构如图1 1 所示。三个相同的模块接收三个相同的输入，产生的三个结 果送至多数表决器。表决器的输出取决于它三个输入的多数。若有一个模块故障， 则另两个正常模块的输出可将故障模块的输出掩蔽，从而不会在表决器输出产生 差错。t m r 的主要问题是表决器的故障同样会造成系统差错。为了克服这一困难， 可采用三重表决，如图1 2 所示。 r 一，一、厂，一、 输入 _ 横瓣i_ 衰抉* )- f 模璃it 寰诗# ) 抽出 0 一 l j 卜一7 崔蚓够- n 圈0 圈。 陌1 ，。翮 国司裔。 l 一一 、一一7 l j 。一 图1 1三模冗余( t m r ) 图1 2 多级三熏表决t m r t m r 的推广是n 模冗余，简称n m r 。与三模冗余原理相同，但采用n 个相同 的模块。n 一般取奇数，方便多数表决。它可以容忍( n 一1 ) 2 个模块故障，但 是功耗、重量、成本及体积都会有所增加。 ( 2 ) 主动冗余又称动态冗余，所谓动态，就是综合运用几种技术来达到更强 容错能力的一种综合性容错技术。“动态”主要体现在作为系统正常资源的冗余 模块数随着检测到的故障数多少而变化。系统在正常状态下以标准模块配置进行 工作；一旦检测出故障，紧接着进行重组和恢复，从而消除故障的影响，达到容 错的目的。本文所实现的容错结构属于动态冗余。 动态冗余主要的结构有单模替换和成对替换两种。 a 单模替换结构 这种系统的特点是：n 个相同模块中，只有一个为主用模块处于运行状态， 用以产生系统输出，其余模块作备份处于待命状态；若主用模块发生故障，则进 行重组，使个正常的待命储备模块转为主用模块，使系统恢复正常运行。图1 3 基于胚胎细胞阵列容错系统的实现 笫一章概述 给出了这种系统的结构框图。 主用模块f 翮主用模块 幔块1 l。，。j 备用 模块 图l3 单模替换结构框图 输出 b 成对替换结构 这种系统的特点是：n 个模块中总有两个组成主用模块对，他们并行进行比 较：一旦比较结果不一致便启动重组，将改模块切除，而换上另两个备用模块作 主用模块对。其结构框图如图1 4 所示。 _ _ 骊丽r _ 一1 、_ 主用 模块 备用 模城 广i 。 。一 i 楼蠼2j l 二二 1 1 1 1 。1 。 1 1 一 模抉3 图1 4 成对替换结构框图 输出 瓜i l 剽 l j 不一致 ( 3 ) 混和冗余的含义就是将主动冗余和被动冗余结合起来构成的混和冗余结 构。混和冗余的成本较高，因此一般用于需要极高可靠度的场合。 1 - 3v l s i 阵列处理与基于胚胎细胞阵列的容错结构 1 3 1v l s i 阵列处理的容错【4 首先，在v l s i 阵列的制造阶段，在有制造工艺缺陷的情况下，需有某种形 式的容错性才能获得效能价格合算的成品率。这称为制造时的容错性问题。第二， 摹 甲：醒 基于胚胎细胞阵列容错系统 1 句实现第一章概述 如果出错发生在阵列安装到系统中以后，则给定足够的时间，阵列可以重新编译 从而具有合适的功能，这称为编译时的容错性问题。第三，需有某种形式的容错 性能克服在处理器工作期间出现的错误，并允许系统继续执行其功能，这称为运 行时的容错性。制造时的容错性就是一种由真实阵列构造物理阵列的技术；而编 译时和运行时的容错性是由物理阵列构造逻辑阵列的技术，下面分别作介绍。 1 制造时的容错 制造时的容错性就是在芯片制造好后消除电路的错误，它的目的是要将成品 率提高到满意的程度，基本的技术就是从具有冗余部件的真实阵列中重构具有确 定尺寸的有效物理阵列。如果有效单元的数目小于阵列所需的数目，则该芯片将 被废弃；如果具有足够多的有效单元，它们就可以被重构，从而形成所需的结构。 用于圆片级集成的阵列处理器的重构方法有：金属化技术、激光工艺、电工艺、 可重编程技术、开关格阵技术、混合封装技术。 2 编译时的容错 编译时的容错性重构方案除了测试和工艺方法不同以外，其它的类似于软件 支持的制造时的容错性设计。一个运行时的容错技术可以应用于编译时的容错设 计中，但反过来不行。另外，大多数实时应用要求有实时的容错性，因此，讨论 的重点应是运行时的容错性。 3 运行时的容错 这里容错的主要目的是保证当大规模阵列处理器处在运行模式下时，能连续 正常工作。运行时的容错性设计的目的是：开发阵列的规则性和局部性；开发阵 列算法的结构特性；使由于考虑容错性而消耗的时间最小。一个典型的容错性方 案包括错误检测、重构和恢复。错误检测可以借助于一些自检电路。重构是用没 有出错的元件替代邻近的出错元件，并对电路重新布线，从而形成一个新的阵列。 本文讨论的容错系统属运行时容错。 1 3 2 基于胚胎细胞阵列的容错 在v l s i 处理阵列的情况下，通常是用备用的物理单元和连线替代出错的单 元。大部分硬件冗余重构技术，都是依赖复杂的算法给逻辑单元阵列重新分配物 理资源来实现的。而多数情况下算法的执行是靠一个中央处理器完成的，它同时 也负责诊断和协调物理阵列的重构工作。这种方法虽已证明是有效的，但如果负 责实现容错的处理器出错的话，那么一切都将处于崩溃状态。p 1 与此同时，生物学不断和电子学结合，产生了遗传算法、神经网络等成功的 学科之后，从生物界得到灵感来改善电子系统中的结构和设计已经成为一种习惯 基于胚胎细胞阵列容错系统的实现 第一章概述 思路。因此很容易人们就想到要将生物界中的某些特性与容错系统相结合。 二十世纪末，人们把目光投向了胚胎细胞，生物体由无数个胚胎细胞组成， 每个细胞内都有相同的基因信息，它们各自完成一个特定的基本功能，而这些基 本功能由不同段的基因信息所决定。基本功能经过组合后就构成生物体的整个生 命活动。当生物体中某一细胞损坏时，临近的空闲细胞会读取自身基因内的信息 取代损坏的细胞，生物体不会死去，从而保持生物体的正常活动。胚胎细胞阵列 的容错系统正是在此灵感下应运而生的。 1 9 9 7 年，c e s a ro r t e g a 和a n d r e wt y r r e l l 在先前的研究成果上较完整的阐述了 一个胚胎细胞的结构，并用其实现了f ( a ，b ，c ) 一a b 十a c 十b c 的简单逻辑功能1 6 1 。 1 9 9 8 年，c e s a ro r t e g a 与a n d yt y r r e l 用相同结构完成了较复杂的二位 j n 减法计数 器和三位分频器。2 0 0 3 年，x z h a n g ，gd r a g f f y , a gp i p e ，n g u n t o n 和q m z h u 对单元胞的结构作了更近一步的细化捧j 。同年，r i c h a r dc a n h a m 与a n d y t y r r e l l 提出了简化配置信息的单元胞提高了整个自愈系统的工作效率【9 j 。 由于其结构的特殊性，胚胎细胞阵列的主要研究目的是为了提高大规模 v l s 阵列容错的设计与性能，使其有如下几个特点： 结构高度整齐，简化了在硅片上的实现。 单个细胞的特定功能可以改变而不会影响到其他细胞。 将诊错逻辑置于每个细胞之内，若其中一个损坏不会大规模影响整个系 统的容错功能。 关于胚胎细胞结构和工作机理将在文中作详细说明。 1 4 本文的主要工作及内容安排 基于胚胎细胞阵列的容错系统的提出距今大约1 0 年左右的时间，受许多客观 条件的限制，目前尚处于研究阶段，主要集中于细胞结构、节约硬件开销等方面 的探讨，其实用性并没有得到完全的发挥。随着技术的发展和人们的投入，相信 这方面的应用会出现在人们的面前。 本文的主要工作是研究这种全新的容错结构，并且选用适当f p g a 进行实例 验证以探求可行性及不足。具体的内容安排如下： 第二章：容错系统的基本知识。 第三章：基于胚胎细胞阵列容错系统的工作原理 第四章：胚胎细胞的硬件结构。 第五章：基于胚胎细胞阵列容错系统的实例 第六章：总结目前的工作，并对未来的研究方向进行展望。 o 基于胚胎细胞阵列容错系统的实现第二蕈容错系统的摹本知识 第二章容错系统的基本知识 2 1 本章概述 本章主要介绍容错系统中的些基本概念和技术。2 2 介绍了故障的定义以 及简单的故障模型。2 3 对故障的检测作初步的介绍。2 4 介绍了评测容错系统的 些基本参数。 2 2 1 故障定义 1 , 2 , 3 1 2 2 故障与故障模型 故障是指系统的硬件中发生的物理缺陷、设计制造的不完善或软件中隐含的 错误。硬件故障的例子有线路的短路、开路或晶体管不能正常导通或截止等。软 件故障的例子有程序中的死循环。 差错是系统中由于故障丽造成的信息或状态的不正确。故障是差错的原因， 而差错是故障的结果。失效是指系统未能正确提供预先指定的服务。差错是失效 的原因，而失效是差错的结果。故障会造成差错，但并不总是故障一出现就立即 会产生差错。同样，差错会造成失效，但并不总是差错一发生就造成失效。 故障可以用故障性质、故障值、故障限度和范围以及故障的时间间隔等参数 来描述。 故障性质是指故障是属于逻辑故障，还是非逻辑故障。凡是使电路或系统中 的某一节点的逻辑值为正常值的相反值的故障均属于逻辑故障。如元件输出端开 路、输入端的开路、元件损坏以及竞态故障等均属于逻辑故障。除逻辑故障以外 的故障都称为非逻辑故障。如同步时序电路中的时序故障和电源失效等。 故障值是指电路或系统中故障产生的错误逻辑值是固定的，还是可变化的。 如果是固定的，那么它的固定值是多少。故障的限度及范围是指故障的影响是局 部型的，还是分布型的。局部型故障只是影响单变量，而分布型故障则影响多个 变量。例如逻辑故障一般是局部性的故障，而同步时序电路中的对钟故障是属于 分布型的故障。故障的时间间隔是说明故障是永久性的还是间歇性的。 2 2 2 故障模型i l o ，3 】 一个元件、电路或系统的物理故障是千变万化的。一方面故障的种类就是各 基于胚胎细胞阵列容错系统的实现 第= 章容错系统的基奉知识 种各样的。就以短路故障为例，一个门电路输入端短路，两个输入端之间的桥接 短路，一个门的输入端和输出端之间的短路，奇数级或偶数级的门输入与输出之 间的短路等等，引起的失效结果会有很大的差异。另一方面，故障的数目在各种 系统中有很大的差异，而多故障组合的情况就更多了。因此，为了研究故障对电 路或系统的影响，诊断故障的位置，有必要对故障作一些分类，并构造最典型的 故障，这个过程称为故障的模型化。用以代表一类故障的典型故障称为模型化故 障。 故障模型化有两个基本原则：个是模型化故障应能准确地反映某一类故障 对电路或系统的影响，即模型化故障应具有典型性、准确性和全面性：第二是模 型化故障应该尽可能简单，以便作各种运算和处理。这两个要求从某种意义上说 是矛盾的。因此往往要采取一些折衷的方案，由于解决的问题不同和研究侧重面 不同，采用的故障模型也小同。下面介绍几种目前常用的模型化故障。 1 固定型故障 固定型故障( s t u c kf a u l t s ) 模型主要反映电路或系统中某一根信号线( 如门的输 入线或输出线、连接导线等) 上的信号的不可控性，即在系统运彳亍过程中永远固 定在某一个值上。在数字系统中，如果该线( 或该点) 固定在逻辑商电平上，则称 之固定l 故障( s t u c k - a t 。1 ) ，简记为s 一和1 ；如果信号固定在逻辑低电平上，则称之 为固定0 故障( s t u c k a t 0 ) ，简记为s - a 0 。 固定型模型在实际应用中用得最普遍，因为电路中元件的损坏、连线的开路 和相当部分的短路故障都可以用固定型故障模型比较准确地描述出来，而且由 于它的描述比较简单，因此处理故障也比较方便。以1 y r l 门电路为例，输出管 的对地短路故障属于s a 0 故障，而输出管的开路故障属于s a 一1 故障。任何使输 出固定为1 的各种物理故障都属于s - a - l 故障。 需要着重指出的是故障模型s a 1 1 和s 廿0 都是相对于故障对电路的逻辑功能 而言的，而同具体的物理故障是没有直接的关系。因此s a 1 故障决不是单纯指 节点与电源的短路故障，s 。a - o 故障也不是单纯指节点与地之间的短路故障，而 是指节点不可控，始终使节点上的逻辑电平停留在逻辑高电平或逻辑低电平上的 各种物理故障之集合。 在对个系统或电路作故障模型 化时，必须考虑其中的每一根连线的 故障情况，而不能以个节点为研究 对象。例如在图2 1 中门l 有扇出，它的 输出分别送至门2 和门3 的输入端，考 虑故障模型化时应该对连线a 、b 和c 分 r _ “。t 、 j _ _ 、秘 l 三，广了f 。一、 = j ，纛! j 一 图2 1 电路故障模型 基于胚胎细胞阵列容错系统的实现 第二帝容错系统的基本知识 剐进行故障模型化，而不能把三点看成一点处理，因为这三点上的故障可能是不 一样的。例如b 点与a 点之间可能有断开的物理故障，这样a 正常时b 却有s 廿l 故障； 又比如b 点与a 和c 都没有故障，但i - j 2 内部有物理故障，导致b 点有等效 s a 口f 口0 ，1 ) 故障，但这个故障不会影响a 和c 的工作，因此这三个点的故障情 况是不一样的。有时为了简化故障处理过程，也可以把这种点看成一个点，但这 时所处理的故障是不完全的。因此，故障的模型化采用什么方法，完全取决于故 障的基本策略。 2 桥接模型 固定型故障主要指系统或电路内节点上的信号不能用原始输入信号控制的 故障，因此固定型故障一般不会改变电路的拓扑结构，即不会使电路或系统的基 本功能有根本性的变化。但是，如果一个系统或电路中发生了短路故障，而短路 故障的情况又是多种多样的，则完全有可能改变电路的拓扑结构，导致系统或电 路的基本功能发生根本性的变化。 在实际应用中常见的两种桥接故障( b r i d g i n gf a u l t ) ，即元件输入端之间的桥接 故障以及输入端和输出之间的反馈式桥接故障。这是因为一个元件的输入和输出 在一块印刷板上是离得比较近的，所以产生短路故障的可能性比较大。 x 1 恐 屯 毛 恐 托 r 一一、x 卜厂、 一。 毯广而七一厂t j 、 一芝j 一、卜彳、卜 之。7l 一7 l 7 。7 玛 a i 故障电路b 模型化电路 图2 2 输入端短路故障等效于线与关系 一个元件输入端之间的桥接故障一般形成线与关系，对于与门来说，它的等 效关系如图2 2 所示。对其他元件也有类似的等效关系。一个元件输出端至输入 端之间的反馈式桥接故障比较复杂，发生这类故障时有可能把组合电路改变成时 1 ：门? 3 ，u “ “ a 故障电路b 模型化电路 基十胚胎细胞阵列容错系统的实现 第二章容错系统的基本知识 图2 3 反馈式桥接故障的一般模型 序电路，甚至使电路发生振荡而趋于不稳定。图2 3 给出了一般反馈式桥接故障 的逻辑模型，其中x ，x ：，t ，。，x 。是电路f 的输入端，输出y 与s 个输入 一，x ：，x ，发生桥接故障。 3 暂态故障 暂态故障( t e m p o r a r yf a u l t s ) 是相对固定型故障而言的。它有两种类型，即瞬 态故障( t r a n s i e n tf a u l t s ) 和间歇性故障( i n t e r m i t t e n tf a u l t s ) 。 瞬态故障不是由电路或系统中硬件引起的故障，而是由电源的干扰和电磁的 辐射等原因造成的，因此这一类故障无法人为予以重复出现。这种故障在计算机 内存芯片中经常出现，但般来说，这一类故障不属于故障诊断的范畴，但在研 究系统的可靠性时考虑这个问题。 间歇性故障是可重复出现的非固定型故障。产生这类故障的原因有：元件参 数的变化，接插件的不可靠、焊点的虚焊和松动以及温度、湿度和机械振动等其 它环境原因等。因此有些间歇性故障应该在改善使用条件和制造工艺方面来加以 防止。 由于间歇性故障是客观存在于个实际系统或电路中，但又并不是总能反映 出来的，因此，有必要对这类故障定义两种状态：如果故障存在，但它没有反映 出来，则称电路或系统处于“故障无作用状态”：反之，如故障影响着系统或电 路的正常工作，则称电路或系统处于“故障作用状态”。从间歇性故障产生的原 因可以看出，它的影响是随机的，而不是确定性的，因此采用概率分析的方法对 它进行模型化。 4 时滞故障 时滞故障( d e l a yf a u l t s ) 主要考虑电路中信号的动态故障，也即电路中各元件 的时延变化和脉冲信号的边沿参数的变化等。这类故障主要导致时序配合上的错 误，因此在时序电路中影响较大。这可能是由于元件参数变化引起的，也可能是 电路结构设计不合理引起的，后者经常可以用故障仿真的方法来解决，对前者的 检测和诊断往往是很困难的。 以上所述的四种典型故障，事实上还不能包括一个或系统中可能发生的全部 故障。但是对一般的系统或电路，根据统计可知，固定型故障占故障总数9 0 以 上，其它故障有些也可等效为固定型故障。本论文所作的主要工作也是针对固定 型故障的检测和修复的。 2 3 故障检测【3 】 由于故障模型和方法的种类繁多，对测试方法进行完全分类是非常困难的。 箨于胚腊身h 胞阵列容错系统的实现 第二章容错系统的基本知识 我们可以按照两个标准进行分类：离线测试和在线测试、外部测试和内部自检测。 第一个分类是基于测试是在电路运行时进行的( 在线测试) ，还是在单独立指定的 时间段进行的( 离线测试) ；第二个标准是基于测试是由电路本身内部的测试模块 完成的( 自检测) ，还是依靠外部的测试设备完成的( 外部测试) 。 2 3 1 离线外部测试 离线的外部测试是最常用的数字电路的测试方法。这类方法中包括多种适用 于装配过程和运行现场的测试技术。在封装以前就装配好测试电路，它的优点是 可以访问电路内部的线和元件。当要对电路进行离线测试时，而这时只能访问该 电路的i o 脚，就出现了其它的离线外部测试技术。最常用的方法就是，输入一组 专用信号并观察电路的相应输出，然后将这些输出值和己知正确的输出值进行比 较，如果不一致就说明存在错误。显然，这项技术的主要优点就是不需要在电路 内部增加额外逻辑，商业应用中较有利。而它的缺点就是相当费时，( 取决于对 电路中的全部或部分线路进行测试所需的输入变量组的多少) ，要找到一组能够 检测出大多数或全部电路故障( 特别是时序电路) 所需的一套输入输出变量组是 很困难的，而且这种测试方法对故障进行精确定位也是很团难的。 2 3 2 离线自检测 离线自检测在需要现场测试的电路中是一个非常普遍的方法。通过在电路内 部集成额外电路，就能克服某些外部测试的缺点f 例如，访问电路内部的某些线 与元件的能力) 。扫描寄存器属于这类技术，是将一些或所有的存储单元( 触发器， 寄存器) 连结在一起形成一个长的移位寄存器，以便能在任意给定时间对电路状 态进行快速检测。 另一个常用的离线的自检测技术，是使用一组输入输出变量进行外部测试。 在这种情况下，输入信号并不是在芯片外面储存的，而是由电路内部自身按一定 算法产生的( 通常是一套伪随机数) 。这种方法虽然不能保证百分之百地检测出所 有故障，但却能通过使用较少的附加逻辑检测出大多数的故障。其实，这项技术 所需的大部分附加逻辑都用于输出变量组的分析了：严格来说，自检测需要在电 路内部验证输出的正确性( 自校验电路1 ，而这项工作通常比输入变量的产生更加 复杂。 2 3 3 在线自检测 基于胚胎细胞阵列容错系统的实现第二章容错系统的基本知识 在线自检测技术通常是在原电路上的进一步发展，因此很难把它定义为一种 标准的测试技术。在数据通道中通常是使用错误检测码实现的：通过使用信息的 冗余位可以检测到改变数据值的错误( 其中最简单的方法就是利用一个奇偶校验 位) 。通常在线自检测是根据每个电路的具体的结构和功能，利用它们各自的特 点和性能，对电路的行为进行验证。缺乏标准的在线自检测方法，自然也是商业 在线自检测电路少的个原因。 在线自检测技术需要相当多的附加逻辑，这也是另个妨碍了它在商业中的 广泛应用的原因。在主流应用中，不需要电路有在运行中检测错误的能力，因为 结果的正确与否一般不是十分的重要的。而在关键的应用中，通常通过二备份或 三备份电路进行比较输出结果进行检错。这种方法虽然能检测到电路发生的所有 单个故障，但不能检测多重故障。 因此，由于硬件开销的重要性，直到目前为止，在主流商业应用中的广泛采 用在线自检测仍被认为是相当昂贵的。特别在硬件级别中更少使用，通常在软件 中使用。通常隋况下，电路在制造后要对其进行一个不完全的离线测试，以便排 除一些明显有毛病的芯片( 保证质量) ，而许多故障只有在电路不能正确运行时才 被检测到，然而随着电路的复杂化和制造成本的增加，一些基本的自检测技术开 始被集成到设计中，而且很快成为不可缺少的一部分。 虽然在线自检测不可能很快成为主流应用中的一个常规特征，但是在某些特 殊应用中，至少在某种程度上用到了这一技术。商业用的f p g a ，由于常用于模 型设计，所以经常包括某种形式的自检测，通常以边界扫描形式( 一个在芯片的 输入输出管脚处的扫描寄存器) 存在，这些将有助于调试新设计。然而，随着f p o a 变得越来越复杂，制造商们不仅在原型设计而且对电路内部进行检错也越来越感 兴趣。 本论文利用阵列的规则性来实现自修复，属于在线自检测的范畴。 2 4 1 可靠度与失效率 2 4 容错系统的评估2 1 可靠度与失效率是研究器件可靠性对系统影响的参数，设有一个具有n 个 元件组成的系统，经运行时间t 后，有f ( t ) 个元件失效，其余s ( t ) 个元件仍保持 完好，定义元件的可靠度r ( o 为：r ( t ) = s ( t ) n = 1 一f ( t ) n ( 1 ) r ( t ) 是时间t 的函数，定义元件在时刻t 的失效率为： 墨主堕堕塑里堕型窒堡至竺塑窭墨 蔓三雯查堂墨堑塑苎查! ! 堡 z ( t ) = 1 s ( t ) d f ( t ) d t ( 2 ) 失效率z ( t ) 表示单位时间内失效元件与非失效元件数之比，它是时间的函数，随 时间的变化曲线一般呈浴盆状，称为浴盆曲线。如图2 4 所示。曲线可分为三个 x 兰鉴塑- 一登堑翌- 一p 塑失苎期 图2 4 浴盆曲线 时期。第一个时期称为早期失效期，在此期间，失效率下降很快。这是由于电子 元件中的一些缺陷在此期间暴露出来。在实际使用中，可以采用“老化”措施来 加速这个时期的过波，也可以通过长期存放来先越过这一时期。第二个时期称为 有用生命期，在这时期失效率较低，基本上不随时间变化。第三个时期称为耗 损失效期，在此期间，元件已被用旧，趋向衰亡，故失效率急剧增大。通常在有 用生命期失效率可视为常数，用 表示。由公式( 1 ) ( 2 ) 可推得： d r ( t ) d t = - - r ( t )( 3 ) 对式( 3 ) 积分，可德：r ( t ) = e ”( 4 ) 式( 4 ) 表明当失效率为常数时，可靠度与时间成指数关系。失效率越大，可靠度下 降越快。 2 4 2 故障时间 1 平均无故障时间 系统的平均无故障时间m t t f ( m e a nt i m et of a i l u r e ) 指的是一个系统产生第 个故障的平均时间。它是一个期望值，可用概率论计算出来，根据期望值公式： m 丁盯= 【t f ( t ) d t ( 5 ) 式中绯) 为失效密度函数，失效密度函数定义如下： 邝) ：一掣( 6 ) 可得： 榭f m l t ! 翰d t f = l r mm 当失效率为常数 时， 删= f e “折= 去 ( 8 ) 基于胚胎细胞阵列容错系统的实现第二章窖错系统的基本知识 2 平均修复时间 平均修复时间m t t r ( m e a nt i m et or e p a i r ) 是修复一个有故障系统所需的平均 时间。系统的平均修复时间是很难估算的。 m t t r 2 1 u ( 9 ) u 为修复率，它是指单位时间内可修复系统的平均次数。 3 平均故障间隔时间 平均故障间隔时间m t b f ( m e 觚t i m eb o 铆e o nf a i l l l r e ) 足指系统连续发生两次 故障之间的平均间隔时间。 m t b g = m t t f t m t t k ( 1 0 ) 基于胚胎细胞阵列容错系统的实现 第三章基十胚胎细胞阵列容错系统的工作原理 第三章基于胚胎细胞阵列容错系统的工作原理 3 1 本章概述 本章介绍详细基于胚胎细胞阵列容错系统的运作机制。3 2 介绍了胚胎阵列 灵感的发源。3 3 对胚胎阵列的容错策略作详细介绍。3 4 介绍了分析胚胎阵列可 靠性的模型，为3 5 作准备。3 5 则对现有的容错策略作可靠性分析，并作比较。 3 2 1p o e 模型 3 2 胚胎阵列的提出 地球上