On-Line Pruning of ZBDD for Path Delay Fault Coverage Calculation

Fatih KOCAN; Mehmet H. GUNES; Atakan KURT

doi:10.1093/ietisy/e88-d.7.1381

On-Line Pruning of ZBDD for Path Delay Fault Coverage Calculation

Fatih KOCAN, Mehmet H. GUNES, Atakan KURT

Full Text Views

0

Cite this

Summary :

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. 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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.7 pp.1381-1388

Publication Date: 2005/07/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.7.1381

Type of Manuscript: Special Section PAPER (Special Section on Recent Advances in Circuits and Systems--Part 1)

Category: Programmable Logic, VLSI, CAD and Layout

Cite this

Copy

Fatih KOCAN, Mehmet H. GUNES, Atakan KURT, "On-Line Pruning of ZBDD for Path Delay Fault Coverage Calculation" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 7, pp. 1381-1388, July 2005, doi: 10.1093/ietisy/e88-d.7.1381.
Abstract: 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. 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.7.1381/_p

Copy

@ARTICLE{e88-d_7_1381,
author={Fatih KOCAN, Mehmet H. GUNES, Atakan KURT, },
journal={IEICE TRANSACTIONS on Information},
title={On-Line Pruning of ZBDD for Path Delay Fault Coverage Calculation},
year={2005},
volume={E88-D},
number={7},
pages={1381-1388},
abstract={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. 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.},
keywords={},
doi={10.1093/ietisy/e88-d.7.1381},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - On-Line Pruning of ZBDD for Path Delay Fault Coverage Calculation
T2 - IEICE TRANSACTIONS on Information
SP - 1381
EP - 1388
AU - Fatih KOCAN
AU - Mehmet H. GUNES
AU - Atakan KURT
PY - 2005
DO - 10.1093/ietisy/e88-d.7.1381
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2005
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. 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.
ER -