On-the-fly and DAG-aware: Rewriting Boolean Networks with Exact Synthesis

The paper presents a generalization of DAG-aware AIG rewriting for k-feasible Boolean networks, whose nodes are k-input lookup tables (k-LUTs). We introduce a high-effort DAG-aware rewriting algorithm, called cut rewriting, which uses exact synthesis to compute replacements on the fly, with support for Boolean don't cares. Cut rewriting pre-computes a large number of possible replacement candidates, but instead of eagerly rewriting the Boolean network, stores the replacements in a conflict graph. Heuristic optimization is used to derive a best, maximal subset of replacements that can be simultaneously applied to the Boolean network from the conflict graph. We optimize LUT mapped Boolean networks obtained from the ISCAS and EPFL combinational benchmark suites. For 3-LUT networks, experiments show that we achieve an average size improvement of 5.58% and up to 40.19% after state-of-the-art Boolean rewriting techniques were applied until saturation. Similarly, for 4-LUT networks, we obtain an average improvement of 4.04% and up to 12.60%.

Published in:
2019 Design, Automation & Test In Europe Conference & Exhibition (DATE), 1649-1654
Presented at:
Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, Mar 25-29, 2019
Jul 23 2019
New York, IEEE

 Record created 2019-06-24, last modified 2020-04-20

Rate this document:

Rate this document:
(Not yet reviewed)