Approximate reachability with BDDs using overlapping projections

Approximate reachability tec hniques trade off accuracy with the capacity to deal with bigger designs. Cho et al [3] proposed approximate FSM traversal algorithms over a partition of the set of state bits. In this paper w egeneralize it by allowing projectionson to a collection of nondisjoint subset...

Full description

Saved in:
Bibliographic Details
Main Authors: Govindaraju, Shankar G., Dill, David L., Hu, Alan J., Horowitz, Mark A.
Format: Conference Proceeding
Language:English
Subjects:
Applied computing > Physical sciences and engineering > Engineering
Binary decision diagrams
Boolean functions
Computer science
Computer systems organization > Dependable and fault-tolerant systems and networks
Data structures
Forward contracts
General and reference > Cross-computing tools and techniques > Performance
Hardware
Hardware > Integrated circuits
Hardware > Robustness
Mathematics of computing > Mathematical software
Networks > Network performance evaluation
Partitioning algorithms
Permission
Reachability analysis
State-space methods
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Approximate reachability tec hniques trade off accuracy with the capacity to deal with bigger designs. Cho et al [3] proposed approximate FSM traversal algorithms over a partition of the set of state bits. In this paper w egeneralize it by allowing projectionson to a collection of nondisjoint subsets of the state variables. We establish the adv an tageof ha ving overlapping projections and present a new multiple constr ainfunction for BDDs, to compute efficiently the approximate image during symbolic forward propagation using overlapping projections. We demonstrate the effectiveness of this new algorithm by applying it to several control modules from the I/O unit in the Stanford FLASH Multiprocessor. We also present our results on the larger ISCAS 89 benchmarks.
DOI:10.1145/277044.277169