A Testability Evaluation Method Based on Reconvergent Fan-Out
-
摘要: 随着电路规模和复杂度的不断提升，可测性分析已成为电路设计与测试阶段中评估电路质量与优化测试点配置的关键环节。然而，现有方法在处理信号相关性与扇出重汇聚结构时，普遍存在精度不足与计算开销较大的问题，难以兼顾效率与准确性。为此，该文提出一种基于扇出重汇聚的可测性评估方法。该方法通过解析电路拓扑识别扇出重汇聚区域，构建结构相关的加权可测性计算模型，并实现了高效的可测性分析算法框架，以在保证精度的同时提升计算效率。实验结果表明，该文方法在可控性预测中均方根误差平均降低约25%，确保精度的同时，计算时间平均加速7倍，在故障覆盖率预测以及排序一致性检测中亦表现优异。Abstract:
Objective As the scale and structural complexity of integrated circuits continue to increase, accurate testability evaluation becomes essential for Trojan detection, fault diagnosis, and test-point optimization in modern Design-for-Testability (DFT) flows. Metrics such as controllability, observability, and fault coverage depend on reliable probabilistic modeling of signal propagation. However, existing analytical and learning-based approaches often lose accuracy in circuits with dense Reconvergent Fan-Out (RFO) structures, where strong signal correlation invalidates classical independence assumptions and causes substantial estimation bias. Although several enhanced techniques attempt to incorporate structural information, many have high computational cost or limited scalability in deeper or highly reconvergent logic networks. This work addresses these limitations by proposing a testability evaluation method that incorporates RFO structural characteristics to improve modeling accuracy while maintaining practical computational efficiency. Methods The proposed approach starts with a structural analysis algorithm that identifies RFO regions through topological traversal of the circuit. A dedicated RFO recognition mechanism maps each root fan-out node to its corresponding RFO nodes, capturing the structural dependencies that govern correlated signal behavior and providing the basis for accurate probabilistic modeling. Building on this structural extraction, a weighted conditional probability model is formulated to correct testability distortion in reconvergent regions. Unlike previous optimization schemes, the weighting strategy assigns influence-based weights derived from the contribution of each root node to the target node, yielding probability estimates that more accurately reflect actual testability behavior. An efficient computational framework is also developed to integrate conditional probability propagation and weight selection into a single topological traversal process, thereby maintaining low algorithmic complexity while improving accuracy. Results and Discussions The proposed method is evaluated on representative benchmark circuits from the ISCAS85, ISCAS89, ITC99, and EPFL suites. Performance is assessed in terms of controllability accuracy, ordering consistency, fault coverage estimation, and runtime efficiency. For controllability prediction, the method achieves an average RMSE of 0.0568, which corresponds to an average reduction of 25% relative to existing techniques, as reported in Table 2 . Ordering consistency also improves, with the average Spearman correlation coefficient reaching 0.935, outperforming existing techniques. Fault coverage estimation shows similarly strong performance, with an average relative error of 3.64%, which is lower than that of previously reported methods, as shown inTable 1 . Runtime analysis further indicates that the proposed framework maintains practical computational efficiency. Across all benchmark circuits, the method achieves an average speedup of 7× while preserving high accuracy, as illustrated inFigure 5 .Conclusions This work addresses the degradation in testability evaluation accuracy caused by RFO structures in integrated circuits by proposing a reconvergent-fan-out-aware testability analysis method. The presented RFO structure identification algorithm extracts reconvergent information at the topological level and establishes explicit mappings between root nodes and RFO nodes. On this structural basis, a weighted conditional probability model is constructed to mitigate probability distortion induced by signal correlation in RFO regions. An efficient computational framework is further developed to integrate the full computation into a streamlined traversal-based process. Experimental results show that the proposed technique achieves accurate fitting of controllability RMSE and ordering consistency relative to simulation-based ground truth. In testability estimation, the predicted fault coverage values also closely match the simulation results. While maintaining high accuracy, the method also has low computational overhead. -
1 扇出重汇聚识别算法
输入：sorted_list - 拓扑排序列表 输出：RFO_info - 扇出重汇聚结构信息 for each node v in sorted_list do if fan-out >1 then /* find candidate root node*/ create struct_info(v) /*set Si*/ else if struct_info(v) repeat then /*candidate RFON*/ create candidate root set RS_v /*set RSi*/ for each root r in RS_v do if struct_info(r) ∩ RS_v is not empty then delete r from RS_v /* follow rule 1*/ for each RFON r in node v RFO structure do if RS_r ∩ struct_info(v) is not empty then add r into RS_v /* follow rule 2*/ propagate_struct_info(v) return RFO_info 
下载: 导出CSV
2 基于扇出重汇聚结构的可测性算法
输入：sorted_list - 拓扑排序列表
RFO_info - 已识别的结构信息输出：可控性 C(v) and 可观测性 O(v) for each node v in sorted_list do /*calculate controllability*/ if v is a primary input then C(v) ← 0.5 /*initialize primary input*/ else if v is RFON then C(v) ← RFON_based_ctrl_cal(v) /*follow formula 6*/ else C(v) ← cop_ctrl_calculate(v) /*follow rules of 图1*/ create/propagate conditional_probability_info(v) for each node v in invert_sorted_list do /*calculate
observability*/if v is a primary output then O(v) ← 1 /*initialize primary output*/ else if v is in RFO structure then O(v) ← RFON_based_obsv_cal(v) /*follow formula 6*/ create/propagate conditional_probability_info(v) else O(v) ← cop_obsv_calculate(v) /*follow rules of 图1*/ return {C(v), O(v)} for all v
下载: 导出CSV
表 1 电路基本信息及故障覆盖率相对误差对比表
Circuit Gate_
numbMax_
numbFault_
coverage(%)FC_RE(%) 文献[5] 文献[7] 文献[12] RFO s1238 631 16 94.29 0.79 0.87 1.62 0.85 s3384 1868 3 92.71 1.19 1.22 0.9 1.52 s9234 6173 20 82.16 1.75 2.75 11.12 0.5 s13207 9262 35 91 2 0.87 0.18 0.64 s35932 17793 2 89.25 1.95 2.19 3.14 2.23 s38584 22764 17 93.01 1.13 1.58 1.63 0.01 c1355 1038 33 96.88 2.86 2.81 3.1 2.43 c6288 4544 3 99.37 0.63 0.63 0.63 0.08 b14 10926 67 87.08 18.42 1.37 4.55 0.36 b17 36897 37 69.78 13.98 13.76 15.93 13.12 b18 85724 101 75.95 1.09 2.16 21.04 2.17 b21 22545 69 87.39 18.71 0.52 2.67 0.31 adder 1279 3 89.18 12.13 12.13 12.1 12.13 arbiter 6743 8 35.15 11.93 12.13 19.23 10.63 dec 309 0 98.32 1.71 1.71 1.71 1.71 max 3350 6 47.72 4.84 4.83 3.6 7.37 voter 13698 8 94.49 5.81 5.81 5.8 5.82 Average 5.94 3.96 6.41 3.64
下载: 导出CSV
表 2 可控性值RMSE与斯皮尔曼秩相关系数对比表
circuit RMSE ρ 文献[5] 文献[7] 文献[12] RFO 文献[5]_ρ 文献[7]_ρ 文献[12]_ρ RFO_ρ s1238 0.0127 0.0073 0.0570 0.0086 0.9956 0.9962 0.9578 0.9968 s3384 0.0303 0.0192 0.0354 0.0187 0.8832 0.8990 0.7877 0.9144 s9234 0.0311 0.0183 0.1894 0.0200 0.8480 0.8758 0.4102 0.8732 s13207 0.0408 0.0250 0.2164 0.0245 0.8481 0.8692 0.2600 0.8858 s35932 0.0595 0.0437 0.0651 0.0378 0.8223 0.8615 0.7983 0.8663 s38584 0.0278 0.0160 0.1141 0.0169 0.9396 0.9601 0.7741 0.9680 c1355 0.0644 0.0439 0.1196 0.0218 0.9179 0.9424 0.8795 0.9474 c6288 0.0984 0.0719 0.1958 0.0470 0.8511 0.8969 0.5078 0.9630 b14 0.0433 0.0410 0.0624 0.0409 0.9444 0.9447 0.9272 0.9452 b17 0.0193 0.0189 0.0737 0.0189 0.9754 0.9763 0.9034 0.9773 b18 0.0434 0.0278 0.079 0.0414 0.9663 0.9806 0.9201 0.9712 b21 0.0491 0.0425 0.0599 0.0442 0.9340 0.9407 0.9227 0.9400 adder 0.0337 0.0204 0.0532 0.0015 0.8967 0.9013 0.8647 0.9265 arbiter 0.0053 0.0045 0.0185 0.0034 0.9902 0.9894 0.9782 0.9889 dec 0.5216 0.5216 0.5194 0.5216 1.0000 1.0000 0.8688 1.0000 max 0.0294 0.0206 0.0371 0.0184 0.9059 0.9170 0.8925 0.9178 voter 0.0935 0.0824 0.0744 0.0796 0.7811 0.8033 0.8609 0.8132 Average 0.0708 0.0603 0.1159 0.0568 0.9118 0.9267 0.7949 0.935
下载: 导出CSV
-
[1] WANG L T, WU Chengwen, and WEN Xiaoqing. VLSI Test Principles and Architectures: Design for Testability[M]. San Francisco: Morgan Kaufmann Publishers, 2006: 1–34. [2] POMERANZ I. Diagnostic test point insertion and test compaction[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2023, 31(2): 276–285. doi: 10.1109/TVLSI.2022.3218924. [3] KIM J, KIM H, PARK J, et al. A new test point insertion using weight adjusted grouping[J]. IEEE Access, 2025, 13: 95934–95944. doi: 10.1109/ACCESS.2025.3575800. [4] GOLDSTEIN L H and THIGPEN E L. SCOAP: Sandia controllability/observability analysis program[C]. The 17th Design Automation Conference, Minneapolis, USA, 1980: 190–196. doi: 10.1145/800139.804528. [5] BRGLEZ F. On testability analysis of combinational networks[J]. IEEE International Symposium on Circuits and Systems, 1984, 1: 221–225. [6] SCHLITT L, AGNIHOTRI P, KALLA P, et al. Silicon photonic test-point selection by integrating design parameters with hypergraph partitioning[C]. 2025 IEEE International Test Conference, San Diego, USA, 2025: 262–271. doi: 10.1109/ITC58126.2025.00033. [7] CHANG A C C, HUANG R H M, and WEN C H P. CASSER: A closed-form analysis framework for statistical soft error rate[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013, 21(10): 1837–1848. doi: 10.1109/TVLSI.2012.2220386. [8] CHEN Liang, EBRAHIMI M, and TAHOORI M B. CEP: Correlated error propagation for hierarchical soft error analysis[J]. Journal of Electronic Testing, 2013, 29(2): 143–158. doi: 10.1007/s10836-013-5365-0. [9] CHEN Chunhong and ZHAN Suoyue. A hybrid method for signal probability estimation with combinational circuits[C]. 2022 IEEE Asia Pacific Conference on Circuits and Systems, Shenzhen, China, 2022: 472–475. doi: 10.1109/APCCAS55924.2022.10090301. [10] JAHANIRAD H. CC-SPRA: Correlation coefficients approach for signal probability-based reliability analysis[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2019, 27(4): 927–939. doi: 10.1109/TVLSI.2018.2886027. [11] WU Nan, LI Yingjie, YANG Hang, et al. Survey of machine learning for software-assisted hardware design verification: Past, present, and prospect[J]. ACM Transactions on Design Automation of Electronic Systems, 2024, 29(4): 59. doi: 10.1145/3661308. [12] IMMANUEL J and MILLICAN S K. Calculating signal controllability using neural networks: Improvements to testability analysis and test point insertion[C]. The 2020 IEEE 29th North Atlantic Test Workshop, Albany, USA, 2020: 1–6. doi: 10.1109/NATW49237.2020.9153082. [13] LI Min, KHAN S, SHI Zhengyuan, et al. DeepGate: Learning neural representations of logic gates[C]. The 59th ACM/IEEE Design Automation Conference, San Francisco, USA, 2022: 667–672. doi: 10.1145/3489517.3530497. [14] CHAO Zhiteng, SUN Bin, LYU Hongqin, et al. HighTPI: A hierarchical graph based intelligent method for test point insertion[C]. The 2025 IEEE 43rd VLSI Test Symposium, Tempe, USA, 2025: 1–7. doi: 10.1109/VTS65138.2025.11022820. [15] DAS N, PAULS F, HASLER M, et al. A survey on recent developments in SCOAP-based hardware Trojan detection strategies[C]. 2025 IEEE International Symposium on Circuits and Systems, London, United Kingdom, 2025: 1–5. doi: 10.1109/ISCAS56072.2025.11043879. [16] RAKESH M B, DAS P, SAI PRANAV K R, et al. GRIPT: Graph attention-assisted inductive methodology for fast and accurate average power estimation from RTL simulation skipping gate-level simulation[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2025, 44(11): 4209–4221. doi: 10.1109/TCAD.2025.3563420. [17] PARIA S, GAIKWAD P, DASGUPTA A, et al. LATENT: Leveraging automated test pattern generation for hardware Trojan detection[C]. The 2024 IEEE 33rd Asian Test Symposium, Ahmedabad, India, 2024: 1–6. doi: 10.1109/ATS64447.2024.10915238. [18] ABRAMOVICI M, BREUER M A, and FRIEDMAN A D. Digital Systems Testing and Testable Design[M]. Beijing: Tsinghua University Press, 2004: 1–36. -
图(5) / 表(4)
计量
- 文章访问数: 203
- HTML全文浏览量: 92
- PDF下载量: 30
- 被引次数: 0
下载:
