BddCut: Towards Scalable Symbolic Cut Enumeration


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.


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)