（电路与系统专业论文）基于单细胞替换的胚胎阵列容错系统.pdfVIP

基于单细胞替换的胚胎阵列容错系统摘要 摘要 胚胎阵列容错系统将生物中细胞替换的机制应用在电子系统中，是一种带有 自恢复功能的新型容错结构。胚胎阵列通常采用列( 行) 替换法进行容错。列替 换法实现起来比较简单，但却造成很大的资源浪费：为了能够替换一个出错细胞， 至少需要一列的空闲细胞做为备用；阵列执行列替换以后，被替换掉的那一列中 没有出错的细胞也不能再被利用。另外，胚胎阵列为实现容错，在每个细胞需中 都存储整个阵列的配置信息，占用大量资源。系统越大，存储配置信息占用的资 源越多。 本文主要从容错策略和配置信息存储两个方面对胚胎阵列进行研究，对细胞 结构进行改进，并以f p g a 为硬件载体对改进后的胚胎阵列进行可行性及优势验 证。 首先，本文尝试采用单细胞替换法的容错策略。单细胞替换法基本思想是： 当发现一个细胞出错后，只需用一个空闲细胞替换该出错细胞；同时，该出错细 胞所在列的其余细胞仍然能够正常使用。单细胞替换法避免了在容错的执行过程 中把有用细胞当成无用细胞从阵列中剔除的缺点，同时由于采用单细胞替换法替 换一个出错细胞只需一个而不是一行的空闲细胞，使得傲为备用的冗余阵列规模 大大减少，从而减少了整个系统的资源浪费。 其次，在胚胎阵列实际执行替换容错的时候，每个细胞虽然都存储了整个系 统的配置信息，但只可能用到那些它可能会执行的功能所对应的配置信息。因此 本文对细胞结构中的配置信息模块进行改进，使每个细胞只存储那些它们可能用 到的信息而不是整个阵列的全部信息，来减少系统资源的占用率。 实验结果证明，单细胞替换法和配置信息的改进在一定程度上减少了资源浪 费，使系统在资源利用方面更具优势。 关键字：容错系统，胚胎阵列，单细胞替换法，f p g a 基于单细胞替换的胚胎阵列容错系统a b s t r a c t a b s 仃a c t t h ef a u l t t o l e r a n ts y s t e mo fe m b r y o n i c a r r a y b a s e do nc e l l e l i m i n a t i o n b y q i a nz h a o 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 f t 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 fi n f o r m a t i o ns c i e n c ea n d t e c h n o l o g y o f t h e f u d a n u n i v e r s i t y i h ef a u l t 。t o l e r a n ts y s t e mo fe m b r y o n i ca r r a yi n t r o d u c e san e wa r c h i t e c t u r eo f f a u l t - t o l e r a n t s y s t e m ，b yc o m b i n i n gt h em e c h a n i s m st h a tt a k ep l a c ed u r i n gt h e e m b r y o n i cd e v e l o p m e n to fm u l t i c e l l u a ro r g a n i s m sw i 血e l e c t r o n i c s t h ee m b r y o n i c a r r a yu s u a l l yp e r f o r m sf a u l t t o l e r a n c eb yc o l u m n - e l i m i n a t i o n c o l u m n e l i m i n a t i o nc a r l b er e a l i z e de a s i l y , b u tm a yc a u s ew a s t eo fr e s o u r c e s ：i no r d e rt or e p l a c eo n ef a u l t y c e l l ，t h e r e m u s tb e a t l e s to n e s p a r e c o l u m n i n t h e a r r a y ；a f t e r t h e c o l u m n e l i m i n a t i o n ，t h en o r m a lc e l l s i nt h e f a u l t yc o l u m n c a n tb eu s e d a n y l o n g e r 0 t h e r w i s e ，i n o r d e rt o p e r f o r mf a u l t - t o l e r a n c e ，e a c h c e l lc o n t a i n st h e c o n f i g u r a t i o nd a t ao fa l lc e l l si nt h ea r r a y , w h i c hn e e dal a r g en u m b e ro fr e s o u r c e s t h e l a r g e rs y s t e mi s ，t h em o r er e s o u r e si sn e e d e d r e s e a r c hi su n f o l d e di nt w oa s p e c t s ：s t r a t e g yf o rf a u l t t o l e r a n c ea n ds t o r a g eo f c o n f i g u r a t i o nd a t a t h ea r c h i t e c t u r eo fc e l l s i si m p r o v e d a n dt h ep r a c t i c a b i l i t ya n d a d v a n t a g eo f t h ei m p r o v e de m b r y o n i ca r r a yi sv a l i d a t e do nf p g a f i r s t l y , c e l l - e l i m i n a t i o ns t r a t e g yf o rf a u l t - t o l e r a n c ei si n t r o d u c e d t h ep o s t u l a t eo f c e l l e l i m i n a t i o ni st h a t ：w h e naf a u l t yc e l li sf o u n d e d ，o n l yo n es p a r ec e l li sn e e d e dt o r e p l a c et h ef a u l t yo n e t l l i ss t r a t e g ya v o i d st h ed e f e c tt h a tf o r m a lc e i li se l i m i n a t e da sa f a u l t yc e l l a n db e c a u s eo n l yo n es p a r ec e l lr a t h e rt h a no n es p a r ec o l u m ni sn e e d e dt o r e p l a c eaf a u l t yc e l l ，t h es c a l eo ft h es t a n d b ya r r a yi nt h ef a u l t t o l e r a n ts y s t e mi sm u c h 2 基于单细胞替换的胚胎阵列容错系统 a b s t r a c t s m a l l e r , w h i c hc a nr e d u c et h ew a s t eo fr e s o u r c e s e c o n d l y , e a c hc e l lc o n t a i n st h ec o n f i g u r a t i o nd a t a so fa l lc e l l s i nt h ea r r a y , b u t o n l ys o m eo ft h e mm a yb eu s e dd u r i n gt h ep r o c e s so ff a u l t - t o l e r a n c e s ob yi m p r o v i n g t h ea r c h i t e c t u r eo f c e l l ，o n l yt h eu s f u lc o n f i g u r a t i o nd a t a sr a t h e rt h a na l ic o n f i g u r a t i o n d a t aa r es t o r e di ne a c hc e l l t h i si m p r o v e m e n ta l s oc a nr e d u c et h eu s a g eo fr e s o u r c e s i ti sv e r i f i e dt h a ts t r a t e g yf o rf a u l t t o l e r a n c ea n dt h ei m p r o v e d s t o r a g eo f c o n f i g u r a t i o nd a t ar e d u c et h ew a s t eo fr e s o u r c e si n am a n n e r , s ot h a tt h ee m b r y o n i c a r r a yh a sm o r ea d v a n t a g e si nt h eu s a g eo f r e s o u r c e s 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 ca r r a y , c e l l e l i m i n a t i o n ，f p g a 基于单细胞替换的胚胎阵列容错系统第一章窖错系统 第一章容错系统 1 1 本章概述 本章主要介绍容错系统的基本概念、常用的容错技术、及胚胎阵列容错系统。 本文主要讨论的是基于数字电路的容错系统。 1 2 容错系统 随着计算机与电子科技的不断发展，电子系统已经成为人类日常生活必不可 少的一部分，人们对于电子产品的需求和依赖程度也与日俱增。但是无论这些产 品制作多么精细，由于制造工艺的限制、使用寿命以及工作条件等影响，故障的 产生是不可避免的。早期的系统故障主要依靠技术人员凭借自己的经验和理论知 识，并借助一些常规工具来完成，但随着电子系统功能和规模的不断增加，基于 先验知识和设计规则的故障检测方法已逐渐难以应付，一旦系统遭到损坏，在庞 大的系统中人为的找寻错误和修正往往事倍功半。因此为保证系统具有高可靠、 长寿命和响应迅速，必须采用容错技术。 1 2 1 容错系统的基本概念，4 】 提高系统可靠性的技术途径归纳起来大体可分为两大类 第一类是提高元部件本身可靠性的技术，即排错技术。它通过对组成系统的 部件进行严格的筛选、对系统进行严格的测试、对系统进行屏蔽以减少外界的干 扰等方法来提高系统的可靠性。然而即使采用了排错技术，一个电子系统还是迟 早会发生故障的。因此在进行系统设计时我们就希望系统一旦发生故障时能自动 检测出故障并重新恢复正常运行。 第二类是用给定元部件构成高可靠性系统的技术，即容错技术。容错技术是 从系统结构方面来提高系统的可靠性，采用容错技术的系统即是容错系统。 容错即是指系统能够容忍故障，在有故障发生时能够自动检测出来并使系统 能够自动恢复正常运行。当出现某些指定的故障时，系统仍能执行规定的功能， 不会因这些故障而中止运行，并且执行结果也不包含由这些故障所引起的差错。 容错技术主要包括故障检测、故障屏蔽、系统重组三个方面的内容： 故障检测的目的是查看系统是否发生了故障。故障诊断的作用是给出故障定 位，在故障检测的基础上进一步回答系统中哪里发生了故障、发生了什么性质的 基于单细胞替换的胚胎阵列容错系统第一章容错系统 故障，即查找故障源和故障性质，实现故障的定位和定性。 故障屏蔽技术是通过增加冗余资源的方法来换取可靠性，使系统在出故障时 仍能维持正常功能。其特点是不改变系统的结构，即系统部件之间的逻辑关系相 互固定，因此又称静态冗余技术。单纯的故障屏蔽只能容忍故障，不能给出故障 警告且受静态冗余配置的限制。 系统重组是指在检测诊断出故障后，用后援备份模块替换掉失效模块，或者 切除失效模块，实现系统重新组合。重组的基础是结构的冗余和基于冗余结构的 故障检测与诊断。实际中，往往在检出故障后通过中断来触发重组。重组有两种 不同类型：后援备份重组和缓慢降级重组。后援备份重组是指系统配置一组平时 不工作的模块作为工作模块组中可能失效模块的备份，在故障发生后，通过故障 检测触发后备模块取代失效模块。缓慢降级重组是指当系统的工作模块出现故障 模块后，进行无替换的切换，每检出一个切除一个，从而使系统的功能和性能逐 步降级。 1 2 2 硬件冗余技术 5 ，6 ，7 l 对于容错系统来说，无论是故障检测、故障屏蔽或是系统重组，它们大都是 建立在资源冗余的基础上的。 硬件冗余是指通过附加硬件来实现故障检测及容错的技术。硬件冗余从实现 形式上可以分为静态冗余和动态冗余。 静态冗余是指冗余结构并不随故障情况变化的冗余形式，它利用逻辑重叠技 术有效地掩蔽硬件故障，从而防止故障造成差错，又称掩蔽冗余。基本机理是通 过多数表决来掩蔽发生的故障。 动态冗余主要体现在作为系统正常资源的冗余模块数随着检测到的故障数 多少而变化。动态冗余采用辅助系统作为主系统的备份，系统在正常状态下以标 准模块配置进行工作，并对主系统进行故障检测；一旦检测出故障，紧接着进行 重组和恢复，从而消除故障的影响，达到容错的目的。在静态冗余中，同一时刻 所有的复制要素均保持启动。如果一个复制发生故障，系统能够马上使用另一复 制，并继续正确的作业。而在动态冗余中，只有一个复制保持启动，而其余复制 则不启动。如果被启动的复制产生故障，先前未被启动的一个复制将被启动并接 管临界作业。 动态冗余的一种实现方法是采用由一个被启动模块和一个备用模块组成的 冗余对。另一方法则采用一簇模块，这些模块不必是其它模块的精确复制，可以 具有不同的特征、接口和容量。这簇复制需要采用失效接替策略，这样当主模块 基于单细胞替换的胚胎阵列容错系统第一章容错系统 出现故障时，就能确定如何对多个模块进行管理。 本文所讨论的容错结构属于硬件动态冗余。 1 3 胚胎阵列容错系统 1 3 1v l s i 阵列容错系统 8 , 9 a o 阵列结构的大规模集成电路系统具有结构规整、易于实现的特点。它在嵌入 式系统、高性能计算、以及信号及图像的并行处理等领域具有广泛的应用。随着 v l s i 技术的高度发展，阵列系统可以被集成到一个微小的芯片上。但是由于集 成密度的增大，处理阵列被损坏的可能性也随之增高。为了应对这一问题，引入 容错技术，以提高系统的可靠性。 容错的最基本方法就是利用冗余资源来屏蔽故障对系统的影响。过去冗余资 源的开销太大代价太高妨碍了容错硬件的广泛使用，而在v l s i 阵列系统中，因为 并不是所有单元在每个操作中都能被用到，所以可以把暂时不用的单元作为备用 资源，这样就解决了冗余资源的开销问题。 v l s i 阵列容错有三个阶段：首先，在v l s i 阵列的制造阶段，在有制造工艺 缺陷的情况下，需有某种形式的容错性才能获得效能价格合算的成品率，这称为 制造时的容错性。它的目的是要将成品率提高到满意的程度。第二，如果出错发 生在阵列安装到系统中以后，则给定足够的时间，阵列可以重新编译从而具有合 适的功能，这称为编译时的容错性。编译时的容错性重构方案除了测试和工艺方 法不同以外，其它的类似于软件支持的制造时的容错性设计。一个运行时的容错 技术可以应用于编译时的容错设计中，但反过来不行。第三，需有某种形式的容 错性能克服在处理器工作期间出现的错误，并允许系统继续执行其功能，这称为 运行时的容错性。 由于大多数实时应用要求有实时的容错性，因此，讨论的重点是运行时的容 错性。这里容错的主要目的是保证当大规模阵列处理器处在运行模式下时，能连 续正常工作。阵列容错的实现是将逻辑功能映射至一个物理可实现无错阵列中， 阵列中每一个单元执行一定的功能。当错误发生时，用一种机制重新配置物理阵 列，使原先的逻辑功能在余下的单元中重新工作。 目前v l s i 容错阵列一般是通过电路的重配置，重定连接线路来避开故障部 分。大多数的硬件重配置技术依靠复杂的算法来实现物理资源的重分配，并且基 本上使用一个中央处理器来执行诊断功能，置换算法和坐标分配。虽然这种结构 可以较有效率的完成差错诊断与恢复，但是有如下缺点：理论上系统如果有n 个 无错单元作为备用，那么就可以替换n 个出错单元，但是实际上由于种种限制， 基于单细胞替换的胚胎阵列容错系统 第一章容错系统 并不可能，所以冗余结构比较庞大，也为替换算法增加了难度；系统由中央处理 单元运行复杂算法来诊断以及重配置，由于其高度集中的特性，一旦中央处理器 出现崩溃，整个阵列也就失去了它的意义。 i u 1 3 2 胚胎阵列容错系统 为了提高系统可靠性，人们努力寻找新的容错系统设计方法。 二十世纪末，人们把目光投向了胚胎细胞。对于人工细胞系统的研究如细胞 自动机、神经网络等，已在人工生命科学领域取得了很大的进展，其目的就是理 解自然细胞系统中的各种行为。其中的一种行为就是容错能力。例如人体是一个 最复杂的系统，出错的情况也很多，但它的整体功能是非常可靠的，因为人体有 自诊断和自修复机制在不停地工作着。这些现象启发我们将这些机制的原理应用 到设计电子系统中去，从而得到一种设计容错系统的新方法胚胎阵列容错系 统。 1 2 , 1 3 , 1 4 】 1 3 2 1 胚胎细胞的进化过程 1 5 , 1 6 , 1 7 , 1 8 】 在生物学中，多细胞生物体大多由胚胎细胞发育而来，新的个体是由一个单 细胞分裂形成的。这个细胞通过有丝分裂的机制产生两个新的细胞，并且在分裂 过程中把其内部的d n a 信息复制给这些子细胞。子细胞继续重复有丝分裂同时给 它们的每个后代传递一个d n a 复本在此繁殖过程中细胞分化形成不同的组 织和器官。分化过程是通过翻译核内的d n a 信息完成的：每个细胞根据自己所在 位置翻译d n a 信息的不同部分来产生机体存活所需蛋白质。最后这些组织和器官 经过组合形成生物体。如人体大约是由6 0 万亿( 6 0 1 0 ”) 个细胞构成，每一个细 胞内的d n a 含有近2 0 亿条的信息特征。 因为构成生物体的每个细胞内都有一个d n a 的完全拷贝，所以这些细胞通过 翻译d n a 信息的不同部分可以实现生物体内的任何功能。这样当生物体中某一细 胞损坏时，临近的空闲细胞就会通过读取自身基因内的d n a 信息来替代这一受损 细胞进行工作，使整个机体恢复原先的功能，从而保持生物体的正常活动。 我们对这个过程进行研究并得到以下几点重要特征： 1 ) 多细胞结构：生物体是由大量细胞构成的。这些细胞具有相同的结构，并且每 个细胞都包含有整个生物体的d n a 信息，所以每个c e l l 都能替代其他任一c e l l 来工作。 2 ) 细胞变异：每个细胞在生物体中有各自不同的位置。虽然具有相同的结构跟 基于单细胞替换的胚胎阵列窖错系统 第一章容错系统 d n a 信息，但它们根据自己在生物体中位置的不同，选取d n a 信息中的不同部 分实现不同的功能。 3 ) 细胞分裂：开始时，只有原始的母细胞包禽有整个生物体的d n a 信息。细胞分 裂时，母细胞把这些d n a 信息复制给其子细胞，这些子细胞再把d n a 信息继续 往下复制这样，整个生物体所有的细胞都有了一份d n a 信息的拷贝。 1 3 2 2 胚胎阵列容错系统的提出【1 1 , 1 7 , 1 9 从生物体胚胎进化的这些特征中人们得到灵感并将其应用到容错阵列中，使 容错阵列产生了全新的结构基于胚胎细胞阵列的容错系统( 简称胚胎阵列) 。 图1 2 给出了胚胎阵列容错系统的 系统框图。由图中可以看到，胚胎阵 列是由许多单元构成的二维阵列，构 成这一阵列的每个单元我们称为仿生 细胞( 简称细胞) 。整个系统如生物体 一样是一个多细胞结构，各细胞具有 相同的结构和配置信息。它们在阵列 中对应不同的坐标位置，分别实现一 定的功能，相互协调组成系统。因为 一 每个细胞具有相同的结构以及相同的配置信息，所以当一个细胞发生错误之后我 们可以使用其他细胞来替代出错细胞进行工作，这就为实现容错提供了可能性。 具有容错功能的胚胎阵列包括了实现系统逻辑必需的细胞，以及系统出现错 误时用来进行替换的空闲细胞。当胚胎阵列中有细胞发生错误时，我们通过一定 的替换机制使阵列中的冗余细胞替代出错细胞进行工作，使系统能够保持正常运 行，从而实现系统的容错。通常采用的是列( 或行) 替换法。列替换法的容错思 想是：对于出错的细胞，放弃其所在的整列细胞，用与它邻近的列来替代并执行 该出错列的功能，以保证整个系统能够重新正常运行。 固空闲曰正常透明因损坏 基于单细胞替换的胚胎阵列容错系统 第一章容错系统 ( a ) 图1 3 列替换的执行 列替换法的执行过程如图1 3 所示。图1 3 ( a ) 是一个处于正常工作的胚胎阵 列，其中实现系统逻辑用到了9 个细胞，在图中用坐标标识；另外有7 个空闲细 胞作为备用，在图中用s 标识。图1 3 ( b ) 中，坐标为( 1 ，0 ) 的细胞发生了错误。因 此我们放弃整个第1 列，第l 列的所有细胞变成透明状态，如图1 3 ( c ) 所示，该 列左右两列的细胞直接通讯。同时出错列细胞不再进行坐标计算，从而在逻辑上 把出错列从阵列中剔除。其他各列的细胞重新计算坐标信息，并从存储单元选择 新的配置信息来执行，这样用第2 列代替第1 列工作，第3 列( 空闲列) 代替第 2 列工作，至此系统重新正常运行。 图1 4 是行替换法的执行过程，与列替换法的执行过程类似。对于同一个出错 细胞( 1 ，o ) ，在行替换法中我们放弃整个第0 行，用第1 行代替第0 行工作，第2 行代 替第1 行工作，第3 行( 空闲行) 代替第2 行工作，从而使系统再次正常运行。 2 0 , 2 1 1 图14 行替换的执行 从上文我们看出，由于胚胎阵列将错误诊断和替换功能分散于每个细胞中， 给阵列中的所有细胞都分配了重构机制，这样跟以前的容错阵列集中诊断并由一 个中央控制单元掌控所有的执行相比，避免了易于崩溃的缺点，简化了算法的实 现并增加了系统的可靠性。除此之外，这种结构应用于大规模集成电路中还有以 下优点： 结构高度整齐，简化了在硅片上的实现。 单个细胞的特定功能可以改变而不会影响到其他细胞。 一个细胞的损坏不会大规模影响整个系统的容错功能，并且能有效的进行恢 复。【2 2 1 3 2 3 胚胎阵列容错系统的发展 基于胚胎细胞阵列的容错系统的提出距今大约l o 年左右的时间。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 c a ，b ，c ) = a b + a c + b c 的简单逻辑功能( 2 ”。1 9 9 8 年， c e s a ro r t e g a 与a n d yt y r r e l 用相同结构完成了较复杂的二位加减法计数器和三 位分频器【2 。2 0 0 2 年，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 对细胞的结构作了更近一步的细化【l6 1 。2 0 0 3 年，r i c h a r d c a n h a m 与a n d y t y r r e l l 提出了简化配置信息的细胞来提高整个自愈系统的工作效率【2 5 】。 由于受许多客观条件的限制，胚胎阵列容错系统目前尚处于研究阶段，其实 用性并没有得到完全的发挥。随着技术的发展和人们的进一步研究，相信这方面 的应用会出现在人们的面前。 1 4 本文的主要工作及内容安排 本文对胚胎阵列的研究主要集中于细胞结构、系统硬件开销等方面的探讨， 并选用适当的f p g a 进行实例验证以探求可行性及不足。首先，胚胎阵列执行容 错时广泛采用了列替换法的替换策略，列替换法实现起来比较简单，但却造成很 大的资源浪费；文中尝试在容错时采用细胞替换法，对细胞结构加以改进，在一 定程度上节省了硬件资源。其次，胚胎阵列为实现容错，在每个细胞需中都存储 整个阵列的配置信息，将占用较多的资源，系统越大，配置信息单元占用的资源 越多；文中通过改变细胞配置信息的存储方法来减少硬件开销，使系统在资源的 利用方面更具优势。 具体的内容安排如下： 第二章：胚胎阵列容错系统的工作原理。 第三章：采用细胞替换法的胚胎阵列容错系统。 第四章：细胞替换法的验证及配置信息的改进。 第五章：总结目前的工作，并对未来的研究方向进行展望。 基于单细胞替换的胚胎阵列容错系统第二章胚胎阵列容错系统 第二章胚胎阵列容错系统 2 1 胚胎阵列容错的实现口0 0 1 】 容错系统就是在出现故障后能继续正常运行的系统，它的目的是通过剔除电 路中的故障而产生正确输出。由于当前的技术还无法实现在物理层次上剔除电路 的故障，因此，容错系统一般是通过电路的重配置，熏定连接线路来避开故障部 分实现的。胚胎阵列的容错也可归为此类。 2 1 1 正常工作的胚胎阵列 具有容错功能的胚胎阵列由两种细胞构成：实现系统逻辑必需的功能细胞， 系统出现错误时用来进行替换的空闲细胞。当系统出现错误时，产生了第三种细 胞：出错细胞。这三种细胞分别对应着三种不同的工作模式：功能细胞处于执行 模式，空闲细胞处于空闲模式，出错细胞处于透明模式( 即出错模式) 。每个细胞 的工作模式根据阵列中出错细胞的产生而变化。 在初始情况下，所有细胞都是正常的，没有细胞发生故障，所以阵列中只包 括功能细胞和空闲细胞。每个功能细胞根据左方细胞和下方细胞的坐标，生成一 个形如 的二维坐标，以此标识本细胞在阵列中的具体位置。其中x 代表该 功能细胞所在的列，y 代表其所在的行。如图2 1 是一个处于正常工作状态的3 3 胚胎阵列。阵列中实现系统逻辑用到了四个细胞，它们的坐标分别为 、 、 、 ；另外一些空闲细胞用来进行容错，在图中用字母s 标识。 图2 13 x 3 的胚胎阵列 跟多细胞生物体结构类似，胚胎阵列中的每个细胞具有相同的结构，能够通 过参数设定对自身结构进行配置，实现具体的逻辑功能。我们把这些参数称为配 置信息。每个功能细胞提供一定的功能，对应着一组配嚣信息，相互组合实现整 个系统的逻辑。为了能够实现容错，阵列中的所有细胞都要存储描述整个系统功 基于单细胞替换的胚胎阵列容错系统第一二章胚胎阵列容错系统 能的配置信息，然后由其中的功能细胞根据自身在阵列中的坐标位置读取相应的 配置信息实现不同的部分功能。这样，当有细胞发生错误后，出错细胞邻近的细 胞可以通过获得该出错细胞的配置信息来替代出错细胞执行其功能，从而实现对 出错细胞的替换，完成容错。 用来描述整个系统功能的配置信息组数跟阵列中功能细胞的个数是相同的。 图2 1 中，实现系统逻辑用到了四个功能细胞，每个功能细胞对应一组配置信息， 所以整个系统包括了四组配置信息，分别用a 、1 3 、c 、d 表示( 配置信息实为二进 制位串，为简单起见，此处用不同字母表示不同位串) 。因此阵列中细胞的存储 状况均如图2 2 ( a ) 所示。每个功能细胞根据自身的坐标信息，得到一个指针信号 p o i n t e r ： p o i n t e r = 2 + y + x ： 然后通过指针信号选择相应的配置信息，如图2 2 ( b ) 所示。其中深色部分为各细 胞根据自身坐标选中的一组配置信息。如此四个细胞分别执行不同的功能，相互 结合实现设定逻辑。 a 细胞中的配置b 阵列中的配置 图2 2 胚胎阵列中的配置信息 2 1 2 故障的检测 由于本文的着眼点在于胚胎阵列的资源利用问题以及当胚胎阵列发生错误 之后的替换策略问题，所以对故障检测不做深入讨论。本文直接使用控制信号 o k 来表示细胞的出错信息。当o k = i 时，细胞处于正常工作状态；当o k = 0 时， 细胞处于出错状态。 另外还需说明的是，由于此结构尚处于研究阶段，因此o k 所表示的出错信 息仅限于仿生细胞中的功能模块，不代表i o 模块、地址模块等的错误，这也是 本结构目前比较突出的问题，即提高了实时性和高效性的同时，增加了较多的冗 余资源，相对来说故障覆盖率不高。 基于单细胞替换的胚胎阵列容错系统 第二章胚胎阵列容错系统 2 1 3 出错后的胚胎阵列 当系统检测到有细胞发生错误时，通常采用列( 或行) 替换法来实现容错。 列替换法的容错思想是：对于出错的细胞，放弃其所在的整个列，用与它邻近的 列来替代并执行该出错列的功能，以保证整个系统能够重新正常运行。 下面仍然以图2 1 所示的3 x 3 胚胎阵列为例说明列替换法的执行过程。 假设出错的是坐标为 的细胞，即此细胞的o k 信号变为0 。检测到变低 的o k 信号后，细胞 从功能细胞转为出错细胞，相应地，工作模式从执行模 式转为透明模式。同时出错细胞发出信号给位于同一列的其他细胞，通知它们准 备进行替换。其他细胞收到替换信号后也转为透明模式。 在透明模式下，细胞不再进行坐标计算，直接把左方细胞坐标传送给右方细 胞，从而使出错列左右两列的细胞直接进行通讯。其他各列的细胞重新获得在阵 列中的坐标位置，并根据新的坐标位置选择对应的一组配置信息来执行，其过程 如图2 3 所示。从图中看出，替换过程相当于把系统中出错列以右的有用细胞整 个往右平移了一列。 图2 _ 3出错后阵列的坐标分配 由于阵列中细胞的坐标进行了重新分配，致使各个细胞选择新的配置信息来 执行，如图2 4 所示。 图2 4 出错后阵列中的配置 基于单细胞替换的胚胎阵列窖错系统 第= 章胚胎阵列容错系统 从图2 t 3 和图2 4 中可以看到虽然原坐标为 的细胞遭到破坏，但当第1 列转为透明状态后，第2 列的空闲细胞取代了第1 列细胞并执行它的功能，而且细 胞间的连接也由原来的第0 、1 列通讯转为第0 、2 列通讯。这样虽然实现系统逻辑 的功能细胞在阵列中的位置不同了，但它们之间的相互位置并没有改变，仍然可 以通过组合实现先前的逻辑功能。从而成功地实现在逻辑上剔除包含出错细胞的 第1 列，使系统重新正常运行。 类似的替换策略还有行替换法。行替换本质上与列替换是一致的，在此不作 讨论。列( 或行) 替换法实现起来相对简单，因此在胚胎阵列容错系统中得到了 广泛的应用。 2 2 胚胎细胞的内部结构 胚胎阵列是由多个可编程细胞构成的阵列。同多细胞生物体一样，这些仿生 细胞的结构相同，这样当有细胞出错时其他细胞才能够替代出错细胞进行工作。 这是胚胎阵列实现容错的基本条件。因此为了对一个数字系统应用胚胎阵列，我 们首先需要寻找一种方法把系统化分为一定数量具有相同结构的单元，这样每个 单元可以跟胚胎阵列中的一个细胞对应，从而完成系统到胚胎阵列的映射。 2 2 1 二进制判决图b d d 算法 2 6 , 2 7 2 2 1 1b d d 简介 二元判决图( b d d ，b i n a r yd e c i s i o nd i a g r a m ) 是计算机科学和数字系统设 计的基础。在解决众多的数字系统设计、重组优化、数学逻辑等等问题中，人们 发现其中许多问题可以简化为布尔函数进行处理，结合图论的知识，可以为这些 复杂的布尔函数建立一种图的表示形式。因为这种图中的变量取值只有0 $ n 1 两 种，所以也把这种图称为- 5 0 决图。 b d d 最早是1 9 5 9 年由美国c y l e e 提出的描述开关电路的方法。1 9 7 8 年 s h e l d o mb a k e r s 对b d d 进行了改进，使之成为一种用来定义、分析、测试和实 现大型数字函数的方法，接近现在的表述形式。1 9 8 6 年r a n d a le b r y a n t 又对b d d 做了进一步的改进，通过指定逻辑变量的次序，将逻辑函数用b d d 予以表示，从 而形成了现在的b d d 方法。b d d 能宜观地表示布尔函数，并且能反映数字电路 逻辑描述的细节，因此越来越受到人们的重视。 2 2 1 2b d d 算法 基于单细胞替换的胚胎阵列容错系统第二章胚胎阵列容错系统 b d d 是一个具有有限个节点的非循环有向图，它源于香侬定理，是一种二叉 树的图形表示。每一个b d d 只有一个根节点，同时还有另外两类节点：终节点和 非终节点。终节点没有输出边，且只可用“0 ”或“1 ”两个值来表示：而每一个 非终节点用一个原始输入变量表示，都有“高( 1 ) ”，“低( o ) ”两条输出边，“高” 边表示当这个节点的变量取“1 ”时函数的分支，“低”边表示当这个节点的变 量取“0 ”时函数的分支。非终节点由一个含有变量的圆圈来表示，终节点由含 有0 或1 值的方框来表示。“低( o ) ”边用虚直线来表示，“高( 1 ) ”边用实线来表 示，若无特殊标明，本文中b d d 的表示方法都遵循这个规定。 对一个变量分别为，x ：_ 的布尔函数，( 葺，叠屯) ，若把它的某个变量一 用b ( b o ，1 ) ) 来代替，得到的结果称为厂的约束，也称为余因子，可表示为f 。 有： ，。，。( x 1 恐x n ) = j ( x ，+ b ，葺x n ) 可以看出，。：。也是一个布尔函数。同理，布尔函数中的变量一由函数g 代 替时，称为布尔函数和g 的合并，记为厂。：。，也就是： ，。( x 1x ：矗) = f ( x l 一，g ( x ，而x o ) ，x 。_ ) 显然函数的合并仍然是布尔函数。 b d d 可以将任何的布尔函数表示为二叉树的形式，并进行化简等处理。对变 量分别为，屯矗的布尔函数，( _ ，x 2 _ ) ，我们可以在它的每一个变量上展开 成一个有向无环图： 厂= 五正，；o + 一正：1 ( 1 ) 其中墨代表函数的任一变量；上，：。是变量t = 0 时函数的值；：，是变量薯= 1 时 函数的值。以函数0 。，x ：，屯) = 而屯+ 工：x 3 为例，在一上展开可以表示为： 五：o = x 2 x 3 六；l2 x 3 + x 2 x 3 f = x , l _ 0 + 一六，t = x 】( x 2 x 3 ) + x i ( x 3 + 戈2 而) 同理，函数也可以在_ 和葺上分别展开： ，= 石2 z = o + t 正 _ l = x 2 ( x l x 3 ) + x 2 ( x 1 x 3 + 屯) f = x 3 厶：o + x 3 厶，i = x 3 ( o ) + 恐( 五+ _ = c 2 ) 下面仍然以布尔函数，g ，x ：，玛) = x l x 3 + x ：屯为例，说明如何得到一个函数的 b d d 。 1 ) 首先把原始函数，在五上展开，令z = 厶_ 0 ，五= 工则，在上可展 开为： f ：- l + x 。f 2 茎苎塑望萱垫塑壁堕堕型窒堕墨竺 苎三童垦堕堕型窒堕墨竺 一= t t 五= x 3 + 鼍 把变量五表示成二叉树节点的形式，如图2 5 ( a ) 所示。它表示函数厂在变量五= 0 时 的值为石，在五= 1 时的值为正。 ( a ) ( b )( c ) 图2 5二叉树分解 2 ) 然后把函数；在上展开。在z 的条件下，当x 2 分别取o 和l 时，令 石= z 。，一= _ 一。，有： = x 2 石+ x 2 六 五= 0 f 4 = 恐 图2 5 ( b ) 中的二叉树结构是在第一步的基础上增加了一个置节点。此节点的输入 为z ，虚线输出为石，实线输出为工。 3 ) 同第二步，把函数z 和五分别在弓上展开。对于函数石，无论乇是。还是 1 其结果都是o ：对于函数工，屯分别取。和l 时，其结果也分别是。和1 。图2 5 ( c ) 给出了增加两个矗节点后的二叉树形式。 4 ) 对函数正重复步骤2 3 ，最后得到函数完整的b d d ，如图2 6 所示。它 是对这个布尔函数反复运用式( 1 ) 得到的。 基于单细胞替换的吒胎阵列容错系统 第二章胚胎阵列容错系统 根节点 图2 6b d d 结构 图2 6 中，五是这个b d d 的根节点，t 、x 3 是这个b d d 的非终节点。每一个 非终节点都有两个输出边，虚线输出边是这个节点的变量取0 时函数的分支， 实线输出边是这个节点的变量取“i ”时函数的分支。 图2 6 的b d d 的规模还可以在不改变其所表示的函数的前提下迸行约简，消 去冗余节点、重复节点以及同构节点。 2 2 1 3b d d 约简 当沿着某个b d d 的根节点向下搜索时，若每个节点在每条分支上出现的次数 最多一次且变量出现的顺序相同，则把这个b d d 称作编序b d d ( o b d d ，o r d e r e d b d d ) 。换句话说，o b d d 是在b d d 的基础上对函数的变量进行编序产生的b d d ， 也即是选定了变量的先后顺序的b d d 。 当一个0 b d d 中不包含同构子图且节点的两条分支不指向同一个节点时，称 这个o b d d 为约简的编序b d d ( r o b d d ，r e d u c e da n do r d e r e db d d ) 。 下面通过图2 6 中的例子来说明如何约简一个b d d 。由于图2 6 是选取变量顺 序为五，而，毛的b d d ，它满足o b d d 的定义，所以就在这个基础上把它约简为 r o b d d 。 一个0 b d d 可以通过以下三条规则转化为r o b d d ，设o b d d 为g = ： 1 ) 合并终节点中相同的节点，使之最多只有两个终节点，且它们的取值只可能 为0 或1 。以图2 6 中的b d d 为例，合并相同的终节点，也就是合并0 、1 节点，得 到的结果如图2 7 0 ) 所示。 2 ) 去除o b d d 中的同构节点。对非终节点u 和v ，如果它们不仅变量相同，而且 其虚线和实线所指向的下一级节点也都完全相同，则称 和v 是同构节点。去除 譬田 舻 终、 基于单细胞替换的胚胎阵列容错系统 第二章胚胎阵列容错系统 同构节点的方法是删除其中一个节点，并将删除节点的所有入边指向保留节点。 对于图2 7 ( a ) ，其中有两个以x 3 为根节点的同构节点。把它们合并为一个，得到 的结果如图2 7 ( b ) 所示。 3 ) 删除图中的无效节点。对非终节点v ，如果其“高( 1 ) ”、“低( o ) ”边相同， 即该节点的两个输出边都指向同一个节点，则删除节点v ，并把它的所有入边指 向“低( o ) ”边。图2 7 ( b ) 中的节点墨和都是无效节点，删除它们，得到的图2 7 ( c ) 便是一个r o b d d 。 烈 争叫 j 7 澎 选二， uu ( a )( b ) 图2 7b d d 化简 要注意的是，函数的b d d 并不是唯一的。 然后是变量x 2 ，x 3 。若是改变变量次序，那么得 不相同a 在图2 8 中，对同一个函数，( x 。，z ：，屯) 后是变量x 2 、x l ，则最后得到的b d d 结构与图2 q r 爿7 a 1 二弋 qq 、 。 曰臼田臼田口口臼 ( a ) ( c ) 在图2 7 中，先分解的是变量葺， 到的b d d 很可能与图2 3 中的b d d = x 1 均+ x 2 ，先分解变量玛，然 6 , 1 图2 7 中的b d d 结构就不一样。 ( b )( c ) 图2 8 第二种b d d 结构 2 2 2b d d 与胚胎阵列的结合 基于单细胞替换的胚胎阵列容错系统第二章胚胎阵列容错系统 由上文我们得知，b d d 可以将任何的布尔函数表示为二叉树的形式，并进行 约简处理。而一个二叉树可以通过一系列2 1 选择器互连来实现。图2 9 ( a ) 给出了 一个二叉树节点与一个2 1 选择器的对应关系。在2 1 选择器中，当变量s 为0 时， 输出o 为m 0 ，即节点s 的虚线端；当变量s 为l 时，输出o 为m 1 ，即节点s 的实线 端。用这种方法可将图2 7 ( c ) 中的b d d 转化为由2 1 选择器实现的电路，如图2 9 ( b ) 所示。这样我们就把布尔函数，( 五，x ，x 3 ) = x i x ，+ x 2 x 3 分解成了由三个2 1 选择器 相互连接组成的电路。 m ( a ) 图2 9 二叉树与2 - 1 选择器的转换 因此，我们通过运用b d d 算法将电路的布尔函数分解成一系列2 1 选择器互 连的形式，再把这些2 1 选择器映射到胚胎阵列的细胞中的方法来实现胚胎阵列。 2 2 3 胚胎细胞内部结构 2 1 , 1 7 0 8 , 2 9 1 2 2 3 1 基本结构 由上文可以得知，胚胎阵列中的每个细胞对应着一个2 1 多路选择器，因此 每个仿生细胞实现的主要逻辑功能是一个 2 - 1 多路选择器。同时为了方便实现