胚胎电子细胞阵列是一种新型的具有故障自检测和自修复能力的高可靠性硬件。在环境恶劣，人工维修难以开展以及对任务要求严苛，需要电子设备长时间连续可靠运行的领域，如深海、深空、强辐射等领域，具有广阔的应用前景。
自胚胎电子细胞阵列的概念提出以来，阵列内故障的实时在线检测问题一直是一个亟待解决的关键性问题。国内外众多学者针对这个问题开展了大量的研究，总结目前已有的故障检测方法，主要的设计思路可分为4类：
1) 第1类设计思路是细胞内或细胞间特定模块的局部检测。比如针对功能模块的双模冗余(Dual Modular Redundancy, DMR)检测[1-2]，针对存储模块的故障检测[3-5]，针对细胞间连线的冗余检测[6]，或者单个电子细胞的双模冗余检测[7]等。采用这类局部检测方法可以有效检测细胞内部及细胞间的各类资源故障，但是细胞结构需要根据具体的检测目标进行特定的设计，因此检测能力受到电子细胞结构的影响，而且细胞中的故障检测单元往往较少考虑自身的自检问题。
2) 第2类设计思路是采用外部检测资源对胚胎电子细胞阵列的输入输出进行实时检测。比如文献[8]等。这种方法对外部检测资源的要求很高，当电路规模很小时，比较有效，但随着电路规模增大，尤其当胚胎电子细胞阵列实现时序逻辑电路功能时，输入输出序列千变万化。如果完全记录这些状态，需要消耗很大的存储资源，如果采用免疫学习、神经网络等方法，则需要很长的学习时间。因此这种方法受到胚胎电子细胞阵列规模的限制，而且过分依靠外部资源，对胚胎电子细胞阵列本身的空闲资源利用不足。
3) 第3类设计思路是在阵列内设计在线BIST(Built-In Self-Test)结构[9-11]。比较有代表性的有原核电子细胞阵列结构[11-12]和充分利用电子细胞阵列可重构特性的Roving STARs[13]方法。基于原核电子细胞结构的原核电子细胞阵列采用链式的数据总线结构，具有很强的故障检测能力，但是检测能力受原核电子细胞结构、细胞连接资源结构以及周围细胞结构限制，通用性不强。以Roving STARs为代表的另一种在线BIST方法，通过不断地循环配置，将电子阵列中一定区域的电子细胞配置成为由测试图形产生器(Test Pattern Generator, TPG)、输出响应分析器(Output Response Analyzer, ORA)和被测单元(Block Under Test, BUT)构成的BIST结构，实现电子阵列的在线故障检测。这种方法充分利用了电子细胞阵列的可重构特性，具有硬件资源消耗少、检测能力强等优点，但是存在故障检测时间长、对电路性能影响大、对重构控制单元要求高等不足。
4) 第4类设计思路与以上3种方法有很大不同，其充分利用电子细胞阵列内的空闲资源，在电路映射阶段，自动生成一种在线故障检测结构，实现阵列内故障的实时在线检测。这种方法以文献[14]为代表，与以上3种方法相比，具有许多潜在的优势。与第1种方法相比，故障检测能力与电子细胞的具体结构无关，仅与映射生成的在线故障检测结构相关，设计良好的在线故障检测结构，不仅能够检测单个细胞或细胞间的局部故障，而且可以对整个工作电子细胞区域进行检测，故障覆盖率、检测率更高。与第2种方法相比，充分利用电子细胞阵列内部的空闲资源，生成检测结构的过程中不需要先验知识的学习，对于被测电路的类型和规模没有限制，可扩展性很强，适用于大规模组合和时序电路，而且对于外部检测资源的要求非常低。与第3种方法相比，可以实现故障的实时检测，检测在电路正常工作时进行，对电路性能影响小，而且不需要额外的计算和控制资源。因此，这种设计思路具有一定的研究价值和良好的研究前景，但是文献[14]仅针对组合电路进行了研究，没有研究时序电路的情况，所采用的奇偶校验码(parity code)与波格码(Berger code)，故障覆盖率有待提高，而且逻辑综合的过程并不能保证电路的全自检(Totally Self-Checking, TSC)特性100%实现。
本文受第4类设计思路的启发，提出了一种基于双模冗余的在线故障检测方法。首先，分析了双模冗余的故障检测结构所具有的特点及优势，并针对胚胎电子细胞中的查找表(Look Up Table, LUT)型功能单元，设计了专门的检测器，同时，为了提高设计效率，给出了双模冗余检测结构的自动化设计方法；然后，为了对双模冗余检测结构对单固定型故障的检测能力进行更详细的分析，提出了一种基于电路等价性验证的故障检测率分析方法；最后，分别选取了8个不同规模的组合和时序标准电路进行仿真，仿真结果显示了这些电路在双模冗余后面积、延时等指标的变化，并证明了这些双模冗余电路对于单固定型故障具有很高的故障检测率，为解决胚胎电子细胞阵列的在线故障检测难题提供了一个新的思路。
1 双模冗余的在线故障检测结构 1.1 双模冗余检测的基本结构双模冗余的故障检测结构如图 1所示，主要包括功能电路、双模冗余电路和检测器。其中，双模冗余电路的逻辑功能与功能电路完全相同，且具有完全相同的输入。双模冗余电路的输出包括功能输出和错误信号两部分。其中，功能输出为功能电路的输出，错误信号为检测器的输出。检测器的主要功能是比较2个电路的输出是否相同，当检测到2个电路输出不同时，错误信号输出经过编码的故障信息，否则输出正常信息。经过特殊设计的检测器也可以反映检测器自身的故障情况。
|
| 图 1 双模冗余检测结构 Fig. 1 DMR checking structure |
映射在胚胎电子细胞阵列中的双模冗余在线检测结构如图 2所示。图中：深色背景的电子细胞是工作细胞，构成电子细胞阵列的功能电路部分，实现胚胎电子细胞阵列的逻辑功能；浅色背景的电子细胞是空闲细胞，在双模冗余检测结构中被配置成为双模冗余电路和检测器，实现对被测电路的实时检测；白色背景的电子细胞是未被利用的空闲细胞。胚胎电子细胞阵列的输出包括功能电路的功能输出和双模冗余电路输出的错误信号。
|
| 图 2 胚胎电子细胞阵列中的双模冗余 Fig. 2 DMR mapped on embryonics array |
本文提出的基于双模冗余的在线故障检测结构与一些常见的在线故障检测结构，比如三模冗余(Triple Modular Redundancy, TMR)、基于错误检测码(Error Detecting Codes, EDC)的故障检测等方法[15]以及在胚胎电子细胞阵列中常用的局部检测(Local Detection, LD)、人工免疫系统(Artificial Immune System, AIS)和Roving STARs等检测方法相比，在故障检测率、检测速度、适用范围和设计难度等方面都具有一定的优势，具体如表 1所示。
| 检测方法 | 故障检测率 | 检测速度 | 资源消耗 | 适用范围 | 设计难度 |
| DMR | 高 | 实时 | 较大 | 无限制 | 低 |
| TMR | 高 | 实时 | 大 | 无限制 | 低 |
| EDC | 中等 | 实时 | 较小 | 一般用于组合电路 | 中等 |
| LD | 低 | 较快 | 中等 | 经特殊设计的电子阵列 | 高 |
| AIS | 较高 | 较快 | 小 | 小规模电路 | 中等 |
| Roving STARs | 高 | 慢 | 小 | 可重构电子阵列 | 高 |
由表 1可知，基于双模冗余的在线故障检测的主要优势如下：
1) 故障检测率高。不仅可以检测电子细胞内的故障，而且可以检测细胞间的连线故障。
2) 检测时间快。能够实现实时在线检测，而且检测不影响被测电路正常工作。
3) 适用范围广。对待测电路没有特殊限制，可用于组合电路和时序电路，也可用于大规模电路，可扩展性强。
4) 设计难度低。设计时不需要被测电路的先验知识，也不需要考虑双模冗余的具体结构，只需要设计好功能电路，相应的双模冗余电路即可自动生成。
5) 资源利用率高。充分利用了胚胎电子细胞阵列中的空闲细胞，在正常工作时，将原本空闲不用的空余细胞变成检测细胞，最大限度利用了硬件资源。
6) 与电子细胞阵列结构无关。经逻辑综合映射生成的双模冗余检测结构可应用于各种结构的电子细胞阵列(如Mesh型、Tree型等)，对后端布局布线过程没有影响，给后端的设计者提供了更大的设计空间。
但是，双模冗余也存在以下不足：
1) 资源消耗大。硬件资源消耗在200%以上，相应的功耗也在2倍以上。
2) 存在虚警。由于有冗余单元的存在，因此在提高了故障检测率的同时，虚警率也相应提高。
3) 故障定位能力差。双模冗余检测能够及时发现故障，但无法准确定位故障，要定位故障，还需要启动进一步的故障定位过程。
4) 受胚胎电子细胞阵列内空闲细胞数目限制。当胚胎电子细胞阵列中可用的空闲细胞较少时，无法构成有效的双模冗余检测结构。
1.2.2 胚胎电子细胞阵列中检测器设计及自检检测器是双模冗余检测结构中最关键的部分。目前，胚胎电子细胞中多采用4输入LUT作为功能单元，因此本文针对LUT型功能单元设计专门的检测器，如图 3所示。其中I_1~I_N和I′_1~I′_N分别连接双模冗余检测结构中功能电路和双模冗余电路的输出。检测器中的每一个LUT实现2对输入的比较，当2对输入都相同时，输出0，否则输出1。O_1~O_N为检测器的输出端口，当输出为全零时，表示检测器没有检测到故障，否则，表示检测器检测到故障。
|
| 图 3 检测器结构 Fig. 3 Structure of checker |
检测器不仅能够检测到故障，而且可以根据输出值实现检测器自身的自检。如图 3所示，假设其中某个LUT的编号为i，则称该LUT与编号为i-1、i+1的LUT为逻辑相邻，特别的，对于LUT 1，逻辑相邻的LUT为LUT N和LUT 2；对于LUT N，逻辑相邻的LUT为LUT N-1和LUT 1。对于LUTi，输入端为I_i，I′_i，I_i+1，I′_i+1，输出端为O_i，相应的输入值记为Ii，I′i，Ii+1，I′i+1，输出值记为Yi，记Ii、I′i异或的结果为Xi，Ii+1、I′i+1异或的结果为Xi+1，LUT的输入和输出之间的逻辑关系如下：
|
(1) |
整个检测器的输入输出关系如下：
|
(2) |
则通过检测器的输出值判断检测器本身是否存在故障，即自检的过程，实际上是通过式(2) 中输出值Y1，Y2，…，YN求解变量X1~XN的过程，当X1~XN都有解时，则检测器无故障，否则检测器存在故障。
当变量Xi=0时，表示输入Ii、I′i相同，当变量Xi=1时，表示输入Ii、I′i不同，即输入端I_i或I′_i发生故障。假设Y1，Y2，…，YN中仅Yi=0，其余输出为1，则式(2) 至少有一组解{Xi=0, Xi+1=0, Xj=1(j≠i且j≠i+1)}。假设Y1，Y2，…，YN中有M个值为0，M≥2，则Y1，Y2，…，YN可被分为逻辑相邻的M段，假设其中自变量个数最少的一段为Yj~Yk，如下：
|
(3) |
式中:k>j。当k=j+1时，有解{Xk=0, Xj=0, Xj+1=0}；当k=j+2时，无解；当k>j+2时，至少有一组解{Xk=0, Xk+1=0, Xj=0, Xj+1=0, Xp=1(p≠k, k+1, j, j+1)}。因此，在Y1，Y2，…，YN中，如果2个0之间1的个数不为1时，则自变量{Xj, Xj+1, …, Xk+1}有解，式(2) 所示的整个检测器方程组也有解。如果在Y1，Y2，…，YN中，存在2个0之间1的个数为1的情况，则无解。在检测器正常工作时，这种情况是不可能发生的，如果发生，则说明检测器自身出现故障。检测器正是利用这一特性实现故障自检。
2 双模冗余检测结构的自动设计电子自动化设计(Electronic Design Automation, EDA)技术是提高集成电路设计效率的关键技术，是目前集成电路设计中广泛采用的方法。但是，在常见的EDA设计过程中，电路中冗余的部分会被优化，无法得到双模冗余的检测结构。所以，需要在原有的EDA工具基础上，开发新的能够产生双模冗余检测结构的设计程序。与文献[14]中所采用的方法不同，本文采用学术界广泛研究的ABC[16]逻辑综合工具，在此基础上，开发一种双模冗余检测结构的自动化生成程序。
双模冗余检测结构的自动化设计流程如图 4所示。首先，输入需要进行双模冗余的功能电路描述文件(描述文件可以是Verilog、VHDL、.blif、.aig、.net、.bench等多种格式)；然后，被描述的电路被翻译并提取出来，生成后续可以处理的电路网表结构，经过一系列逻辑综合优化[16-17]过程，生成最优化(逻辑门数量最少，延时最小，触发器个数最少等)的电路网表; 最后，经过映射，生成由LUT和D触发器构成的电路网表，在胚胎电子细胞中，功能模块一般由LUT和D触发器构成，因此，映射过程实际上是将优化的逻辑门网表映射为由胚胎电子细胞构成的电路网表的过程。映射完成后，即可对电路进行双模冗余设计，设计的输出是后端布局布线(Placement and Routing, P & R)工具[18]能够处理的.blif格式的电路描述文件。
|
| 图 4 双模冗余设计方法 Fig. 4 Design methodology for DMR |
双模冗余电路生成的伪代码如下：
Dual_Function(Network circuit, Filepath filename){
circuit_new=NetworkAlloc(Network);
for (i=0;i < 2;i++){
for each object{
circuit_new->object= ObjCopy(circuit->object);
do{ObjCreateNames(circuit_new->object);
}while(!Names already exist)};
for each object{
NetworkConnectObj(circuit_new, object); }
}
NetworkInputNames(circuit_new);
NetworkOutputNames(circuit_new);
IOWriteDual(circuit_new, filename, FileType){
NetworkRewriteInputNames(filename, circuit_new);
for(i=0;i < NetworkGetOutputNum(circuit_new)/2;i++)
{IOWriteFanins(filename, ObjGetNames(object));
IOWriteChecker (AssignNames(i));
IOWriteCheckerFunction(); }
NetworkRewriteOutputNames(filename, circuit_new); }
}
生成双模冗余检测结构的函数为Dual_Function，函数的主要输入参数是当前待设计的电路网表，生成的双模冗余电路以.blif格式存储在指定文件路径和文件名的filename文件中。object为电路网表中各元素的统称，包括输入端、输出端、触发器、逻辑节点等多种类型。程序首先构建一个新的电路网表circuit_new，根据输入的电路网表，将每个元素复制到新的电路网表中，并对每个元素编号命名，然后依次连接各元素，重复执行以上流程一次后，circuit_new中生成2个相互独立的、与输入电路网表完全相同的电路，此时circuit_new中输入端和输出端的数目为输入电路网表的2倍。因此，还需要重新对输入端进行命名，使circuit_new中的2个电路网表具有相同的输入。电路网表复制完成后，还需要在电路网表中加入检测器，本文检测器个数与输入电路网表中输出端个数相同，对每一个检测器，首先确定检测器的输入端，然后对检测器命名，并设计具体的逻辑功能。加入检测器后，对circuit_new的输出端进行修改，输出功能输出和错误信号。
由以上的设计流程可以看出，设计者在设计电路时，只需要设计功能电路即可，双模冗余检测结构在逻辑综合中自动生成，而且设计的过程对输入的功能电路没有任何要求，为设计人员提供了方便。
3 故障检测率分析 3.1 故障类型及故障检测率在电子设备正常运行过程中，同一时刻发生2个或多个故障的概率比较小，因此本文主要针对单故障进行研究。在数字电路故障检测诊断的研究中，固定型故障是一种非常常用的故障模型，其能够反映电路中由于元件损坏而产生的固定高/低电平故障，也能反映元件之间连线的断路型连线故障和相当一部分短路故障，因此，本文主要研究单固定型故障。单固定型故障可分为单固定型0故障(stuck at 0, s-a-0) 和单固定型1故障(stuck at 1, s-a-1)。
当电路中发生单固定型故障时，如果对于电路的每一组输入，电路的非正常输出总能被检测器检测出来，则称电路对于此固定型故障可有效检测。本文定义电路的故障检测率为
|
(4) |
式中：CFN为可有效检测的故障数量；FN为全部的故障数量。
当检测电路中发生单固定型故障时，如果至少存在一组输入，使检测器输出错误信号，则称检测电路对于此固定型故障是可自检的。本文定义检测电路中的故障可自检率为
|
(5) |
式中:STFN为可自检的故障数量。
3.2 基于电路等价性验证的故障检测率分析方法传统的故障检测率分析方法主要是故障注入，然后比较输入输出的关系来判断电路的故障检测情况，进而计算得到故障检测率。这种方法可以得到非常详细可靠的数据，但是普遍存在实验时间长、实验代价高等问题。因此，本文提出一种新的基于电路等价性验证的故障检测率分析方法。故障检测率分析的总体流程如图 5所示。
|
| 图 5 故障检测率计算流程 Fig. 5 Calculation process of fault detection rate |
如图 5所示，计算待测电路的故障检测率时，首先将待测电路变成待验证电路，然后对待验证电路中的所有节点依次进行单固定型故障注入，并将故障注入后的电路与故障注入前的电路进行等价性验证[19-20]，并记录验证结果，当所有节点依次完成故障注入和等价性验证后，即可得到待测电路的故障检测率。
假设待检测的双模冗余电路如图 6所示。电路可分为功能电路FC和错误检测电路EDC。其中，错误检测电路由双模冗余电路和检测器构成。为了对电路的故障检测率进行分析，首先对电路进行改造，构成如图 7所示的等价性验证电路ECC。
|
| 图 6 待测双模冗余电路 Fig. 6 DMR circuit to be detected |
|
| 图 7 等价性验证电路 Fig. 7 Equivalence checking circuit |
如图 7所示，功能电路FC和错误检测电路EDC构成的待测电路被复制为FC′和EDC′，其中FC和FC′构成Miter电路，在EDC和EDC′的基础上加上一个专门设计的附加检测器AC，附加检测器主要用来对错误检测电路EDC的输出进行特征提取，并对错误检测电路EDC的状态进行判断，本文中附加检测器AC的具体结构如图 8和图 9所示。
|
| 图 8 附加检测器 Fig. 8 Additional checker |
|
| 图 9 基于双模冗余检测的附加检测电路 Fig. 9 Additional checker circuit based on DMR detection |
如图 8所示，附加检测器AC的输入为错误检测电路EDC输出的错误信号，输出包括对错误检测电路EDC输出进行特征提取的特征信号FO和对错误检测器的自检信号EO，当错误检测电路EDC输出表示检测到故障时，FO输出为1，否则为0；当附加检测器AC判断错误检测电路EDC发生故障时，EO输出为1，否则为0。
如图 9所示，附加检测器AC由N个与门和2个N输入的或门组成。由1.2.2节对检测器的分析可知，在检测器的输出Y1，Y2，…，YN中，记任意3个逻辑相邻的输出为一组，共N组，记其中一组为{Yi-1, Yi, Yi+1}，则当{Yi-1, Yi, Yi+1}值不为{0, 1, 0}时，可以认为检测器无故障，否则，检测器出现故障。
在故障检测率分析的过程中，除功能电路FC和错误检测电路EDC之外的全部电路都是正常的，只针对功能电路FC和错误检测电路EDC进行单固定型故障注入。由图 7可知，如果等价性验证电路中无故障存在，那么等价性验证电路实际上是一个输出恒为0的电路。当注入单固定型故障时，分2种情况进行考虑。
1) 当故障发生在功能电路FC时，如果在某输入情况下，导致FC输出与正常值FC′不同，此时Miter电路输出为1，如果AC的FO输出与AC′的FO输出也不同，那么说明双模冗余检测器检测到故障，电路输出为0。因此，当功能电路FC中存在单固定型故障时，如果对于每一组输入，FC的功能输出或者输出正常值，或者异常输出都能被检测出来，那么电路的输出恒为0，即注入故障的电路与等价性验证电路等价，说明待测电路可以检测此单固定型故障。否则，注入故障的电路与等价性验证电路不等价，说明待测电路不能有效检测此故障。
2) 当故障发生在错误检测电路EDC时，此时Miter电路的输出恒为0，即功能电路FC不存在故障。当附加检测器AC检测到注入故障的EDC与正常EDC′输出不同时，特征信号FO输出1，此时附加检测器AC如果能确定错误检测电路EDC发生故障，则自检信号EO输出为1，否则输出为0。理想情况下，每当错误检测电路EDC发生故障时，附加检测电路AC应该总能确定该故障，此时注入故障的等价验证电路输出恒为0。但是实际上，由于受到错误检测电路EDC输出端口的限制，错误检测电路EDC内部元件的可观性较差，通常仅能通过错误检测电路EDC的输出来判断其自身是否存在故障。例如在本文中，通过错误检测电路EDC的输出仅能检测双模冗余结构中检测器是否发生故障。因此，存在这种情况，即附加检测器AC检测到EDC与EDC′输出不同，但附加检测器AC不能确定错误检测电路EDC发生故障，此时EO输出为0。本文中，当EDC中的双模冗余电路发生故障时，等价性验证电路不恒等于0说明该故障可检测。当EDC中的检测器故障时，等价性验证电路恒等于0说明该故障不影响检测器正常工作(本文中视为正常)或检测器可自检。
因此，对于发生在等价性验证电路ECC中功能电路FC或错误检测电路EDC中的某单固定型故障，通过故障注入前后电路的等价性验证，可以得到电路对于该故障的故障检测能力或故障自检能力。当遍历功能电路FC和错误检测电路EDC中的所有节点，分别注入s-a-0型故障和s-a-1型故障并进行等价性验证后，就可以计算得到电路的故障检测率和可自检率。
4 仿真实验仿真实验在逻辑综合工具ABC及布局布线工具VPR环境中进行，分别选取标准电路集中常用的8个不同规模的组合电路和时序电路进行仿真。仿真中采用经典的行列移除的胚胎电子细胞阵列结构，并设定每个胚胎电子细胞中的功能模块只包含一个LUT和D触发器单元，根据胚胎电子细胞阵列的特点，对FPGA结构描述文件中逻辑单元块CLB和I/O端口等模块进行修改，但保留连线资源和I/O端口等模块中的面积、延时等信息。具体方法可参考文献[21]。
4.1 硬件资源消耗及性能分析本文主要分析双模冗余电路与原电路相比，在面积及电路延时等方面的变化情况，因此主要针对面积增长率(Area Increase Rate, AIR)和延时增长率(Delay Increase Rate, DIR)2个指标的变化情况进行分析。分别将不同规模的8个组合电路和8个时序电路映射到胚胎电子细胞阵列中，然后进行布局布线，布线完成后的电路规模、面积增长率和延时增长率情况如表 2所示。
| 电路 | 电路规模 | 触发器个数 | 输出个数 | 输入个数 | AIR | DIR |
| c8 | 7×7 | 18 | 28 | 2.423 8 | 1.374 1 | |
| dk14 | 7×7 | 3 | 5 | 4 | 2.201 1 | 1.019 2 |
| c499 | 9×9 | 32 | 41 | 2.584 3 | 1.347 2 | |
| s344 | 9×9 | 15 | 11 | 10 | 2.113 5 | 1.075 9 |
| term1 | 10×10 | 10 | 34 | 2.148 4 | 1.202 4 | |
| s641 | 10×10 | 19 | 23 | 36 | 2.364 1 | 1.368 3 |
| apex7 | 11×11 | 49 | 37 | 2.239 0 | 1.318 4 | |
| s820 | 11×11 | 5 | 19 | 19 | 2.343 0 | 1.190 1 |
| c432 | 12×12 | 7 | 36 | 2.041 8 | 1.111 8 | |
| ex1 | 12×12 | 5 | 19 | 10 | 2.188 1 | 1.991 0 |
| c880 | 14×14 | 26 | 60 | 2.258 8 | 1.470 6 | |
| s1 | 14×14 | 5 | 6 | 9 | 2.013 1 | 0.973 2 |
| rot | 18×18 | 135 | 107 | 2.482 3 | 1.353 0 | |
| s1494 | 18×18 | 6 | 19 | 9 | 2.113 2 | 1.198 2 |
| c3540 | 21×21 | 22 | 50 | 2.031 0 | 1.314 5 | |
| scf | 21×21 | 7 | 56 | 28 | 2.287 6 | 1.266 7 |
首先将实现电路所需要的胚胎电子细胞阵列的大小定义为该电路的规模。如表 2中的c8电路，在电子细胞阵列中实现c8, 最少需要7行7列的胚胎电子细胞，因此，定义c8的电路规模为7×7。同理，根据标准电路在胚胎电子细胞阵列中的映射情况，将标准电路划分成8个不同的规模。电路的规模可看做是对电路硬件消耗的近似估计。
从理论模型上分析，双模冗余结构主要由2个相同的电路加上1个检测器构成，因此经过双模冗余后，电路的面积增长率AIR及延时增长率DIR为
|
(6) |
|
(7) |
式中：A为原电路的面积；C为检测器的面积。因此，AIR的理论值应该为2+C/A。CD为原电路延时，DCD为双模冗余电路延时。由1.2.2节可知，检测器的面积与输出端口的个数相关，而电路的面积可由电路的规模近似，因此定义电路的输出个数与电路规模的比值为输出规模比(Output number Dividing the circuit Scale, ODS)。则由ODS就可以近似估计电路双模冗余后的面积增长率，即
|
(8) |
式中：OutputNum为电路输出端个数；CircuitScale为电路规模。
可见，由式(8) 估计双模冗余的面积增长率是非常简单方便的。
但是，在实际映射的过程中，电路的面积不仅包括构成电路的各功能模块，还包括模块之间的连接资源以及I/O端口资源，为了得到更详细的数据，记录仿真过程中各标准电路的总面积增长率、逻辑单元面积增长率和连线面积增长率，如图 10所示。
|
| 图 10 双模冗余电路的面积增长率 Fig. 10 Area increase rate of DMR circuits |
图 10中，电路的总面积包括逻辑资源面积和连线资源面积。其中，逻辑资源面积包括功能模块的电子细胞面积和I/O端口面积。连线资源面积为阵列中开关盒的面积。为了更加清楚直观，将16个标准电路按照输出规模比ODS由小到大依次排列，作为横坐标。纵坐标为面积增长率AIR。图 10中的理论值曲线即为电路的输出规模比ODS。可以看出，逻辑单元面积增长率曲线与理论值曲线较为接近，但个别点有较大的偏差，这主要是由2个原因造成的：① 在计算逻辑单元面积增长率时，不仅包含逻辑单元也包含I/O单元，因此在ODS较小时，I/O单元对计算的影响较小，两曲线几乎重合，但当ODS增大时，两曲线的差距越来越大；② ODS在计算时采用的电路规模是估计值，存在误差，比如图 10中的c8电路，电路的规模为7×7，而实际上，映射过程中仅需要39个电子细胞即可，存在比较大的误差。图 10中的连线面积增长率由于受到电路结构及具体布局布线算法的影响，呈现出较大的波动，无明显规律性。可以看出，电路的总面积增长率由于受到连线资源的影响，也呈现出一定的波动性，但是波动范围在以逻辑单元面积增长率曲线和连线面积增长率曲线为上下限的空间内，大致随着电路ODS的增大而增大。
由图 10可知，虽然受到连线资源的影响，但是电路的实际面积增长率大致随着电路输出规模比ODS的增大而增大，面积增长率大致在200%~300%之间，所以，可以用ODS近似估计电路的面积增长率。
将标准电路分为8个规模，并在每种规模的标准电路中选择时序电路和组合电路分析双模冗余后电路的延时变化，如图 11所示。可以看到，双模冗余后，电路的延时变化没有明显特征，延时增长率也并不随电路规模的增大而增大。所以，双模冗余后电路的延时并不一定大幅增加，也可能变化不大。虽然双模冗余后电路的延时整体呈现增加的趋势，但增加的具体程度难以确定，如ex1电路，双模冗余后延时上升将近2倍；但dk14、s1等电路，电路的延时几乎没有变化。从仿真结果看，组合电路的延时增长率相比时序电路更加稳定，其值大致在110%~150%之间，时序电路的延时增长率波动比较大，其值大致在100%~200%之间。因此，双模冗余后电路的延时变化情况并不能简单确定，一般来说，电路的延时变化情况与电路自身结构以及布局布线算法有很大关系，对于具体电路，不能采用固定的方法进行估算，要得到双模冗余后延时比较短、速度比较快的电路，还需要对布局布线算法进行专门的设计。
|
| 图 11 双模冗余电路的延时增长率 Fig. 11 Delay increase rate of DMR circuits |
对16个标准电路依次进行单固定型故障注入实验，并采用等价性验证的方法对故障的检测能力进行分析，仿真结果如表 3所示。
| 电路 | 功能电路 | 检测电路 | |||||||||
| LUT FDR | 触发器FDR | LUT ST | 触发器ST | ||||||||
| s-a-0 | s-a-1 | s-a-0 | s-a-1 | s-a-0 | s-a-1 | s-a-0 | s-a-1 | ||||
| c8 | 100 | 100 | 100 | 100 | |||||||
| c432 | 100 | 100 | 100 | 100 | |||||||
| c499 | 100 | 100 | 100 | 100 | |||||||
| term1 | 100 | 100 | 100 | 99.0 | |||||||
| apex7 | 100 | 100 | 97.8 | 100 | |||||||
| c880 | 100 | 100 | 100 | 100 | |||||||
| rot | 100 | 100 | 99.3 | 99.3 | |||||||
| c3540 | 100 | 100 | 100 | 100 | |||||||
| dk14 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | |||
| s344 | 100 | 100 | 100 | 100 | 98.7 | 98.7 | 100 | 100 | |||
| s641 | 100 | 100 | 100 | 100 | 87.5 | 96.4 | 78.9 | 100 | |||
| s820 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | |||
| ex1 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | |||
| s1 | 100 | 100 | 100 | 100 | 81.6 | 99.5 | 100 | 100 | |||
| s1494 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | |||
| scf | 100 | 100 | 100 | 100 | 99.2 | 100 | 100 | 100 | |||
仿真中，分别在电路逻辑节点的输出端和触发器的输出端注入s-a-0型和s-a-1型故障。当故障发生在功能电路时，记录电路的故障检测率FDR，定义见式(4)；当故障发生在检测电路时，记录检测器的可自检率ST，定义见式(5)。理想情况下，功能电路的故障检测率和检测电路的可自检率都应该是100%，但是实际上，检测器由于受到端口数目的限制以及逻辑综合过程中优化算法的影响，可能出现检测器某些内部节点的故障在检测器输出端是不可观的情况。
总体上看，双模冗余检测电路的检测率非常高，可以达到100%，但这只是针对在电路输出端可观测的故障，对于某些在输出端不可观的故障，检测电路将输出正常信号，此时，虽然电路内部可能存在故障，但是并不影响电路的正常功能，这种情况也认为电路是无故障的。此外，双模冗余检测电路中检测电路的可自检率也比较高，大多数故障都可以在输出端表现出来。所以，当双模冗余检测电路工作时，虽然无法准确定位故障，但是却具有很高的故障检测率，当检测到故障后，可以立即启动相应的故障定位机制来完成故障的诊断定位。
5 结论本文设计实现了基于双模冗余的胚胎电子细胞阵列的在线故障检测方法，并对双模冗余的自动化生成方法、面积、延时、故障检测率等进行了分析。
1) 双模冗余的自动化生成方法对输入电路的类型和规模等没有限制，可以实现不同规模的组合电路和时序电路的双模冗余设计，设计流程与具体的电子细胞结构及阵列结构无关，通用性强。
2) 双模冗余的资源消耗比较大，电路的延时也有一定的增加，但并不一定有很大的劣化。当映射到经典的胚胎电子细胞阵列中时，设计产生的双模冗余电路，面积增长率随输出规模比的增大而增大，电路的延时也呈增加的趋势，但具体的延时增长率还与电路结构和布局布线算法相关，难以简单估计。
3) 虽然双模冗余检测故障定位能力较差，但是对于单固定型故障，双模冗余检测的故障检测率很高，可达到100%。
总的来说，基于双模冗余的在线故障检测方法，虽然在电路面积、延时等方面有所增加，但是设计方法简单，有效利用了胚胎电子细胞阵列中的空闲细胞，可实时检测故障，故障检测率高，为解决胚胎电子细胞阵列在线故障检测难题提供了一种新的思路。
| [1] | MANGE D, SANCHEZ E, STAUFFER A, et al. Embryonics:A new methodology for designing field-programmable gate arrays with self-repair and self-replicating[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1998, 6(3): 387–399. DOI:10.1109/92.711310 |
| [2] | KIM S, CHU H, YANG I, et al. A hierarchical self-repairing architecture for fast fault recovery of digital systems inspired from paralogous gene regulatory circuits[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2012, 20(12): 2315–2328. DOI:10.1109/TVLSI.2011.2176544 |
| [3] | PRODAN L, UDRESCU M, VLADUTIU M, et al.Self-repairing embryonic memory arrays[C]//Proceedings 2004 NASA/DoD Conference on Evolvable Hardware.Piscataway, NJ:IEEE Press, 2004:130-137. |
| [4] | YANG S S, WANG Y R.A new self-repairing digital circuit based on embryonic cellular array[C]//Proceedings 2006 8th International Conference on Solid-State and Integrated Circuit Technology.Piscataway, NJ:IEEE Press, 2006:1997-1999. |
| [5] | BRADLEY D, CESAR O S, TYRRELL A.Embryonics+Immunotronics:A bio-inspired approach to fault tolerance[C]//Proceedings of the 2nd NASA/DoD Workshop on Evolvable Hardware.Piscataway, NJ:IEEE Press, 2000:215-223. |
| [6] |
郝国锋, 王友仁, 张砦, 等. 可重构硬件芯片级故障定位与自主修复方法[J].
电子学报, 2012, 40(2): 384–388.
HAO G F, WANG Y R, ZHANG Z, et al. In-chip fault localization and self-repairing method for reconfigurable hardware[J]. Chinese Journal of Electrics, 2012, 40(2): 384–388. (in Chinese) |
| [7] | ZHANG X, DRAGFFY G, PIPE A G, et al. Artificial innate immune system:An instant defence layer of embryonics[J]. Lecture Notes in Computer Science, 2004, 3239(1): 302–315. |
| [8] | CANHAM R O, TYRRELL A M. A hardware artificial immune system and embryonic array for fault tolerant systems[J]. Genetic Programming and Evolvable Machines, 2003, 4(4): 359–382. DOI:10.1023/A:1026143128448 |
| [9] | CANHAM R O, TYRRELL A M.An embryonic array with improved efficiency and fault tolerance[C]//Proceedings 2003 NASA/DoD Conference on Evolvable Hardware.Piscataway, NJ:IEEE Press, 2003:265-272. |
| [10] | SAMIE M, DRAGFFY G, TYRRELL A M. Novel bio-inspired approach for fault-tolerant VLSI systems[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013, 21(10): 1878–1891. DOI:10.1109/TVLSI.2012.2220793 |
| [11] | BREMNER P, LIU Y, SAMIE M, et al. SABRE:A bio-inspired fault-tolerant electronic architecture[J]. Bioinspiration & Biomimetics, 2013, 8(1): 1–16. |
| [12] | UPEGUI A, THOMA Y, MORENO J M, et al.The perplexus bio-inspired reconfigurable circuit[C]//Proceedings 2007 NASA/ESA Conference on Adaptive Hardware and Systems.Piscataway, NJ:IEEE Press, 2007:600-605. |
| [13] | ABRAMOVICI M, EMMERT J M, STROUD C E.Roving STARs:An integrated approach to on-line testing, diagnosis, and fault tolerance for fpgas in adaptive computing systems[C]//Proceedings the 3rd NASA/DoD Workshop on Evolvable Hardware.Piscataway, NJ:IEEE Press, 2001:73-92. |
| [14] | BOLCHINI C, SALICE F, SCIUTO D.Designing self-checking FPGAs through error detection codes[C]//Proceedings 17th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems.Piscataway, NJ:IEEE Press, 2002:60-68. |
| [15] | STOTT E, SEDCOLE P, CHEUNG P Y K.Fault tolerant methods for reliability in FPGAs[C]//International Conference on Field Programmable Logic and Applications.Piscataway, NJ:IEEE Press, 2008:415-420. |
| [16] | BRAYTON R, MISHCHENKO A. ABC:An academic industrial-strength verification tool[J]. Lecture Notes in Computer Science, 2010, 6174(1): 24–40. |
| [17] | MISHCHENKO A, CHATTERJEE S, BRAYTON R.DAG-aware AIG rewriting:A fresh look at combinational logic synthesis[C]//Proceedings 2006 Design Automation Conference.Piscataway, NJ:IEEE Press, 2006:532-535. |
| [18] | LUU J, GOEDERS J, WAINBERG M, et al. VTR7.0:Next generation architecture and cad system for FPGAS[J]. ACM Transactions on Reconfigurable Technology and Systems, 2014, 7(2): 6. |
| [19] | MISHCHENKO A, CHATTERJEE S, BRAYTON R, et al.Improvements to combinational equivalence checking[C]//2006 IEEE/ACM International Conference on Computer Aided Design.Piscataway, NJ:IEEE Press, 2006:836-843. |
| [20] | MISHCHENKO A, CASE M, BRAYTON R, et al.Scalable and scalably-verifiable sequential synthesis[C]//2008 IEEE/ACM International Conference on Computer Aided Design.Piscataway, NJ:IEEE Press, 2008:234-241. |
| [21] |
朱赛, 蔡金燕, 孟亚峰. 一种LUT型胚胎电子阵列的功能分化方法[J].
电子学报, 2015, 43(12): 2440–2448.
ZHU S, CAI J Y, MENG Y F. A functional differentiation method for LUT-based embryonics array[J]. Chinese Journal of Electrics, 2015, 43(12): 2440–2448. DOI:10.3969/j.issn.0372-2112.2015.12.014(in Chinese) |