基于演化硬件的实时容错系统设计方法

摘要

本发明公开了一种基于演化硬件的实时容错系统设计方法，属于演化硬件领域。该方法从电路编码和系统容错机制进行分析，并在FPGA平台上实现了一套实时容错系统。采用动态自适应CGP编码方法，挖掘编码矩阵的潜能，减少演化耗时，提高演化成功率；采用多种机制保证容错系统的实时性和容错性。以系统故障容错时间为约束条件，保证系统的实时性；利用静态故障配置库加速对故障的修复过程；当静态配置库溢出时，采用补偿修复模式重构系统，提高系统长期运行能力；采用虚拟可重构技术在FPGA平台上构建了一套实时容错系统原型，验证该设计方法的可行性和有效性。该方法兼顾系统的容错性和实时性，充分发挥演化硬件在容错系统设计领域的优势。

说明书

技术领域

本发明属于演化硬件领域，涉及一种基于演化硬件的实时容错系统设计方法。

背景技术

随着信息时代的来临，各类电子产品层出不穷，人们的工作和生活方式正在发生巨大改变。日益丰富的电子产品在给人们生活带来便捷的同时，也对电子系统的设计水平提出了更高的要求。电子系统的功能不断增强，规模不断扩大，电子系统设计的复杂度呈指数增长，仅仅依靠经验将无法设计出符合需求的电子系统。对于一些工作在特殊环境中的电子设备，如太空飞船，深海探测器等，对系统的可靠性要求极其严格，一旦系统出现故障，将会对这些设备造成致命的损害，带来巨大的经济损失。由于传统的设计方法是静态的，系统结构一旦被设计好就很难再被更改，仅仅依靠设计人员的经验，无法预测系统会遭遇何种故障，也无法进行提前预防，这就给系统的安全性和可靠性带来了极大的隐患。为了能够突破人工设计电路的局限性，增强系统对抗外部环境变化的适应能力，提高系统可靠性，迫切需要一种能够提高系统容错能力的设计方法。

发明内容

本发明要解决的技术问题是提供一种基于演化硬件的实时容错系统设计方法，结合演化硬件的自组织，自适应和自修复的特性，提出了一种动态自适应笛卡尔遗传编码(Cartesian Genetic Programming，CGP)方法和实时容错机制，并在FPGA平台上实现了一套实时容错系统原型，其总体架构如图1所示。其中，演化算法采用C代码编写，运行在FPGA平台内嵌的Microblaze处理器软核上；其他模块则采用Verilog代码编写，运行在FPGA平台上。

一种基于演化硬件的实时容错系统设计方法，步骤如下：

(1)动态自适应CGP编码方法

传统的CGP编码随机选择一个固定节点作为最终输出节点，动态自适应CGP编码方法输出节点不固定，采用一种动态随机采样模型从CGP编码矩阵中选择不同节点作为输出节点，分别计算CGP编码矩阵的适应度值，并选择适应度值最大的矩阵作为最优解；节点的采样概率随着种群整体适应度变化情况动态调整，当前种群的适应度分布情况采用以下公式计算：

$f_d\left(t\right)=\frac{\overline{f\left(t\right)}}{f_{max}\left(t\right)-f_{\min }\left(t\right)}---\left(1\right)$

其中，f_d(t)表示种群中个体适应度分布或多样性；表示种群中个体的平均适应度值；f_max(t)表示种群中个体的最大适应度值；f_min(t)表示种群中个体的最小适应度值；随着迭代次数的增加，个体之间的适应度差值越来越小，平均适应度值增加，f_d(t)的值也逐渐变大；

采样概率分为两部分，在演化初期，种群适应度值较低，采用固定的较高采样概率加块收敛速度；当种群平均适应度值或迭代次数达到预定的阈值时，根据种群平均适应度值动态调整采样概率；演化过程中采样概率的计算公式为：

$P_s=\left(\begin{array}{c}{P}_{s0},t<t_0\\ P_{s0}{e}^{\frac{-\partial (t-t_0)}{t_{\max }}}/f_d\left(t\right),t\ge t_0\end{array}\right)---\left(2\right)$

其中，P_s0是设定的初始采样概率，初始采样概率的设定综合考虑种群规模和染色体长度；如果初始采样概率设为1，则此时遍历所有的节点，并计算适应度值；如果初始采样概率设置过小，则随机选择，初始采样概率不低于0.5；t₀是采样概率调整的临界迭代次数，t₀的取值为0.3t_max；是自定义的参数调节因子，设定为2，t_max是演化算法的最大迭代次数；

(2)基于演化硬件的实时容错机制

容错系统本质上是一种实时系统，实时性是容错系统的一个重要约束条件；基于演化硬件的实时容错机制，以系统容错时间为约束条件，利用静态配置库加速修复过程，兼顾容错系统的实时性和容错性；整个实时容错机制主要包括以下几个方面：

①计算演化算法最大迭代次数

将系统可容忍的故障时间定义为修复期限T_max；T_max通过故障分析树技术得到；为了保证系统在修复期限内修复系统故障，在演化过程中将修复期限作为演化算法的约束条件；首选通过公式(3)计算出演化算法迭代一次需要的时间T_g；

T_g＝λ(T_cfg+T_fit)+T_ea(3)

其中，T_cfg是演化平台的配置时间，T_fit是适应度评估时间，T_ea是演化算法的执行时间，λ是每次迭代过程中产生的子代个体的数量；则根据公式(4)得到最大的迭代次数；

$G_{max}=\frac{T_{max}}{T_g}---\left(4\right)$

②运行时故障检测

在系统运行阶段，当系统出现故障时，需要在最短的时间内检测到错误；故障最终导致系统输出错误，比较系统的实际输出和期望输出，判断系统是否有故障发生；故障检测的结果用公式(5)表示

$R=O_{real}\oplus O_{\exp }---\left(5\right)$

其中R表示实际输出和期望输出的异或，如果期望输出和实际输出一致，则R为0，否则R不为零，通过检测R的值，得到检测系统是否出错；

③利用静态配置库修复故障

静态配置库主要用来加速故障的修复时间；在系统设计阶段，通过FTA技术挖掘系统潜在的故障，并将这些故障的补偿电路存储在静态配置库中；在系统运行时，如果发生故障，则以向量(I_n,O_real)为索引到静态配置库中查找对应的补偿电路；

如果查找对应的补偿电路，则说明发生了已知故障，直接从配置库中查找对应的补偿电路，完成对系统故障的修复；

如果没有查到对应的修复电路，则说明发生了未知故障，启动演化算法来演化补偿电路；

在演化未知故障的补偿电路时，采用一种基于相似性的演化算法来加速演化过程；首先，采用海明距离来计算期望补偿输出和配置库中已有电路的补偿输出的相似性，表示为Dis(R,R’)，其中R是期望补偿电路的输出，R’是配置库中已有电路的补偿输出；如果则用R’对应的补偿电路来产生演化算法的初始种群，并演化出R；反之，则根据R’对应的补偿电路来演化出然后在补偿输出上加上反相器；

静态配置库的大小取决于系统规模和硬件资源，静态配置库的空间越大占用的存储资源越多，查库的时间递增；配置库中的修复电路和故障索引是一对多的关系，即一个修复电路对应多个故障索引；

④利用演化与补偿的方式重构系统

每修复一个故障，将对应的补偿电路存储在配置库中，但是配置库的存储空间有限，不能存储所有的补偿电路；当配置库内存溢出时，配置库将无法存储新的补偿电路，而且随着系统长时间的运行，出现更多的未知故障，配置库的作用逐渐降低，最终影响系统的容错能力；为了提高系统长期运行的可靠性，当配置库内存溢出时，将采用基于补偿修复技术重构系统；

在重构目标系统时，采用基于补偿修复技术的演化方式；演化过程中如果检测到停滞效应则停止演化，假设当前迭代次数为G_s,如果G_s,≥G_max,则表明不能在规定的迭代次数内演化出目标系统；如果G_s<G_max，则启动修复进程对已经演化出的部分正确系统进行修正，修复进程必须在G_max-G_s次迭代次数内完成。

本发明的有益效果：(1)通过采用动态自适应CGP编码方式能够减少演化耗时，提高演化成功率；(2)以系统容错时间为约束条件，结合配置库和补偿容错模式，能够提高系统的容错性和实时性；(3)在FPGA平台上构建虚拟可重构框架，并在该框架上实现一套实时容错系统，为容错系统的设计提供一种可行的参考模型。

附图说明

图1是系统的整体结构框图。

图2是CGP编码矩阵示例图。

图3是静态配置库工作原理图。

具体实施方式

以下结合附图和技术方案，进一步说明本发明的具体实施方式。

一种基于演化硬件的实时容错系统设计方法，步骤如下：

动态自适应CGP编码方法和实时容错机制的主要原理如下：

(1)动态自适应CGP编码方法

CGP是演化硬件领域是最为常用的编码方式，其原理如图2所示。传统的CGP编码随机选择一个固定节点作为最终输出节点，动态自适应CGP编码方法输出节点不固定，采用一种动态随机采样模型从CGP编码矩阵中选择不同节点作为输出节点，分别计算CGP编码矩阵的适应度值，并选择适应度值最大的矩阵作为最优解。节点的采样概率随着种群整体适应度变化情况动态调整，当前种群的适应度分布情况可以采用以下公式计算：

$f_d\left(t\right)=\frac{\overline{f\left(t\right)}}{f_{max}\left(t\right)-f_{\min }\left(t\right)}---\left(1\right)$

其中，f_d(t)表示种群中个体适应度分布或多样性；表示种群中个体的平均适应度值；f_max(t)表示种群中个体的最大适应度值；f_min(t)是最小适应度值。随着迭代次数的增加，个体之间的适应度差值越来越小，平均适应度增加，f_d(t)的值也逐渐变大。采样概率主要分为两部分，在演化初期，种群适应度较低，采用固定的较高采样概率加块收敛速度；当种群平均适应度或迭代次数达到预定的阈值时，根据种群平均适应度值动态调整采样概率。演化过程中采样概率的计算公式为：

$P_s=\left(\begin{array}{c}{P}_{s0},t<t_0\\ P_{s0}{e}^{\frac{-\partial (t-t_0)}{t_{\max }}}/f_d\left(t\right),t\ge t_0\end{array}\right)---\left(2\right)$

其中，P_s0是设定的初始采样概率，初始采样概率值的设定需要综合考虑种群规模和染色体长度。如果初始采样概率设为1，则此时需要遍历所有的节点计算适应度值；如果初始采样概率设置过小，则变成了随机选择，可能会影响迭代次数。因此，初始采样概率一般不低于0.5。t₀是采样概率调整的临界迭代次数，t₀的取值不能太大，取值过大会影响算法的加速效果，一般取0.3t_max。是自定义的参数调节因子，一般设定为2，t_max是演化算法的最大迭代次数。在演化前期，种群整体适应度较低，采样概率较大，有利于加快演化算法收敛速度；在演化后期，种群整体较优，采样概率变小，减少对电路结构的调整有利于优良基因的积累，提高演化算法的成功率。

(2)基于演化硬件的实时容错机制

传统的容错系统设计方法主要考虑系统的容错能力，忽略了容错系统的实时性，而容错系统本质上是一种实时系统，实时性是容错系统的一个重要约束条件。基于演化硬件的实时容错机制，以系统容错时间为约束条件，利用静态配置库加速修复过程，能够兼顾容错系统的实时性和容错性。整个实时容错机制主要包括以下几个方面：

①计算演化算法最大迭代次数

将系统可容忍的故障时间定义为修复期限,定义为T_max。T_max可以通过故障分析树(Fault>g。

T_g＝λ(T_cfg+T_fit)+T_ea(3)

其中，T_cfg是演化平台的配置时间，T_fit是适应度评估时间，T_ea是演化算法的执行时间，λ是每次迭代过程中产生的子代个体的数量。则根据公式(4)可以得到最大的迭代次数。

$G_{max}=\frac{T_{max}}{T_g}---\left(4\right)$

②运行时故障检测

在系统运行阶段，当系统出现故障时，需要能够在最短的时间内检测到错误。故障最终会导致系统输出错误，只需要比较系统的实际输出和期望输出就可以检测是否有故障发生。故障检测的结果可以用公式(5)表示。

$R=O_{real}\oplus O_{\exp }---\left(5\right)$

其中R表示实际输出和期望输出的异或，如果期望输出和实际输出一致，则R为0，否则R不为零，通过检测R的值就可以检测系统是否出错。

③利用静态配置库修复故障

静态配置库主要用来加速故障的修复时间。在系统设计阶段，可以通过FTA技术挖掘系统潜在的故障，并将这些故障的补偿电路存储在静态配置库中。在系统运行时，如果发生故障，则以向量(I_n,O_real)为索引到静态配置库中查找对应的补偿电路。

如果查找对应的补偿电路，则说明发生了已知故障，直接从配置库中查找对应的补偿电路，完成对系统故障的修复。

如果没有查到对应的修复电路，则说明发生了未知故障，需要启动演化算法来演化补偿电路。在演化未知故障的补偿电路时，采用一种基于相似性的演化算法来加速演化过程。首先，采用海明距离来计算期望补偿输出和配置库中已有电路的补偿输出的相似性，表示为Dis(R,R’)，其中R是期望补偿电路的输出，R’是配置库中已有电路的补偿输出。如果则用R’对应的补偿电路来产生演化算法的初始种群,并演化出R；反之，则根据R’对应的补偿电路来演化出然后在补偿输出上加上反相器。基于相似性的演化修复机制能够充分利用已有补偿电路的结构特点，加快演化算法的收敛速度，减少演化耗时，适用于实时性容错系统。

静态配置库的大小取决于系统规模和硬件资源，静态配置库的空间越大占用的存储资源也越多，同时查库的时间也会递增。图3给出了用静态配置库修复三位奇偶校验器电路中故障的示例。图中的计算单元矩阵(Function Element Array，FEA)包含四个计算单元，每个计算单元由两个多路选择器和一个函数模块组成，每个功能函数模块包含八个函数功能。计算单元的输入数据由cfg1和cfg2信号决定，计算单元的功能由cfg3信号决定。假设在线路f₀出现短路的故障，当输入I_n＝(010)时，系统的实际输出是O_real＝0,期望输出O_exp＝1，根据公式(5)可以得到R＝1，则可以判断系统出现故障。这时选择向量(I_n,O_real)＝(010,0)作为查库的索引，如果在库中能够查到匹配的修复电路，则说明该故障是已知故障，直接用库中的配置信息重构VRC。在该示例中，VRC被重配置成一个异或电路，故障电路被补修正，最终得到正确输出。配置库中的修复电路和故障索引是一对多的关系，即一个修复电路可能对应多个故障索引。例如故障向量(011,1)，(100,0)和(101,1)都对应着同一个修复电路。

④利用演化与补偿的方式重构系统

每修复一个故障，都会将对应的补偿电路存储在配置库中，但是配置库的存储空间有限，不可能存储所有的补偿电路。当配置库内存溢出时，配置库将无法存储新的补偿电路，而且随着系统长时间的运行，可能会出现更多的未知故障，配置库的作用逐渐降低，最终会影响系统的容错能力。为了提高系统长期运行的可靠性，当配置库内存溢出时，将采用基于补偿修复技术重构系统。

在重构系统时，考虑停滞效应对演化算法的影响。停滞效应是指种群的适应度在演化初期增加很快，但是当种群的适应度接近目标值时，适应度值停滞，大量的迭代次数都花费在了停滞阶段，但种群的适应度值却并没有增加，显然，演化一个部分正确的系统要比演化完整的目标系统要简单的多。在重构目标系统时，采用基于补偿修复技术的演化方式。演化过程中如果检测到停滞效应则停止演化，假设当前迭代次数为G_s,如果G_s,≥G_max,则表明不可能在规定的迭代次数内演化出目标系统，由于停滞效应一般出现在演化初期，这种情况一般不会发生。如果G_s<G_max，则启动修复进程对已经演化出的部分正确系统进行修正，修复进程必须在G_max-G_s次迭代次数内完成。由于修复电路的规模一般比较小，比较容易得到。