Boolean Rewriting Strikes Back: Reconvergence- Driven Windowing meets Resynthesis
The paper presents a novel DAG-aware Boolean rewriting algorithm for restructuring combinational logic before technology mapping. The algorithm, called window rewriting, repeatedly selects small parts of the logic and replaces them with more compact implementations. Window rewriting combines small-scale windowing with a fast heuristic Boolean resynthesis. The former uses sophisticated structural analysis to capture reconvergent paths in a multi-output window. The latter re-expresses the multi-output Boolean function of the window using fewer gates if possible. Experiments on the EPFL benchmarks show that a single iteration of window rewriting outperforms state-of-the-art AIG rewriting repeated until convergence in both quality and runtime.
Reconvergence.pdf
n/a
openaccess
n/a
166.1 KB
Adobe PDF
f53b2d58a3544dd802f2a6fe4b23cecb