TY - JOUR
T1 - On-line pruning of ZBDD for path delay fault coverage calculation
AU - Kocan, Fatih
AU - Gunes, Mehmet H.
AU - Kurt, Atakan
PY - 2005/7
Y1 - 2005/7
N2 - Zero-suppressed BDDs (ZBDDs) have been used in the nonenumerative path delay fault (PDF) grading of VLSI circuits. One basic and one cut-based grading algorithm are proposed to grade circuits with polynomial and exponential number of PDFs, respectively. In this article, we present a new ZBDD-based basic PDF grading algorithm to enable grading of some circuits with exponential number of PDFs without using the cut-based algorithm. The algorithm overcomes the memory overflow problems by dynamically pruning the ZBDD at run-time. This new algorithm may give exact or pessimistic coverage depending on the statuses of the pruned nodes. Furthermore, we re-assess the performance of the static variable ordering heuristics in ZBDDs for PDF coverage calculation [1]. The proposed algorithm combined with the efficient static variable ordering heuristics can avoid ZBDD size explosion in many circuits. Experimental results for ISCAS85 benchmarks show that the proposed algorithm efficiently grades circuits.
AB - Zero-suppressed BDDs (ZBDDs) have been used in the nonenumerative path delay fault (PDF) grading of VLSI circuits. One basic and one cut-based grading algorithm are proposed to grade circuits with polynomial and exponential number of PDFs, respectively. In this article, we present a new ZBDD-based basic PDF grading algorithm to enable grading of some circuits with exponential number of PDFs without using the cut-based algorithm. The algorithm overcomes the memory overflow problems by dynamically pruning the ZBDD at run-time. This new algorithm may give exact or pessimistic coverage depending on the statuses of the pruned nodes. Furthermore, we re-assess the performance of the static variable ordering heuristics in ZBDDs for PDF coverage calculation [1]. The proposed algorithm combined with the efficient static variable ordering heuristics can avoid ZBDD size explosion in many circuits. Experimental results for ISCAS85 benchmarks show that the proposed algorithm efficiently grades circuits.
KW - On-line pruning
KW - Path delay fault
KW - Simulation
KW - ZBDD
UR - http://www.scopus.com/inward/record.url?scp=26044464822&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=26044464822&partnerID=8YFLogxK
U2 - 10.1093/ietisy/e88-d.7.1381
DO - 10.1093/ietisy/e88-d.7.1381
M3 - Article
AN - SCOPUS:26044464822
SN - 0916-8532
VL - E88-D
SP - 1381
EP - 1388
JO - IEICE Transactions on Information and Systems
JF - IEICE Transactions on Information and Systems
IS - 7
ER -