Scalable Technology Mapping and Clustering Techniques using Decision Diagrams

Abstract

BDDs have proven to be an efficient means to represent and manipulate Boolean formulae [1] and sets [2] due to their compactness and canonicality. In this work, we leverage the efficiency of BDDs for new areas in FPGA CAD flow including cut generation and clustering by reducing these problems to BDDs and solving them using Boolean operations. As a result, we show that this leads to more than 10x reduction in runtime and memory use when compared to previous techniques as reported in [3] and [4]. This speedup allows us to apply our work to new areas in the FPGA CAD flow previously not possible. Specifically, we introduce a new method to solve the logic synthesis elimination problem found in FBDD, a recently reported BDD synthesis engine with an order of magnitude speedup over SIS. Our new elimination algorithm results in an overall speedup of 6x in FBDD with no impact on circuit area.

Reference

Andrew C. Ling, Jianwen Zhu, and Stephen D. Brown, "Scalable Technology Mapping and Clustering Techniques using Decision Diagrams," accepted for publication in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, to appear in Spring 2008

(Download Full Paper)