Extending Boolean Methods for Scalable Logic Synthesis
Open Access
- 15 December 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 226828-226844
Abstract
In recent years, Boolean methods in logic synthesis have been drawing the attention of EDA researchers due to the continuous push to advance quality of results. Boolean methods require high computational cost, as they rely on complete functional properties of a logic circuit (e.g., don’t cares), but usually result in better optimization. In particular, Boolean resubstitution is considered one of the most powerful Boolean methods in logic synthesis. In this paper, we present three novel Boolean resubstitution algorithms designed to be scalable and runtime-effective in a modern synthesis flow. They make use of circuit partitioning techniques and Boolean filtering to be fast and computationally tractable. We also discuss different data structures and reasoning engines, namely truth tables, binary decision diagrams, and satisfiability, that are required to gather don’t cares and functional information. As the choice of the engine determines the scalability of Boolean resubstitution, we present different scenarios in which the Boolean methods are best driven by one or the other of these. We have implemented the presented resubstitution techniques together with state-of-the-art methods in an industrial logic optimization engine to create a novel resynthesis flow. Our global resynthesis flow achieves significant synthesis results: Within the EPFL synthesis competition, we improve the best-known area results when mapped into LUT-6; when embedded in a commercial EDA flow, the new Boolean resynthesis flow results in 3:12% combinational area savings and 1:34% WNS reduction after physical implementation, at contained (w.r.t. the time of the entire flow) runtime cost.Keywords
Funding Information
- Swiss National Science Foundation (200021-169084 MAJesty)
- ERC project (H2020-ERC-2014-ADG 669354 CyberCare)
- Defense Advanced Research Projects Agency (FA8650-18-2-7849)
- Semiconductor Research Corporation (2710.001, 2867.001)
This publication has 30 references indexed in Scilit:
- Scalable don't-care-based logic optimization and resynthesisACM Transactions on Reconfigurable Technology and Systems, 2011
- Robust Boolean reasoning for equivalence checking and functional property verificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002
- BDS: a BDD-based logic optimization systemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002
- Optimization of combinational logic circuits based on compatible gatesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- Logic Synthesizers, The Transduction Method and Its Extension, Sylon1993
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplicationIEEE Transactions on Computers, 1991
- Multilevel logic synthesisProceedings of the IEEE, 1990
- The transduction method-design of logic networks based on permissible functionsIEEE Transactions on Computers, 1989
- Multi-level logic minimization using implicit don't caresIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- The large scale structure and dynamics of gene control circuitsJournal of Theoretical Biology, 1974