Extending Boolean Methods for Scalable Logic Synthesis

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.