A Reliability-Critical Path Identifying Method With Local and Global Adjacency Probability Matrix in Combinational Circuits

Accurate and efficient identification of reliability-critical paths (RCPs) not only facilitates fault localization and troubleshooting but also allows circuit designers to improve circuit reliability at a low cost. This article proposes a local and global adjacency probability matrix-based approach (LGAPM) to quickly and efficiently identify RCPs of combinational logic circuits. The approach reflects the criticality of the overall reliability of the circuit as well as the local criticality of gates in the path. In addition, we design a pruning-based method to accelerate RCP identification in large-scale circuits. The experimental results of the LGAPM on all 74 series circuits, ISCAS-85, and partial EPFL benchmark circuits show that the 74181 circuit with a minimum of 17 paths and the EPFL-remainder10 circuit with a maximum of 8.081 × 10
⁸
paths take times of about 0.18s and 33931.04s, respectively. The average accuracy on small and medium-scale circuits is 94.24%, and the average stability on all-size circuits is 86.19%. Compared to the SAT-based method, hill-climbing algorithm, and random method, LGAPM’s metrics are superior and more appropriate for large-scale circuits. The overall circuit reliability can be improved from 0.7726 to 0.9238 on average by hardening a tiny number of gates in the identified the most RCPs and the average cost savings is 4.08 times over random hardening methods.