内进化容错模型设计及其可靠性分析

　　摘要：仿照自然界的碳基生物进化过程，在FPGA内部实现了可控的硅基进化。针对电子系统常见的SA故障，提出了基于演化硬件技术的内进化容错模型，通过在FPGA内部装载Microblaze CPU和构建可重配置阵列，实现了演化硬件的片内进化。利用该模型进行了故障容错实验，检验了其有效的故障容错能力，证明该容错方法能够有效提高数字电路的可靠性。

　　0 引言

　　进化硬件（Evolution Hardware,EHW）指的是仿照自然界中以碳为基的生物进化过程，在现有的FPGA芯片基础上实现可控的“硅基进化”.进化硬件实际上是一种特殊硬件，它可以像生物一样具有自适应、自组织、自修复特性，从而可以根据使用环境的变化而改变自身的结构以适应其生存环境。进化硬件除了能够生成具有新功能的电路以外，还可用于减少故障的发生，获得容错的功能，从而提高电路可靠性。

　　1 内进化容错模型

　　通过在FPGA内部构建运算进化算法的MicroblazeCPU,把决定电路结构和功能的二进制配置位串作为染色体，通过对实际硬件的配置和测试来加速适应度评估过程。将其进化结果直接用于可重配置电路，以便获得具备预期功能的实际硬件。内进化设计的方式更充分地利用了可编程器件的芯片资源和可重构特性。由于将进化硬件特有的快速进化和硬件可重配置结构与FPGA内部算法运行和的内进化模式相结合，即可获得具有实时、自适应、容错能力的理想硬件特性。如图1所示。

　　

　　从图1可以发现在FPGA 内部主要分为两个区域：

　　Microblaze CPU和可重配置阵列。图中的MicroblazeCPU 是基于XILINX 公司FPGA 的微处理器IP 核，和其他外设IP 核一起，可以完成可编程系统芯片（SoPC）的设计。Microblaze是一个高度灵活可以配置的软核，可以根据设计的需要，对Microblaze 进行裁减，用少的资源完成设计的需要。可重配置阵列由可编程单元组成，其规模根据电路的复杂程度和功能需求设定。其中基本单元是可编程单元（Programmable Element,PE），由配置寄存器、多路选择器和基本逻辑运算单元组成。

　　在系统工作时，Microblaze CPU通过数据控制通道配置可重配置阵列，配置完成后可重配置阵列单独工作。

　　如果嵌入该模型的FPGA 工作环境或功能要求发生了变化，只需重新启动上述进化过程，针对新的设计目标和内、外部条件重新进行搜索，便可获得新的配置位串和预期电路功能，即实现硬件自适应。同样，如果硬件电路本身出现了局部故障但存在预留的资源冗余，重新执行上述进化过程后也有望避开故障区域，重新获得预期的电路功能。

　　2 具体实现

　　2.1 算法流程

　　由于遗传算法模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。因此将遗传算法作为演化算法。在求解问题时，问题的每个可能的解都被编码成一个“染色体”,即个体，若干个个体构成了群体。在遗传算法开始时，随机地产生初始个体群，根据预定的目标函数对每个个体进行评价，给出了一个适应度值。

　　基于此适应度值，选择个体用来复制下一代。选择操作体现了“适者生存”原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。演化算法的基本流程如图2所示。

　　

　　2.2 遗传算子设计

　　（1）转盘赌选择，即个体的选择概率pi 等于其适应度值在所有个体的适应度值之和中占的比例。首先先计算个体的相对适应值记为pi,然后根据选择概率{pi ,i=1,2,…，N}把一个圆盘分成N 份，其中第i 扇形的中心角为2πpi.在进行选择时，先生成一个[0,1]内的随机数r,若p0+p1+…+pi-1<r≤pi+pi+1+…+pn,可以假想转动一下圆盘，若某参照点落入到第i 个扇形内，则选择个体i.

　　（2）交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。

　　交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。本设计采取单点式交叉方法，即随机的在两个父串上选择一个杂交点，然后交换这两个串的对应的子串。

　　（3）变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。

　　2.3 适应度评估

　　内部演化将遗传算法每一代产生的每一条染色体都实际到器件中，并对每一种电路结构的输出直接进行评判。内部演化评估速度快，并可利用器件的实际特性实现系统动态重构。适应度的计算方式为给一个输入矩阵，读取输出矩阵，如果和希望的标准矩阵一致则“适应度”加1.其数学表达式为：

　　

　　式中：X为该个体对应的输出矩阵；M为标准输出矩阵。

　　3 故障容错实验与冗余可靠性分析

　　3.1 实验条件

　　采用Schwefel 的（1+λ）-ES 演化策略[7].程序参数为：适应度值12,种群规模10,变异率0.02,交叉率0.3,演化代数100 000.根据列PE 单元的损伤数目设计7种不同的故障模式，每种故障采用100个不同的随机数种子。应用数理统计的方法，每种故障模式采用100个样本。在规模为8×4个PE单元的可重配置阵列中，进行了列PE单元逻辑门损坏和容错实验。模拟文献[6]中提到数字电路中常见的SA故障，SA故障指的是无论对于何种输入，节点的输出固定为某一逻辑值。

　　3.2 实验结论

　　记PEi为列PE损伤数为i（i<7）的故障模式，试验结果如表1所示。

　　

　　针对SA-0错误，通过Microblaze CPU对可重配置阵列进行演化在十万代内均能找到正确的解（PEi（i<6）），成功证明了该算法良好的容错特性，在电路设计方面有效改善了传统电路设计中设计终身定型的弊端，使电路在遇到故障时可以避开故障单元，实现功能自修复。

　　3.3 冗余可靠性分析

　　图3 所示为演化电机的3 输入2 输出换向电路，分别计算两种不同电路的可靠性。

　　

　　由于设计只使用了基本的逻辑单元如与门、或门、与非门和或非门，得到演化方法设计电路可靠性概率pe为：

　　

　　pe 和pn 概率如图4所示，虚线表示传统电路设计方法生成的电路的故障率，实线表示冗余电路利用演化算法生成电路的故障率。可以看出，当p∈（0,0.5）时pe>pn,即动态可重构冗余电路具有更高的可靠性。

　　

　　4 结语

　　本文通过在FPGA内部集成Microblaze CPU和可重配置阵列的方式，实现了基于内进化方式容错模型。针对SA 故障进行了容错实验，证明该模型具有良好的故障容错能力，为获得具有实时、自适应、容错能力的理想硬件特性提供了新的技术途径。建立了电路可靠性的概率分析模型，并且针对本试验中的具体电路分析了冗余方法结合演化算法设计电路和传统方法设计电路的出错概率，证明了前者具有更高的可靠性。（作者：娄建安，李阳，余建华）