高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

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

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

蔡烁, 何辉煌, 余飞, 尹来容, 刘洋. 基于相关性分离的逻辑电路敏感门定位算法[J]. 电子与信息学报, 2024, 46(1): 362-372. doi: 10.11999/JEIT230012
引用本文: 蔡烁, 何辉煌, 余飞, 尹来容, 刘洋. 基于相关性分离的逻辑电路敏感门定位算法[J]. 电子与信息学报, 2024, 46(1): 362-372. doi: 10.11999/JEIT230012
CAI Shuo, HE Huihuang, YU Fei, YIN Lairong, LIU Yang. Critical Gates Localization of Logic Circuits Based on Correlation Separation[J]. Journal of Electronics & Information Technology, 2024, 46(1): 362-372. doi: 10.11999/JEIT230012
Citation: CAI Shuo, HE Huihuang, YU Fei, YIN Lairong, LIU Yang. Critical Gates Localization of Logic Circuits Based on Correlation Separation[J]. Journal of Electronics & Information Technology, 2024, 46(1): 362-372. doi: 10.11999/JEIT230012

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

doi: 10.11999/JEIT230012
基金项目: 国家自然科学基金(62172058),湖南省自然科学基金(2022JJ10052, 2022JJ30624)
详细信息
    作者简介:

    蔡烁:男,博士,副教授,研究方向为容错计算、电路系统可靠性等

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

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

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

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

    通讯作者:

    蔡烁 caishuo@csust.edu.cn

  • 中图分类号: TN431.2; TN406

Critical Gates Localization of Logic Circuits Based on Correlation Separation

Funds: The National Natural Science Foundation of China (62172058), The Natural Science Foundation of Hunan Province (2022JJ10052, 2022JJ30624)
  • 摘要: 随着CMOS器件特征尺寸进入纳米量级,因高能粒子辐射等造成的电路失效问题日益严重,给电路可靠性带来严峻挑战。现阶段,准确评估集成电路可靠性,并以此为依据对电路进行容错加固,以提高电路系统可靠性变得刻不容缓。然而,由于逻辑电路中存在大量扇出重汇聚结构,由此引发的信号相关性导致可靠性评估与敏感单元定位面临困难。该文提出一种基于相关性分离的逻辑电路敏感门定位算法。先将电路划分为多个独立电路结构(ICS);以ICS为基本单元分析故障传播及信号相关性影响;再利用相关性分离后的电路模块和反向搜索算法精准定位逻辑电路敏感门单元;最后综合考虑面向输入向量空间的敏感门定位及针对性容错加固。实验结果表明,所提算法能准确、高效地定位逻辑电路敏感单元,适用于大规模及超大规模电路的可靠性评估与高效容错设计。
  • 图  1  与门输出节点的集合U计算过程

    图  2  示例电路

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

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

    图  5  CCGR和IRF随Th的变化

    图  6  FTE随Th的变化

    表  1  与门输出节点信息

    输入向量LVoutPFIoutUout
    n1=n, n0=01${\rm{PFI}}_{P_1} $+···+${\rm{PFI}}_{P_{n-1}} $+FPG$ U_{P_1} $∪$U_{P_2} $∪···∪$ U_{Pn_1}$
    n1=n–1, n0=10${\rm{PFI}}_{Q_1} $+FPG$ U_{Q_1} $ – $ U_{P_1 } $∪···∪$U_{Pn_1} $
    n0≥20FPG$ U_{Q_1 } $∩···∩$ U_{Qn_0 } $ – $ U_{P_1} $∪···∪$U_{Pn_1} $
    下载: 导出CSV
    算法1 VCGLA算法
     输入:电路网表文件,输入向量
     输出:向量敏感门
     1. 通过COSEA算法计算电路所有节点的T
     2. 计算CFR集合的输出:${U_{{\rm{CFR}}} } = \bigcup\limits_{i = 1}^{m_1} { {U_i} }$ //m1表示电路中CFR
      数量
     3. 计算CFI集合的输出: ${U_{ {\rm{CFI} } } } = \bigcup\limits_{i = 1}^{m_2} { {{\rm{C}}_{ {\rm{FIi} } } } }$//m2表示电路中CFI
      数量
     4. 创建VCG.set用于存储向量敏感门
     5. FOR i =1 to n //nUCFR中的CFR数量和UCFI中的CFI数量
      之和
     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  示例电路节点信息计算过程

    节点输入LVCFICFRPFIUT
    G1111NoPFIG1=FPGUG1={Ø}TG1={1, FPG, Ø}
    S111${\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)} $}
    G2100No${\rm{PFI}}_{G_2} $=FPG${{U}}_{G_2 } $={Ø}${{T}}_{G_2} $={0, FPG, Ø}
    G310No${\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)} $}
    S200${\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)} $}}
    G401No${\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)} $}}
    G5010No${\rm{PFI}}_{G_5 }$=2FPG${{U}}_{G_5} $=${{U}}_{S_2} $–${{U}}_{S_1} $={CFR(S2)}${{T}}_{G_5} $={0, 2FPG, ${\rm{C}}_{{\rm{FR}}(S_2)} $}
    G6101No${\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)} $}
    S300${\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)}$}
    S411${\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)} $}}
    G7101No${\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)} $}}
    S511${\rm{PFR}}_{S_5} $= PFIG7=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)} $, CFR(S5)}${{T}}_{S_5} $={1, 0,{${\rm{C}}_{{\rm{FR}}(S_1)} $, ${\rm{C}}_{{\rm{FR}}(S_4)} $, ${\rm{C}}_{{\rm{FR}}(S_5)} $}}
    G8111No${\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) } $}}
    G9101No${\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)} $}}
    Out111No${\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)} $}}
    Out211No${\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 Gi in VCG.set //Gi 为第i个门
     7.  Calculate the sensitivity of Gi : $ {\text{G}}{{\text{S}}_{{G_i}}} = \dfrac{{{k_i}}}{N} $//ki是VCG.set
        的Gi编号
     8.  IF GSGi > Th
     9.   Add Gi to CCG.set //所有敏感门集合
     10. END IF
     11. END FOR
     12. END
    下载: 导出CSV

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

    电路CGC-V1VCGLACGC-V3CGC-V4CGC-V6
    avg.CG时间(s)avg.CGmax.err时间(s)avg.CGmax.erravg.err时间(s)avg.CGmax.erravg.err时间(s)avg.CGmax.erravg.err时间(s)
    C43253.7118.253.700.1052.3182.10.0452.018.01.720.3050.726.03.010.30
    C499302.8428.5302.800.31308.313849.30.15280.9138.021.9111.00280.9138.021.932.40
    C880218.65.1218.600.16223.24010.30.06215.317.02.42.50212.830.04.91.00
    C1355225.21597.5225.200.24228.08229.40.10211.982.013.3383.10211.982.013.384.80
    Avg200.1537.3200.100.20203.069.522.80.09190.063.89.8129.20189.169.010.832.10
    下载: 导出CSV

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

    电路门数向量数VCGLACGC-V3
    avg.CG时间(s)avg.CG时间(s)avg.errmax.err
    C190888010000404.80.34405.00.140.485
    C2670119310000449.20.46468.60.2520.9191
    C3540166910000500.30.59439.60.43113.0425
    C5315230710000809.20.99824.00.4015.073
    C7552351250001414.31.371488.30.7274.6256
    S9234559750002492.22.562540.71.9451.9176
    S15850977250005893.66.235952.66.9061.3134
    S3841722179100014215.812.9814914.311.45706.2862
    b212002710002780.128.072781.120.437.171
    b222916210004138.439.304141.628.6013.6118
    下载: 导出CSV
  • [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
  • 加载中
图(6) / 表(6)
计量
  • 文章访问数:  142
  • HTML全文浏览量:  98
  • PDF下载量:  45
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-01-10
  • 修回日期:  2023-04-12
  • 网络出版日期:  2023-04-20
  • 刊出日期:  2024-01-17

目录

    /

    返回文章
    返回