BddCut: Towards Scalable Symbolic Cut Enumeration
Abstract
While the covering algorithm has been perfected recently by the
iterative approaches, such as DAOmap and IMap, its application has been
limited to technology mapping. The main factor preventing the covering
problem's migration to other logic transformations, such as elimination
and resynthesis region identification found in SIS and FBDD, is the
exponential number of alternative cuts that have to be evaluated.
Traditional methods of cut generation do not scale beyond a cut size
of 6. In this paper, a symbolic method that can enumerate all cuts is
proposed without any pruning, up to a cut size of 10. We show that it
can outperform traditional methods by an order of magnitude and, as
a result, scales to 100K gate benchmarks. As a practical driver, the
covering problem applied to elimination is shown where it can not only
produce competitive area, but also provide more than 6x average runtime
reduction of the total runtime in FBDD, a BDD based logic synthesis
tool with a reported order of magnitude faster runtime than SIS and
commercial tools with negligible impact on area.
Reference
Andrew Ling, Jianwen Zhu, Stephen D. Brown, "BddCut: Towards Scalable Symbolic Cut Enumeration," in ASP-DAC'07: Proceedings of the 2007 conference on Asia South Pacific Design Automation, Yokohama, Japan, Jan 2007, pp 408-413.
(Download Full Paper)