Approximate BDD Minimization by Weighted A*

Reduced ordered Binary Decision Diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs depends on a chosen variable ordering, i.e. the size may vary from linear to exponential, and the existence of a polynomial algorithm to approximate the optimal variable ordering of BDDs implies P = NP. In this paper, a new approximate BDD minimization algorithm is presented which is based on weighted A*. When compared to the best known previous method, large gains in run time are observed whereas the degradation of solution quality is considerably smaller than for the previous method. The improved behavior now allows for a wider range of time/quality tradeoffs. Experimental results demonstrate the efficiency of the new approach.


Published in:
IEEE International Symposium on Circuits and Systems, 2974-2977
Presented at:
ISCAS 2009, Taipei (Taiwan R.o.C.), 2009-05-24 - 2009-05-27
Year:
2009
Publisher:
Institute of Electrical and Electronics Engineers
ISSN:
0271-4310
Keywords:
Laboratories:




 Record created 2010-11-17, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)