A BDD-based fast heuristic algorithm for disjoint decomposition
2003 (English)In: The IEEE Asia and South Pacific Design Automation Conference 2003 (ASP-DAC 2003), January, 2003, Kitakyushu, Japan, Asia and South Pacific Design Automation Conference, 2003, 191-196 p.Conference paper (Refereed)
This paper presents a heuristic algorithm for disjointdecomposition of a Boolean function based on its ROBDDrepresentation. Two distinct features make the algorithm feasiblefor large functions. First, for an n-variable function, it checks onlyO(n2) candidates for decomposition out of O(2n) possible ones. Aspecial strategy for selecting candidates makes it likely that allother decompositions are encoded in the selected ones. Second,the decompositions for the approved candidates are computedusing a novel IntervalCut algorithm. This algorithm does notrequire re-ordering of ROBDD. The combination of both techniquesallows us to decompose the functions of size beyond thatpossible with the exact algorithms. The experimental results on582 benchmark functions show that the presented heuristic finds95% of all decompositions on average. For 526 of those functions,it finds 100% of the decompositions.
Place, publisher, year, edition, pages
2003. 191-196 p.
IdentifiersURN: urn:nbn:se:kth:diva-24436DOI: 10.1109/ASPDAC.2003.1195015OAI: oai:DiVA.org:kth-24436DiVA: diva2:349874
QC 201009092010-09-092010-09-092010-09-09Bibliographically approved