基于相关性分离的逻辑电路敏感门定位算法

蔡烁; 何辉煌; 余飞; 尹来容; 刘洋

doi:10.11999/JEIT230012

基于相关性分离的逻辑电路敏感门定位算法

doi: 10.11999/JEIT230012

蔡烁^1, ,,
何辉煌¹,
余飞¹,
尹来容²,
刘洋³

1.
长沙理工大学计算机与通信工程学院长沙 410114
2.
长沙理工大学汽车与机械工程学院长沙 410114
3.
中通服咨询设计研究院有限公司南京 210019

基金项目: 国家自然科学基金(62172058)，湖南省自然科学基金(2022JJ10052, 2022JJ30624)

详细信息

作者简介:
蔡烁：男，博士，副教授，研究方向为容错计算、电路系统可靠性等

何辉煌：男，硕士生，研究方向为容错计算、电路系统可靠性

余飞：男，博士，副教授，研究方向为非线性系统与电路、忆阻神经网络等

尹来容：男，博士，副教授，研究方向为机构学与机器人、机械设计与理论等

刘洋：男，硕士，高级工程师，研究方向为无线网络通信规划与设计

通讯作者:
蔡烁　caishuo@csust.edu.cn

中图分类号: TN431.2; TN406
计量
- 文章访问数: 369
- HTML全文浏览量: 193
- PDF下载量: 72
- 被引次数: 0
出版历程
- 收稿日期: 2023-01-10
- 修回日期: 2023-04-12
- 网络出版日期: 2023-04-20
- 刊出日期: 2024-01-17

Critical Gates Localization of Logic Circuits Based on Correlation Separation

1.
School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114, China
2.
College of Automotive and Mechanical Engineering, Changsha University of Science and Technology, Changsha 410114, China
3.
Zhongtong Service Consulting Design and Research Institute Company Limited, Nanjing 210019, China

Funds: The National Natural Science Foundation of China (62172058), The Natural Science Foundation of Hunan Province (2022JJ10052, 2022JJ30624)

摘要

摘要: 随着CMOS器件特征尺寸进入纳米量级，因高能粒子辐射等造成的电路失效问题日益严重，给电路可靠性带来严峻挑战。现阶段，准确评估集成电路可靠性，并以此为依据对电路进行容错加固，以提高电路系统可靠性变得刻不容缓。然而，由于逻辑电路中存在大量扇出重汇聚结构，由此引发的信号相关性导致可靠性评估与敏感单元定位面临困难。该文提出一种基于相关性分离的逻辑电路敏感门定位算法。先将电路划分为多个独立电路结构(ICS)；以ICS为基本单元分析故障传播及信号相关性影响；再利用相关性分离后的电路模块和反向搜索算法精准定位逻辑电路敏感门单元；最后综合考虑面向输入向量空间的敏感门定位及针对性容错加固。实验结果表明，所提算法能准确、高效地定位逻辑电路敏感单元，适用于大规模及超大规模电路的可靠性评估与高效容错设计。
- 逻辑电路 /
- 失效率 /
- 相关性分离 /
- 敏感门定位 /
- 容错设计
Abstract: With the feature size of CMOS device entering the nanoscale, the circuit failure issue caused by high-energy particle radiation is becoming more and more serious, which brings severe challenges to the circuit reliability. At present, it is urgent to accurately evaluate the reliability of the integrated circuit and reinforce the fault tolerance of circuit, so as to improve the reliability of the circuit system. However, due to the large number of fan-out reconvergence structures in the logic circuit, the resulting signal correlation causes difficulties in reliability evaluation and critical gates location. This paper proposes critical gates location algorithm for logic circuit based on correlation separation. First, the circuit is divided into multiple Independent Circuit Structures (ICS); second, taking ICS as the basic unit to analyze fault propagation and signal correlation; Then, the circuit module after correlation separation and the reverse search algorithm is used to accurately locate the circuit critical gates; Finally, critical gates location and targeted fault tolerance reinforcement for the input vector space are comprehensively considered. The experimental results show that proposed algorithm can accurately and efficiently locate the critical gates of logic circuit, and it is suitable for reliability evaluation and efficient fault-tolerant design of large-scale and super-scale circuits.
- Logic circuit /
- Failure /
- Correlation separation /
- Critical gate location /
- Fault tolerant design

HTML全文

1. 引言

随着互补金属氧化半导体(Complementary Metal Oxide Semiconductor, CMOS)器件特征尺寸持续缩小，电路规模不断增大，芯片的速度、功耗等性能得到稳步提升。但与此同时，工艺扰动、环境噪声和粒子辐射等造成的芯片失效率问题日益严重，给电路可靠性带来严峻挑战^[1-3]，尤其是因空间高能粒子辐射引发的软错误所带来的影响最为严重。依据国际半导体技术发展蓝图(International Technology Roadmap for Semiconductors, ITRS)对集成电路的预测，电路制造工艺由45 ns缩减至12 ns时，电路软错误率可增加10个以上数量级。因此，在设计阶段对电路失效率进行有效评估并采取合理容错与加固设计以提高产品可靠性变得刻不容缓^[4]。

电路可靠程度可用电路失效率衡量。准确、高效地评估电路失效率是指导高效容错设计的前提^[5]。逻辑电路失效率评估方法一般可分两类：基于模拟的方法与基于信号概率分析的方法。蒙特卡罗(Monte Carlo, MC)方法是典型的基于模拟的方法，其准确性与模拟次数密切相关^[6]。由于要模拟多次才能保证准确性，MC方法往往耗时较长。概率转移矩阵(Probability Transition Matrix, PTM)与概率门模型(Probabilistic Gate Models, PGM)方法都可通过准确分析电路的输入输出关系评估电路整体失效率。PTM方法通过建立基本门电路的输入与输出关系评估电路可靠性，是一种能准确计算电路整体失效率的概率分析方法，其缺点是算法的空间复杂度太大^[7,8]。PGM方法利用条件概率计算不同类型扇出重汇聚结构的节点信号概率，具有线性的空间复杂度，但在扇出重汇聚处的指数级时间复杂度未能得到有效解决。基于PGM的估算方法则假设所有逻辑门的输入信号相互独立，通过逐个门迭代计算输出节点概率，虽然计算过程简单，但因忽视了信号相关性影响，仅能得到近似结果^[9-11]。文献[12]表明三模冗余技术是目前使用最广泛的缓解FPGA软错误的电路加固技术，可以有效提高电路可靠性。文献[13]提出的关键信号算法(Critical Score Algorithm, CSA)可快速计算特定输入下的电路失效率，其复杂度与电路规模呈线性关系，但也因其没有考虑信号相关性而导致准确性不高。当前关于电路信号相关性的研究仍无法做到在保证计算精度的情况下解决耗时问题，难以应用于超大规模电路的评估与计算。

精准定位敏感目标且针对性地容错加固能以最小代价降低电路失效率^[14,15]。在容错设计中，人们关注的是那些对电路输出端有直接影响的门，即敏感门。敏感门与输入激励向量及电路拓扑结构有关^[16]。文献[17]结合信号传播特点，通过深度优先搜索递归算法对敏感单元进行标识，但因其重复计算扇出节点而影响了准确性。文献[18]考虑了扇出源节点与敏感门的关系，并通过从电路原始输出端向前迭代获取潜在敏感门集合，再逐一验证集合中的门单元。然而，潜在敏感门集获取方法是基于关键信号的，没有准确考虑信号相关性影响的情况下，潜在敏感门集本身存在误差。综上，由于电路规模增大和信号相关性影响，目前的方法很难既准又快地评估超大规模电路失效率^[19]；也很难精准、高效地定位对电路失效率影响较大的敏感单元。

本文提出一种相关性分离方法用于准确、快速地计算特定向量激励下的电路失效率；在此基础上，利用相关性分离后的电路模块和反向搜索算法精准定位电路敏感单元；再综合考虑多输入激励的情况，确定最优容错目标，实现以低容错成本提高电路可靠性的目的。

本文第2节详细介绍相关性分离方法(COrrelation SEparation Approach, COSEA)；第3节提出基于相关性分离的逻辑电路敏感门定位算法；第4节对一系列电路的实验结果进行分析；最后是结论。

2. 相关性分离方法

本文提出一种充分考虑信号相关性的逻辑电路失效率计算方法，该方法将电路划分为多个独立电路结构(Independent Circuit Structure, ICS)，并以这些独立电路结构为基本计算单元，分析它们的出错率及故障在电路中的传播情况，以此计算电路失效率。下面介绍此方法的原理与计算过程。

2.1 ICS分类与计算

逻辑电路中普遍存在大量扇出重汇聚结构。上游电路的故障信息会在扇出节点处沿扇出分支传播，若扇出支路重汇聚，则汇聚路径包含相关的故障信息，导致信号具有相关性。可在扇出支路上标记故障来源，根据分支标记溯源故障信息。以扇出节点为间隔将电路划分为不同电路模块。每个模块包含多个输入节点和一个输出节点，其中，输入为电路扇出节点或原始输入信号，输出为扇出节点或原始输出。每个电路模块代表的电路结构都不同，模块失效率相互独立，将这些模块称为独立电路结构。根据ICS输出节点的不同，将其分为两类：输出节点为扇出节点的ICS称为扇出相关电路C_FR，其对应的失效率PFR通过扇出源传播；输出为非扇出节点的ICS称为扇出无关电路C_FI，其失效率PFI表示以该节点为输出的ICS失效率。

对于非扇出节点j，以该节点为输出的ICS类型为C_FI，其对应失效率PFI计算如式(1)所示：

${\text{PF}}{{\text{I}}_j} = {\text{FPG}} + \sum\limits_{i = 1}^t {{\text{PF}}{{\text{I}}_i}}$

(1)

其中，t为其关键信号个数，PFI_i为第i个关键输入信号的PFI。

实际上，C_FI可转化为C_FR。转化后C_FR的失效率PFR等于转化前PFI的失效率，与此同时，C_FI(b)的PFI变为0，计算过程如式(2)所示：

$\left. {\begin{array}{*{20}{llllllllllllll}} {{{\text{C}}_{{\text{FR(b)}}}} \leftarrow {{\text{C}}_{{\text{FI}}(b)}}} \\ {{{\text{C}}_{{\text{FI}}(b)}} \leftarrow \varnothing} \end{array},\begin{array}{*{20}{c}} {{\text{PFR}}(b) = {\text{PFI}}(b)} \\ {{\text{PFI}}(b) = 0} \end{array}} \right\}$

(2)

式(2)表明，在检测到b点为扇出节点后，以b点为输出的C_FI(b)即转化为C_FR(b)。

2.2 节点信息定义与计算

电路节点的出错率受该节点输入锥中逻辑门的影响。将电路划分为不同的C_FR和C_FI，节点j的出错率可表示为EPN_j = function( ${\rm{C}}_{{\rm{FR}}_1}$ , ${\rm{C}}_{{\rm FR}_2 }$ , ···, ${\rm{C}}_{{\rm{FR}}_m }$ , ${\rm{C}}_{{\rm{FI}}_j }$ )。其中，m为节点j的输入锥中C_FR的个数， ${\rm{C}}_{{\rm{FI}}_j }$ 为以节点j为输出的C_FI。 ${\rm{C}}_{{\rm{FI}}_j }$ 对节点j的影响是必然的；而对于C_FR，其故障可能被屏蔽，也可能被传播至目标节点j，对该节点的出错率产生影响。因此，节点j的出错率EPN_j可表示为

${\text{EP}}{{\text{N}}_j} = {\text{PF}}{{\text{I}}_j} + \sum\limits_{j = 1}^{{\text{nc}}} {{\text{PF}}{{\text{R}}_j}}$

(3)

其中，nc为对节点j出错率有影响的C_FR的数目，PFR_j为 ${\rm{C}}_{{\rm{FR}}_j }$ 的失效率，PFI_j为 ${\rm{C}}_{{\rm{FI}}_j }$ 的失效率。

影响目标节点出错率的C_FR可能有多个，用U表示影响该节点的C_FR集合；影响目标节点的C_FI只有一个。通过以下节点信息可计算整个电路失效率：节点逻辑值LV、节点PFI、影响节点出错率的C_FR集合U。T表示此3类信息集合，即T={LV, PFI, U}。节点逻辑值LV由门输入信号和门类型决定；PFI可利用CSA方法计算，随着目标节点的变化，C_FI可转化为C_FR。

接下来介绍如何计算集合U。C_FR的故障信息通过其输出节点(扇出源)传播，当扇出分支在同一节点汇聚，由于故障信息已保存，在计算该节点出错率时可充分考虑到C_FR间的相关性。目标节点前驱逻辑门的输入信号中，若多个输入信号中存在相同的C_FR，则说明它们源于同一个C_FR。

图1描述了n输入与门输出节点的C_FR集合U的计算过程。设与门输入信号中‘1’的个数为n₁，‘0’的个数为n₀，n₁+n₀ = n。输入为‘1’的信号记为P₁，P₂, ···, $P_{n_1}$ ，对应节点信息为{ ${ T}_{P_1}$ , ${T}_{P_2}$ , ···, ${T}_{P_{n_1}}$ }，其中T_Pi={ ${\rm{LV}}_{P_i}$ , ${\rm{PFI}}_{P_i}$ , ${U}_{P_i }$ }；输入为‘0’的信号记为Q₁, Q₂, ···, $Q_{n_0}$ ，对应节点信息为{ ${T}_{Q_1}$ , ${T}_{Q_2}$ , ···, ${T}_{Q_{n_0}}$ }，其中， ${{T}}_{Q_i}$ ={ ${\rm{LV}}_{Q_i}$ , ${\rm{PFI}}_{Q_i}$ , ${{U}}_{Q_i}$ }。第P_i个‘1’信号节点信息的C_FR集合 ${U}_{P_i}$ = { ${\rm C}_{{\rm{FR}}P_i(1)}$ , ${\rm C}_{{\rm{FR}}P_i(2)}$ , ···, ${\rm C}_{{\rm {FR}}P_i (kP_i)}$ }，第Q_i个‘0’信号节点信息的C_FR集合 ${{U}}_{Q_i}$ = { ${\rm C}_{{\rm{FR}}Q_i(1)}$ , ${\rm C}_{{\rm{FR}}Q_i(2)}$ , ···, ${\rm C}_{{\rm{FR}}Q_i(kQ_i)}$ }，图1中各信号线上所列即为输入信号所对应的U。输出端的节点信息T_out = {LV_out, PFI_out, U_out}。

图 1 与门输出节点的集合U计算过程

下载: 全尺寸图片幻灯片

针对不同输入，分情况讨论输出节点的C_FR集合U的计算方法，表1列出了与门输出节点信息。同理，或门及非门的输出节点信息的计算方法与门类似，不再赘述。

表 1 与门输出节点信息

输入向量	LV_out	PFI_out	U_out
n₁=n, n₀=0	1	${\rm{PFI}}_{P_1}$ +···+ ${\rm{PFI}}_{P_{n-1}}$ +FPG	$U_{P_1}$ ∪ $U_{P_2}$ ∪···∪ $U_{Pn_1}$
n₁=n–1, n₀=1	0	${\rm{PFI}}_{Q_1}$ +FPG	$U_{Q_1}$ – $U_{P_1 }$ ∪···∪ $U_{Pn_1}$
n₀≥2	0	FPG	$U_{Q_1 }$ ∩···∩ $U_{Qn_0 }$ – $U_{P_1}$ ∪···∪ $U_{Pn_1}$

下载: 导出CSV

| 显示表格

(1) n₁ = n, n₀ = 0。如图1(a)所示，与门的所有输入都为1，其正常输出为1。此时，任意输入信号的C_FR出错，都将导致与门输出出错。因此，输出节点的U即为输入节点的U之并集，即 ${U_{{\rm{out}}}} = \bigcup\limits_{i = 1}^{n_1} {{U_{{{P}}_i}}}$ ；

(2) n₁ = n–1, n₀ = 1。如所示，与门输入中存在一个0信号，其正常输出为0。输入信号Q_i上的 ${\rm C}_{{\rm FR}Q_i(kQ_i)}$ 出错，将导致与门输出出错；但若 ${\rm C}_{{\rm FR}Q_i(kQ_i)}$ 也存在于其他输入1信号中，则 ${\rm C}_{{\rm FR}Q_i(kQ_i)}$ 出错将使输入1信号变为0，导致与门输出仍为0。因此，只有存在于输入0且不存在于任意输入1上的C_FR出错，才会导致与门输出出错。此时，输出节点的U为输入0信号的U减去所有输入1信号的U之并集，即 ${U_{{\rm{out}}}} = {U_{{{Q}}_1}} - \bigcup\limits_{j = 1}^{n1} {{U_{{{P}}_j}}}$ ；

(3) 1<n₀<n, n₁=n–n₀。如图1(c)所示，与门输入中存在多个0信号，其正常输出为0。与图1(b)情形类似，只有存在于所有输入0信号且不存在于任意输入1信号上的C_FR出错，才能导致门输出出错。所以输出节点的U为所有输入0信号的U之交集减去所有输入1信号的U之并集，即 ${U_{{\rm{out}}}} = \bigcap\limits_{i = 1}^{n_0} {{U_{{{Q}}_i}}} - \bigcup\limits_{j = 1}^{n_1} {{U_{{{P}}_j}}}$ 。

3. 敏感门定位算法

敏感门(Critical Gates, CG)指那些若发生故障便将直接导致电路失效的逻辑门。CG的故障不会被下游电路逻辑屏蔽，而是被传至电路原始输出端，或被下游存储单元捕获，从而导致电路失效。本节提出基于COSEA的敏感门定位算法，包括单个输入向量激励下电路的敏感门定位方法和多输入向量激励的敏感门定位方法(Vector Critical Gate Location Algorithm, VCGLA)。

3.1 向量敏感门定位算法

在单个特定向量激励下，若逻辑门故障导致电路失效，则称此逻辑门为向量敏感门(Vector Critical Gate, VCG)。对特定电路而言，不同输入向量对应不同的VCG集合。本节介绍如何计算电路的VCG集合。

类似地，将那些若发生故障便会导致电路失效的ICS称为敏感ICS，否则为非敏感ICS。显然，所有以电路原始输出节点为输出的C_FI都是敏感ICS。电路中的C_FR是否为敏感ICS则取决于电路的拓扑结构和当前输入向量。由于非敏感ICS的故障不会导致电路失效，所以该结构内部的逻辑门都不是向量敏感门；而敏感ICS结构内部的逻辑门也并非都是向量敏感门，可使用关键信号定位敏感ICS内部的向量敏感门。

VCGLA首先对输入的电路网表进行解析，针对每个单独的输入向量调用COSEA计算电路所有原始输出的节点信息T；其次，对所有输出节点的集合U进行分类，得到对电路输出有影响的敏感ICS集合；最后，对得到的ICS进行敏感门定位，使用反向搜索算法从ICS的输出向上游迭代，通过关键信号定位每个能影响到此ICS输出的逻辑门，将它们加入至敏感门集合。具体过程如算法1所示。

算法1 VCGLA算法
输入：电路网表文件，输入向量
输出：向量敏感门
1. 通过COSEA算法计算电路所有节点的T 　2. 计算C_FR集合的输出： ${U_{{\rm{CFR}}} } = \bigcup\limits_{i = 1}^{m_1} { {U_i} }$ //m₁表示电路中C_FR的　　数量
3. 计算C_FI集合的输出: ${U_{ {\rm{CFI} } } } = \bigcup\limits_{i = 1}^{m_2} { {{\rm{C}}_{ {\rm{FIi} } } } }$ //m₂表示电路中C_FI的　　数量
4. 创建VCG.set用于存储向量敏感门
5. FOR i =1 to n //n为U_CFR中的C_FR数量和U_CFI中的C_FI数量　　之和
6. 　Locate output gate of independent circuit structure
7.　Node number are added to VCG.set
8. 　Calculate the number of critical inputs of the node: k
9. 　　IF k == 0
10. 　　　GO to 5.
11. 　ELSE
12. 　　FOR j = 1 to k
13. 　　　IF the critical gate j is the primary input or fanout 　　　　　 node
14. 　　　　GO to 12.
15. 　　　ELSE
16. 　　　　GO to 7.
17. 　　　END IF
18. 　　END FOR
19. 　END IF
20. END FOR
21. END

下载: 导出CSV

| 显示表格

3.2 示例说明

本文以图2电路为例说明VCGLA具体计算过程。

图 2 示例电路

下载: 全尺寸图片幻灯片

步骤1　根据COSEA方法计算示例电路原始输出Out₁和Out₂的节点信息分别为T_out1 ={1, FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}和T_out2={1, 4FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}，则输出节点的U_CFR = ${\rm{U}}_{{\rm{out}}_1}$ ∪ ${\rm{U}}_{{\rm{out}}_2}$ = { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }, U_CFI = { ${\rm{C}}_{{\rm{FI}}({\rm{out}}_1) }$ , ${\rm{C}}_{{\rm{FI}}({\rm{out}}_2)}$ }。电路节点信息的具体计算过程如表2所示，其中No表示该节点处不需要进行C_FI和C_FR之间的转化。

表 2 示例电路节点信息计算过程

节点	输入	LV	C_FI→C_FR	PFI	U	T
G₁	11	1	No	PFI_G1=FPG	U_G1={Ø}	T_G1={1, FPG, Ø}
S₁	1	1	${\rm{PFR}}_{S_1}$ = ${\rm{PFI}}_{G_1}$ =FPG	${\rm{PFI}}_{S_1}$ =0	${{U}}_{S_1}$ = ${{U}}_{G_1}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_1)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{S_1}$ ={1, 0, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
G₂	10	0	No	${\rm{PFI}}_{G_2}$ =FPG	${{U}}_{G_2 }$ ={Ø}	${{T}}_{G_2}$ ={0, FPG, Ø}
G₃	1	0	No	${\rm{PFI}}_{G_3}$ =FPG	${{U}}_{G_3}$ = ${{U}}_{S_1}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{G_3}$ ={0, FPG, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
S₂	0	0	${\rm{PFR}}_{S_2}$ = ${\rm{PFI}}_{G_3}$ =FPG	${\rm{PFI}}_{S_2}$ =0	${{U}}_{S_2}$ = ${{U}}_{G_3}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_2)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }	${{T}}_{S_2}$ ={0, 0, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }}
G₄	0	1	No	${\rm{PFI}}_{G_4}$ =FPG	${{U}}_{G_4}$ = ${{U}}_{S_2 }$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }	${{T}}_{G_4 }$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }}
G₅	01	0	No	${\rm{PFI}}_{G_5 }$ =2FPG	${{U}}_{G_5}$ = ${{U}}_{S_2}$ – ${{U}}_{S_1}$ ={C_FR(S2)}	${{T}}_{G_5}$ ={0, 2FPG, ${\rm{C}}_{{\rm{FR}}(S_2)}$ }
G₆	10	1	No	${\rm{PFI}}_{G_6}$ =2FPG	${{U}}_{G_6}$ = ${{U}}_{G_4}$ – ${{U}}_{G_5}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{G_6}$ ={1, 2FPG, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
S₃	0	0	${\rm{PFR}}_{S_3}$ = ${\rm{PFI}}_{G_2 }$ =FPG	${\rm{PFI}}_{S_3}$ =0	${{U}}_{S_3}$ = ${{U}}_{G_2}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_3)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_3)}$ }	${{T}}_{S_3 }$ ={0, 0, ${\rm{C}}_{{\rm{FR}}(S_3)}$ }
S₄	1	1	${\rm{PFR}}_{S_4 }$ = ${\rm{PFI}}_{G_6}$ =2FPG	${\rm{PFI}}_{S_4}$ =0	${{U}}_{S_4}$ = ${{U}}_{G_6 }$ ∪ ${\rm{C}}_{{\rm{FR}}(S_4)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{S_4}$ ={1, 0,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
G₇	10	1	No	${\rm{PFI}}_{G_7 }$ =3FPG	${{U}}_{G_7}$ = ${{U}}_{S_4}$ – ${{U}}_{S_3}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{G_7}$ ={1, 3FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
S₅	1	1	${\rm{PFR}}_{S_5}$ = PFI_G7=3FPG	${\rm{PFI}}_{S_5}$ =0	$U_{S_5}$ = ${{U}}_{G_7}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_5)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , C_FR(S5)}	${{T}}_{S_5}$ ={1, 0,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}
G₈	11	1	No	${\rm{PFI}}_{G_8}$ = FPG	${{U}}_{G_8}$ = ${{U}}_{S_4}$ ∩ ${{U}}_{S_5}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4) }$ }	$T_{G_8 }$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1) }$ , ${\rm{C}}_{{\rm{FR}}(S_4) }$ }}
G₉	10	1	No	${\rm{PFI}}_{G_9}$ =4FPG	${{U}}_{G_9 }$ = ${{U}}_{S_5}$ - ${{U}}_{S_3}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }	${{T}}_{G_9 }$ ={1, 4FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ . ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}
Out₁	1	1	No	${\rm{PFI}}_{{\rm{Out}}_1}$ = ${\rm{PFI}}_{G_8}$ =FPG	${{U}}_{{\rm{Out}}_1}$ = ${{U}}_{G_8 }$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{{\rm{Out}}_1}$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
Out₂	1	1	No	${\rm{PFI}}_{{\rm{Out}}_2}$ = ${\rm{PFI}}_{G_9}$ =4FPG	${{U}}_{{\rm{Out}}_2}$ = ${{U}}_{G_9}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }	${{T}}_{{\rm{Out}}_2}$ ={1, 4FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}

下载: 导出CSV

| 显示表格

步骤2：定位每个敏感ICS内的向量敏感门，在此以C_FR(S₄)为例。C_FR(S₄)为U_CFR中的敏感ICS，首先找到输出节点G₆，将G₆加入向量敏感门集合；然后，向前追溯G₆的输入信号“10”，由于G₆是或门，所以输入‘1’为G₆的关键信号，该信号的前驱逻辑门为G₄，故将G₄添加至向量敏感门集合；最后，G₄的前驱为扇出节点S₂，停止此次迭代。因此， ${\rm{C}}_{{\rm{FR}}(S_4)}$ 的向量敏感门为G₄和G₆。分析所有敏感ICS可知，在输入向量为“1110”时，电路的向量敏感门集合为{G₁, G₄, G₆, G₇, G₈, G₉}。

3.3 电路敏感门定位算法

电路中被多数向量甚至所有向量都定位为向量敏感门的逻辑门，被称为电路敏感门(Circuit Critical Gate, CCG)，它们是容错设计的重点，对该部分逻辑门进行容错，能够大幅度提高电路可靠性。本节我们提出一种电路敏感门定位算法(Circuit Critical Gate Location Algorithm, CCGLA)，如算法2所示。

算法2 CCGLA算法
输入：电路网表文件，电路敏感门阈值Th
输出：所有敏感门集合
1. FOR i = 1 to N//每个电路的输入向量数N
2. 　Randomly generate an input vector V(i)
3. 　VCG.set(i) = CALL Location algorithm of critical gate
4. END FOR
5. FOR i = 1 to Num//电路总门数Num
6. 　Count the number of times G_i in VCG.set //G_i 为第i个门
7. 　Calculate the sensitivity of Gi : ${\text{G}}{{\text{S}}_{{G_i}}} = \dfrac{{{k_i}}}{N}$ //k_i是VCG.set 　　　的G_i编号
8. 　IF GS_Gi > Th
9. 　　Add G_i to CCG.set //所有敏感门集合
10. END IF
11. END FOR
12. END

下载: 导出CSV

| 显示表格

若逻辑门G为输入向量V的向量敏感门，则向量V为逻辑门G的敏感向量。定义逻辑门的敏感向量数占总输入向量空间的比值为该逻辑门的敏感度GS。设定敏感度阈值Th，认为电路敏感门即电路中敏感度超过阈值Th的逻辑门。例如，某电路的原始输入数为w，其输入向量空间大小为2^w。计算所有输入向量空间的敏感门集合分别为VCG₁, VCG₂, ···, VCG₂^w，若逻辑门G_i出现在其中k_i个向量敏感门集合中，则G_i的敏感度为k_i/2^w。随着输入数和电路规模的增大，计算所有输入向量的敏感门集合变得非常困难，因此，通常只选取部分向量计算对应敏感门。设N为选取的向量个数，k_i为第i个逻辑门G_i的敏感向量数，则G_i的敏感度为

${{\rm{GS}}_{{G_i}}} = \frac{{{k_i}}}{N}$

(4)

算法2为CCGLA算法总体框架，包含3步：(1)选取N个向量，计算这些向量对应的向量敏感门集合：VCG₁, VCG₂, ···, VCG_N；(2)计算电路中每一个逻辑门的敏感度；(3)设定阈值参数Th，比较逻辑门的敏感度与阈值Th的大小，超过阈值的门添加至电路敏感门集合。

4. 实验结果及分析

4.1 VCGLA效果验证

模拟实验在配备3.0 GHz微处理器和8 GB内存的计算机上进行。VCGLA, CCGLA和CGC方法都是基于MATLAB 2014a平台。ISCAS-85,89系列电路应用于文献[16-18,20]进一步验证提出的方法的准确性，其中文献[17,18]提出的CGC方法被广泛应用于电路敏感门定位，通过与其对比验证VCGLA的准确性与高效性。其中，CGC的变体方法共有6种，选取实验条件相似(单线程)的CGC-V1, V3, V4和V6方法进行对比。V1方法通过逐个检测电路每个单元的敏感性获取向量敏感门，准确率为100%，但因为对每个逻辑门进行检测耗时太高，无法用于大规模和超大规模电路的敏感门定位；相比之下，V3方法是一种快速的VCG定位方法，但准确性不高。V4和V6方法的准确性与定位速度介于以上两种方法之间。

考虑到CGC-V1, V4和V6方法所需时间较长，针对实验电路的每种方法各选择100个向量，用于定位电路的VCG集合。本实验中，由于CGC-V1方法能精准定位VCG集合，故以其为标准验证其他方法的准确性。针对ISCAS’85系列4个规模较小的电路，表3列举了VCGLA与CGC-V1, V3, V4和V6方法的比较结果。其中，avg.CG为100个相同随机向量激励下对应的敏感门数目的平均值，avg.err是它们与CGC-V1方法相比的误差平均值(即每个向量对应VCG误差的平均值)，如式(5)所示，max.err表示单个随机向量激励下敏感门集合误差的最大值，如式(6)所示，表3还列出了单个向量激励下定位对应VCG的平均计算时间。

表 3 VCGLA与CGC-V1, V3, V4和V6方法的比较

电路	CGC-V1		VCGLA			CGC-V3				CGC-V4				CGC-V6
电路	avg.CG	时间(s)	avg.CG	max.err	时间(s)	avg.CG	max.err	avg.err	时间(s)	avg.CG	max.err	avg.err	时间(s)	avg.CG	max.err	avg.err	时间(s)
C432	53.7	118.2	53.7	0	0.10	52.3	18	2.1	0.04	52.0	18.0	1.7	20.30	50.7	26.0	3.0	10.30
C499	302.8	428.5	302.8	0	0.31	308.3	138	49.3	0.15	280.9	138.0	21.9	111.00	280.9	138.0	21.9	32.40
C880	218.6	5.1	218.6	0	0.16	223.2	40	10.3	0.06	215.3	17.0	2.4	2.50	212.8	30.0	4.9	1.00
C1355	225.2	1597.5	225.2	0	0.24	228.0	82	29.4	0.10	211.9	82.0	13.3	383.10	211.9	82.0	13.3	84.80
Avg	200.1	537.3	200.1	0	0.20	203.0	69.5	22.8	0.09	190.0	63.8	9.8	129.20	189.1	69.0	10.8	32.10

下载: 导出CSV

| 显示表格

${\rm{avg.err}} = \frac{1}{{{m_1}}} \times \sum\limits_{i = 1}^{{m_1}} {\left| {{{\rm{VCG}}_{{\rm{CGC}} - V1(i)}} - {{\rm{VCG}}_{{\rm{Other}}(i)}}} \right|}$

(5)

$\begin{split} & {\rm{max.err}} = \max\left| {{{\rm{VCG}}_{{\rm{CGC}} - V1(i)}} - {{\rm{VCG}}_{{\rm{Other}}(i)}}} \right|,\\ & {i = 1,2, \cdots ,m_1} \end{split}$

(6)

其中，m₁是是激励向量数，VCG_CGC-V1(i)是由CGC-V1方法定位出的第i个输入向量的VCG, VCG_Other(i)表示其他几类方法计算出的第i个输入向量的VCG，在此统一表示。公式中的VCG差值实际是两个集合中不同的敏感门总数：相比CGC-V1方法定位的VCG集合，用其他方法定位的VCG集合中漏检与误检的敏感门。

表3中VCGLA的max.err列都为0表明VCGLA与CGC-V1方法找到的所有敏感门集合完全相同，表明本方法在定位向量敏感门时具有100%的准确性；而在定位速度上，VCGLA平均耗时0.2 s，相比CGC-V1的537.3 s快了3个数量级以上。CGC-V3是唯一一个在定位速度上稍快于VCGLA的方法，但由它定位的敏感门集合的最大误差平均值为69.5，且平均误差为22.8，是所列方法中准确性最低的。CGC-V4和V6的速度和准确性介于CGC-V1和V3之间，但都不及VCGLA。相关性分离方法通过将电路划分为多个ICS，再以ICS为基本单元分析故障传播及信号相关性影响，在保证准确性的前提下，大大简化了敏感门定位算法的迭代过程。

接下来使用VCGLA计算更大规模电路，衡量其计算大规模和超大规模电路时的有效性，结果如表4所示。考虑到CGC-V1, V4和V6方法的计算时间太长，已很难在合适的时间内定位这些大规模电路的敏感门，后续实验中我们仅使用VCGLA与CGC-V3方法定位敏感门。在表3和表4中，avg.err和max.err的含义相同，都是以CGC-V1方法结果为参考。只是表4中计算avg.err和max.err时，使用VCGLA方法的计算结果代替了CGC-V1方法结果，因为之前已证明，VCGLA方法与CGC-V1方法结果一致，且速度远快于后者。所选实验电路包括ISCAS’85, 89系列和ITC’99的10个电路。对于其中规模相对较小的电路，各选取10000个测试向量，随着电路规模的不断增大，考虑到定位时间的快速增长，所选取向量的数目逐渐减小。

表 4 VCGLA与CGC-V3方法定位大规模电路的敏感门

电路	门数	向量数	VCGLA		CGC-V3
电路	门数	向量数	avg.CG	时间(s)	avg.CG	时间(s)	avg.err	max.err
C1908	880	10000	404.8	0.34	405.0	0.14	0.4	85
C2670	1193	10000	449.2	0.46	468.6	0.25	20.9	191
C3540	1669	10000	500.3	0.59	439.6	0.43	113.0	425
C5315	2307	10000	809.2	0.99	824.0	0.40	15.0	73
C7552	3512	5000	1414.3	1.37	1488.3	0.72	74.6	256
S9234	5597	5000	2492.2	2.56	2540.7	1.94	51.9	176
S15850	9772	5000	5893.6	6.23	5952.6	6.90	61.3	134
S38417	22179	1000	14215.8	12.98	14914.3	11.45	706.2	862
b21	20027	1000	2780.1	28.07	2781.1	20.43	7.1	71
b22	29162	1000	4138.4	39.30	4141.6	28.60	13.6	118

下载: 导出CSV

| 显示表格

从表4可知，电路规模达到万门以上，VCGLA的计算耗时仍与CGC-V3方法相差不大，二者计算超大规模电路的向量敏感门速度都比较快。在实验中，随着电路规模的增长，VCGLA方法的计算耗时基本随逻辑门的数量呈线性增长，充分证明所提算法的可拓展性。因此，VCGLA可应用于更大规模电路的敏感门精准定位。

4.2 CCGLA效果验证

影响电路敏感门(CCG)定位性能的参数包括选取的向量数N和敏感度阈值Th。先考虑N的变化对CCGLA的影响。实验电路选取C7552的一个单输出子电路，输出节点编号为65。实验使用CCGLA计算当N为不同值时该子电路的敏感门集合，且对设定的每个N值，取Th的范围为0～1，步长为0.05。以N=50000时的计算结果为参考标准，比较N取其它值时对应21个不同Th的电路敏感门集合，并将此21组差值求和表示为该N值与最大N值(N=50000)的敏感门集合差，实验结果如图3所示。由图可知，当N<5000时，对应电路敏感门集合与参考标准差别逐渐减小；当N>5000时，随着N继续增大，敏感门集合差异已可忽略。实验说明，当N增大到一定程度即可用于准确定位CCG集合，无需遍历所有输入激励。实际上，对多数电路都有此结论。

图 3 N的变化对敏感门差异的影响

下载: 全尺寸图片幻灯片

Th是电路敏感度阈值，其值可影响CCG集的大小和质量：Th值若增大，则CCG集合中的元素减少，但CCG的敏感度更高；反之，则CCG数增加，但门的敏感度降低。定位CCG的目的是更高效地对电路进行容错加固。在此，假设改进后的CCG无错，对比容错前后的电路失效率，即可得到对该CCG集合容错后电路失效率的改善情况，以此评估Th对CCG定位及容错效果的影响。为保证失效率计算结果的准确性，使用MC模拟方法计算容错前后电路的失效率，模拟次数为5×10⁶。实验电路为ISCAS’89系列电路。

本实验分5步：(1)选定实验电路，使用MC方法计算实验电路失效率，将逻辑门的出错概率设为10^–4[15,20]；(2)设N=10000，针对Th值定位CCG集合；(3)计算容错后电路失效率，并对比容错前电路失效率；(4)改变Th大小，其范围为0～1，间隔步长为0.05；(5)重复步骤(3)和步骤(4)，分析Th对容错效果的影响。

实验结果如图4所示，图4(a)—4(f)分别描述不同电路下Th变化对电路失效率的影响。蓝色折线为针对不同Th值定位CCG集合并容错后得到的电路失效率；绿色直线为不进行容错的电路失效率。在图中，当Th为0时，所有输入激励对应的CCG都是容错对象，容错后电路失效率最低(可认为是0)；随着Th增大，容错对象减少，容错后电路失效率也逐渐增大；当Th为1时，只有极少数CCG为容错对象，容错后电路失效率最高。

图 4 敏感门容错前后电路失效率对比

下载: 全尺寸图片幻灯片

容错效果与容错代价是需综合考虑的两个重要指标。设FPC_a和FPC_b分别为容错后和容错前电路失效率，两者之间的改善比率定义为电路失效率改善率(Improvement Rate of Failure, IRF)，如式(7)所示；N_CCG为CCG集合的元素个数，N_CCG与电路总门数Num的比值称为电路敏感度比值(Circuit Critical Gate Rate, CCGR)，如式(8)所示。容错效果可用IRF衡量，IRF越大，说明容错效果越好；容错代价则用CCGR衡量，CCGR越小，则表明容错代价越小。定义容错效率(Fault Tolerance Efficiency, FTE)为IRF和CCGR的比值，如式(9)所示。FTE越大，表示对CCG集合容错的效率越高。

$\quad {\rm{IRF}} = \left| {\frac{{{{\rm{FPC}}_a} - {{\rm{FPC}}_b}}}{{{{\rm{FPC}}_b}}}} \right| \times 100\%$

(7)

$\quad {\rm{CCGR}} = \frac{{{N_{{\rm{CCG}}}}}}{{{\text{Num}}}} \times 100\%$

(8)

$\quad {\rm{FTE}} = \frac{{{\rm{IRF}}}}{{{\rm{CCGR}}}}$

(9)

图5中两条曲线分别描述了所选择的6个实验电路的IRF和CCGR随Th的变化情况，其中蓝色折线代表IRF，绿色折线代表CCGR。由图可知，IRF与CCGR都随Th的增大而减小。当电路设计人员以特定的IRF为电路设计目标时，可根据IRF选择Th值，从而得到对应的CCG集合，再对集合中的逻辑门进行容错；当以特定的CCGR为电路容错限制条件时，同样可选择对应Th值以得到CCG集合，再进行容错处理。

图 5 CCGR和IRF随Th的变化

下载: 全尺寸图片幻灯片

图6为实验电路的FTE随Th的变化情况。当Th为0时，FTE最小，随着Th增大，FTE也逐渐增大；当Th增大到一定程度时，FTE的增大开始变缓，甚至有减小趋势。从本文实验电路的结果可知：当Th为0.6～1的范围时，电路容错效率较高，但不同电路最佳容错点对应的Th会有差别。

图 6 FTE随Th的变化

下载: 全尺寸图片幻灯片

5. 结论

本文提出了一种基于相关性分离的逻辑电路敏感门定位算法。首先将整个电路分离成多个独立电路结构；再针对独立电路结构反向搜索定位特定输入向量的向量敏感门；最后进一步定位面向向量空间的电路敏感门。使用本文提出的敏感门定位算法，能精准定位对多数输入激励都敏感的逻辑门集合；而针对这些敏感门进行容错加固将有助于提升整个电路可靠性，同时能保证较低的容错开销。相比于其他敏感门定位算法，本文提出的算法既准确又高效，适用于定位大规模及超大规模电路的敏感门单元，以辅助高效容错设计。

图 1 与门输出节点的集合U计算过程

下载: 全尺寸图片幻灯片

图 2 示例电路

下载: 全尺寸图片幻灯片

图 3 N的变化对敏感门差异的影响

下载: 全尺寸图片幻灯片

图 4 敏感门容错前后电路失效率对比

下载: 全尺寸图片幻灯片

图 5 CCGR和IRF随Th的变化

下载: 全尺寸图片幻灯片

图 6 FTE随Th的变化

下载: 全尺寸图片幻灯片

表 1 与门输出节点信息

输入向量	LV_out	PFI_out	U_out
n₁=n, n₀=0	1	${\rm{PFI}}_{P_1}$ +···+ ${\rm{PFI}}_{P_{n-1}}$ +FPG	$U_{P_1}$ ∪ $U_{P_2}$ ∪···∪ $U_{Pn_1}$
n₁=n–1, n₀=1	0	${\rm{PFI}}_{Q_1}$ +FPG	$U_{Q_1}$ – $U_{P_1 }$ ∪···∪ $U_{Pn_1}$
n₀≥2	0	FPG	$U_{Q_1 }$ ∩···∩ $U_{Qn_0 }$ – $U_{P_1}$ ∪···∪ $U_{Pn_1}$

下载: 导出CSV

算法1 VCGLA算法
输入：电路网表文件，输入向量
输出：向量敏感门
1. 通过COSEA算法计算电路所有节点的T 　2. 计算C_FR集合的输出： ${U_{{\rm{CFR}}} } = \bigcup\limits_{i = 1}^{m_1} { {U_i} }$ //m₁表示电路中C_FR的　　数量
3. 计算C_FI集合的输出: ${U_{ {\rm{CFI} } } } = \bigcup\limits_{i = 1}^{m_2} { {{\rm{C}}_{ {\rm{FIi} } } } }$ //m₂表示电路中C_FI的　　数量
4. 创建VCG.set用于存储向量敏感门
5. FOR i =1 to n //n为U_CFR中的C_FR数量和U_CFI中的C_FI数量　　之和
6. 　Locate output gate of independent circuit structure
7.　Node number are added to VCG.set
8. 　Calculate the number of critical inputs of the node: k
9. 　　IF k == 0
10. 　　　GO to 5.
11. 　ELSE
12. 　　FOR j = 1 to k
13. 　　　IF the critical gate j is the primary input or fanout 　　　　　 node
14. 　　　　GO to 12.
15. 　　　ELSE
16. 　　　　GO to 7.
17. 　　　END IF
18. 　　END FOR
19. 　END IF
20. END FOR
21. END

下载: 导出CSV

表 2 示例电路节点信息计算过程

节点	输入	LV	C_FI→C_FR	PFI	U	T
G₁	11	1	No	PFI_G1=FPG	U_G1={Ø}	T_G1={1, FPG, Ø}
S₁	1	1	${\rm{PFR}}_{S_1}$ = ${\rm{PFI}}_{G_1}$ =FPG	${\rm{PFI}}_{S_1}$ =0	${{U}}_{S_1}$ = ${{U}}_{G_1}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_1)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{S_1}$ ={1, 0, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
G₂	10	0	No	${\rm{PFI}}_{G_2}$ =FPG	${{U}}_{G_2 }$ ={Ø}	${{T}}_{G_2}$ ={0, FPG, Ø}
G₃	1	0	No	${\rm{PFI}}_{G_3}$ =FPG	${{U}}_{G_3}$ = ${{U}}_{S_1}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{G_3}$ ={0, FPG, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
S₂	0	0	${\rm{PFR}}_{S_2}$ = ${\rm{PFI}}_{G_3}$ =FPG	${\rm{PFI}}_{S_2}$ =0	${{U}}_{S_2}$ = ${{U}}_{G_3}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_2)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }	${{T}}_{S_2}$ ={0, 0, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }}
G₄	0	1	No	${\rm{PFI}}_{G_4}$ =FPG	${{U}}_{G_4}$ = ${{U}}_{S_2 }$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }	${{T}}_{G_4 }$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_2)}$ }}
G₅	01	0	No	${\rm{PFI}}_{G_5 }$ =2FPG	${{U}}_{G_5}$ = ${{U}}_{S_2}$ – ${{U}}_{S_1}$ ={C_FR(S2)}	${{T}}_{G_5}$ ={0, 2FPG, ${\rm{C}}_{{\rm{FR}}(S_2)}$ }
G₆	10	1	No	${\rm{PFI}}_{G_6}$ =2FPG	${{U}}_{G_6}$ = ${{U}}_{G_4}$ – ${{U}}_{G_5}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ }	${{T}}_{G_6}$ ={1, 2FPG, ${\rm{C}}_{{\rm{FR}}(S_1)}$ }
S₃	0	0	${\rm{PFR}}_{S_3}$ = ${\rm{PFI}}_{G_2 }$ =FPG	${\rm{PFI}}_{S_3}$ =0	${{U}}_{S_3}$ = ${{U}}_{G_2}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_3)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_3)}$ }	${{T}}_{S_3 }$ ={0, 0, ${\rm{C}}_{{\rm{FR}}(S_3)}$ }
S₄	1	1	${\rm{PFR}}_{S_4 }$ = ${\rm{PFI}}_{G_6}$ =2FPG	${\rm{PFI}}_{S_4}$ =0	${{U}}_{S_4}$ = ${{U}}_{G_6 }$ ∪ ${\rm{C}}_{{\rm{FR}}(S_4)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{S_4}$ ={1, 0,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
G₇	10	1	No	${\rm{PFI}}_{G_7 }$ =3FPG	${{U}}_{G_7}$ = ${{U}}_{S_4}$ – ${{U}}_{S_3}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{G_7}$ ={1, 3FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
S₅	1	1	${\rm{PFR}}_{S_5}$ = PFI_G7=3FPG	${\rm{PFI}}_{S_5}$ =0	$U_{S_5}$ = ${{U}}_{G_7}$ ∪ ${\rm{C}}_{{\rm{FR}}(S_5)}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , C_FR(S5)}	${{T}}_{S_5}$ ={1, 0,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}
G₈	11	1	No	${\rm{PFI}}_{G_8}$ = FPG	${{U}}_{G_8}$ = ${{U}}_{S_4}$ ∩ ${{U}}_{S_5}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4) }$ }	$T_{G_8 }$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1) }$ , ${\rm{C}}_{{\rm{FR}}(S_4) }$ }}
G₉	10	1	No	${\rm{PFI}}_{G_9}$ =4FPG	${{U}}_{G_9 }$ = ${{U}}_{S_5}$ - ${{U}}_{S_3}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }	${{T}}_{G_9 }$ ={1, 4FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ . ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}
Out₁	1	1	No	${\rm{PFI}}_{{\rm{Out}}_1}$ = ${\rm{PFI}}_{G_8}$ =FPG	${{U}}_{{\rm{Out}}_1}$ = ${{U}}_{G_8 }$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }	${{T}}_{{\rm{Out}}_1}$ ={1, FPG,{ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ }}
Out₂	1	1	No	${\rm{PFI}}_{{\rm{Out}}_2}$ = ${\rm{PFI}}_{G_9}$ =4FPG	${{U}}_{{\rm{Out}}_2}$ = ${{U}}_{G_9}$ ={ ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }	${{T}}_{{\rm{Out}}_2}$ ={1, 4FPG, { ${\rm{C}}_{{\rm{FR}}(S_1)}$ , ${\rm{C}}_{{\rm{FR}}(S_4)}$ , ${\rm{C}}_{{\rm{FR}}(S_5)}$ }}

下载: 导出CSV

算法2 CCGLA算法
输入：电路网表文件，电路敏感门阈值Th
输出：所有敏感门集合
1. FOR i = 1 to N//每个电路的输入向量数N
2. 　Randomly generate an input vector V(i)
3. 　VCG.set(i) = CALL Location algorithm of critical gate
4. END FOR
5. FOR i = 1 to Num//电路总门数Num
6. 　Count the number of times G_i in VCG.set //G_i 为第i个门
7. 　Calculate the sensitivity of Gi : ${\text{G}}{{\text{S}}_{{G_i}}} = \dfrac{{{k_i}}}{N}$ //k_i是VCG.set 　　　的G_i编号
8. 　IF GS_Gi > Th
9. 　　Add G_i to CCG.set //所有敏感门集合
10. END IF
11. END FOR
12. END

下载: 导出CSV

表 3 VCGLA与CGC-V1, V3, V4和V6方法的比较

电路	CGC-V1		VCGLA			CGC-V3				CGC-V4				CGC-V6
电路	avg.CG	时间(s)	avg.CG	max.err	时间(s)	avg.CG	max.err	avg.err	时间(s)	avg.CG	max.err	avg.err	时间(s)	avg.CG	max.err	avg.err	时间(s)
C432	53.7	118.2	53.7	0	0.10	52.3	18	2.1	0.04	52.0	18.0	1.7	20.30	50.7	26.0	3.0	10.30
C499	302.8	428.5	302.8	0	0.31	308.3	138	49.3	0.15	280.9	138.0	21.9	111.00	280.9	138.0	21.9	32.40
C880	218.6	5.1	218.6	0	0.16	223.2	40	10.3	0.06	215.3	17.0	2.4	2.50	212.8	30.0	4.9	1.00
C1355	225.2	1597.5	225.2	0	0.24	228.0	82	29.4	0.10	211.9	82.0	13.3	383.10	211.9	82.0	13.3	84.80
Avg	200.1	537.3	200.1	0	0.20	203.0	69.5	22.8	0.09	190.0	63.8	9.8	129.20	189.1	69.0	10.8	32.10

下载: 导出CSV

表 4 VCGLA与CGC-V3方法定位大规模电路的敏感门

电路	门数	向量数	VCGLA		CGC-V3
电路	门数	向量数	avg.CG	时间(s)	avg.CG	时间(s)	avg.err	max.err
C1908	880	10000	404.8	0.34	405.0	0.14	0.4	85
C2670	1193	10000	449.2	0.46	468.6	0.25	20.9	191
C3540	1669	10000	500.3	0.59	439.6	0.43	113.0	425
C5315	2307	10000	809.2	0.99	824.0	0.40	15.0	73
C7552	3512	5000	1414.3	1.37	1488.3	0.72	74.6	256
S9234	5597	5000	2492.2	2.56	2540.7	1.94	51.9	176
S15850	9772	5000	5893.6	6.23	5952.6	6.90	61.3	134
S38417	22179	1000	14215.8	12.98	14914.3	11.45	706.2	862
b21	20027	1000	2780.1	28.07	2781.1	20.43	7.1	71
b22	29162	1000	4138.4	39.30	4141.6	28.60	13.6	118

下载: 导出CSV

参考文献(20)

[1]	OATES A S and CHEUNG K P. Reliability of nanoelectronic devices[M]. VAN DE VOORDE M, PUERS R, BALDI L, et al. Nanoelectronics: Materials, Devices, Applications. Hoboken: Wiley, 2017: 317–330.
[2]	RAMIN R, MICHAEL N, and HU X S. Low-cost sequential logic circuit design considering single event double-node upsets and single event transients[C]. 2021 IEEE 39th International Conference on Computer Design (ICCD), Storrs, USA, 2021: 178–185.
[3]	TANG Du, HE Chaohui, LI Yonghong, et al. Soft error reliability in advanced CMOS technologies-trends and challenges[J]. Science China Technological Sciences, 2014, 57(9): 1846–1857. doi: 10.1007/s11431-014-5565-6
[4]	VASILYEV N O, ZAPLETINA M A, and IVANOVA G A. The analysis of logic resynthesis methods to increase the fault tolerance of combinational circuits for single failures[C]. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), St. Petersburg, Russia, 2021: 2050–2053.
[5]	SIKANDER K, ZHAN Suoyue, and CHEN Chunhong. An analytical model for circuit reliability estimation[C]. 2021 IEEE International Midwest Symposium on Circuits and Systems (MWSCAS), Lansing, USA, 2021: 84–87.
[6]	LIU Baojun and CAI Li. Monte Carlo reliability model for single-event transient on combinational circuits[J]. IEEE Transactions on Nuclear Science, 2017, 64(12): 2933–2937. doi: 10.1109/TNS.2017.2772267
[7]	KRISHNASWAMY S, VIAMONTES G F, MARKOV I L, et al. Probabilistic transfer matrices in symbolic reliability analysis of logic circuits[J]. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(1): 1–35. doi: 10.1145/1297666.1297674
[8]	XIAO Jie, LOU Jungang, and JIANG Jianhui. A fast and effective sensitivity calculation method for circuit input vectors[J]. IEEE Transactions on Reliability, 2019, 68(3): 938–953. doi: 10.1109/TR.2019.2897455
[9]	HAN Jie, CHEN Hao, BOYKIN E, et al. Reliability evaluation of logic circuits using probabilistic gate models[J]. Microelectronics Reliability, 2011, 51(2): 468–476. doi: 10.1016/j.microrel.2010.07.154
[10]	SINGH N S S, HAMID N H, ASIRVADAM V S, et al. Evaluation of circuit reliability based on distribution of different signal input patterns[C]. IEEE International Colloquium on Signal Processing and its Applications, Malacca, Malaysia: 2012: 5–9.
[11]	CHEN Chunhong and XIAO Ran. A fast model for analysis and improvement of gate-level circuit reliability[J]. Integration, 2015, 50: 107–115. doi: 10.1016/j.vlsi.2015.02.005
[12]	陈雷, 张瑶伟, 王硕, 等. FPGA三模冗余工具的关键技术与发展[J]. 电子与信息学报, 2022, 44(6): 2230–2244. doi: 10.11999/JEIT210330 CHEN Lei, ZHANG Yaowei, WANG Shuo, et al. Key technology and development of triple modular redundancy tool for FPGA[J]. Journal of Electronics &Information Technology, 2022, 44(6): 2230–2244. doi: 10.11999/JEIT210330
[13]	IBRAHIM W, SHOUSHA M, and CHINNECK J W. Accurate and efficient estimation of logic circuits reliability bounds[J]. IEEE Transactions on Computers, 2015, 64(5): 1217–1229. doi: 10.1109/tc.2014.2315633
[14]	XIAO Jie, SHI Zhanhui, ZHU Weidong, et al. Uniform non-Bernoulli sequences oriented locating method for reliability-critical gates[J]. Tsinghua Science and Technology, 2021, 26(1): 24–35. doi: 10.26599/TST.2019.9010045
[15]	XIAO Jie, SHI Zhanhui, YANG Xuhua, et al. BM-RCGL: Benchmarking approach for localization of reliability-critical gates in combinational logic blocks[J]. IEEE Transactions on Computers, 2022, 71(5): 1063–1076. doi: 10.1109/TC.2021.3071253
[16]	IBRAHIM W. Identifying the worst reliability input vectors and the associated critical logic gates[J]. IEEE Transactions on Computers, 2016, 65(6): 1748–1760. doi: 10.1109/TC.2015.2458868
[17]	IBRAHIM W and AMER H. Critical nodes count algorithm for accurate input vectors reliability ranking[C]. Proceedings of the Summer Computer Simulation Conference, Montreal, Canada, 2016: 19.
[18]	IBRAHIM W and IBRAHIM H. Multithreaded and reconvergent aware algorithms for accurate digital circuits reliability estimation[J]. IEEE Transactions on Reliability, 2019, 68(2): 514–525. doi: 10.1109/TR.2018.2876475
[19]	CAI Shuo, HE Binyong, WU Sicheng, et al. An accurate estimation algorithm for failure probability of logic circuits using correlation separation[J]. Journal of Electronic Testing, 2022, 38(2): 165–180. doi: 10.1007/s10836-022-05996-y
[20]	XIAO Jie, CHEN Wenbo, LOU Jungang, et al. Identifying reliability-critical primary inputs of combinational circuits based on the model of gate-sensitive attributes[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(11): 4708–4720. doi: 10.1109/TCAD.2022.3142194

施引文献

资源附件(0)

访问统计

图(6) / 表(6)

计量

文章访问数: 369
HTML全文浏览量: 193
PDF下载量: 72
被引次数: 0

1. 引言
2. 相关性分离方法
2.1 ICS分类与计算
2.2 节点信息定义与计算
3. 敏感门定位算法
3.1 向量敏感门定位算法
3.2 示例说明
3.3 电路敏感门定位算法
4. 实验结果及分析
4.1 VCGLA效果验证
4.2 CCGLA效果验证
5. 结论

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于相关性分离的逻辑电路敏感门定位算法

doi: 10.11999/JEIT230012

通讯作者:
蔡烁　caishuo@csust.edu.cn

计量

Critical Gates Localization of Logic Circuits Based on Correlation Separation

1. 引言

2. 相关性分离方法

2.1 ICS分类与计算

2.2 节点信息定义与计算

3. 敏感门定位算法

3.1 向量敏感门定位算法

3.2 示例说明

3.3 电路敏感门定位算法

4. 实验结果及分析

4.1 VCGLA效果验证

4.2 CCGLA效果验证

5. 结论

计量

目录

1. 引言

2. 相关性分离方法

2.1 ICS分类与计算

2.2 节点信息定义与计算

3. 敏感门定位算法

3.1 向量敏感门定位算法

3.2 示例说明

3.3 电路敏感门定位算法

4. 实验结果及分析

4.1 VCGLA效果验证

4.2 CCGLA效果验证

5. 结论

留言板

基于相关性分离的逻辑电路敏感门定位算法

doi: 10.11999/JEIT230012

通讯作者: 蔡烁 caishuo@csust.edu.cn

计量

出版历程

Critical Gates Localization of Logic Circuits Based on Correlation Separation

1. 引言

2. 相关性分离方法

2.1 ICS分类与计算

2.2 节点信息定义与计算

3. 敏感门定位算法

3.1 向量敏感门定位算法

3.2 示例说明

3.3 电路敏感门定位算法

4. 实验结果及分析

4.1 VCGLA效果验证

4.2 CCGLA效果验证

5. 结论

计量

出版历程

目录

1. 引言

2. 相关性分离方法

2.1 ICS分类与计算

2.2 节点信息定义与计算

3. 敏感门定位算法

3.1 向量敏感门定位算法

3.2 示例说明

3.3 电路敏感门定位算法

4. 实验结果及分析

4.1 VCGLA效果验证

4.2 CCGLA效果验证

5. 结论

通讯作者:
蔡烁　caishuo@csust.edu.cn