DAG-aware AIG rewriting a fresh look at combinational logic synthesis

TLDR

Combinational logic is represented using and‑inverter graphs (AIGs), networks of two‑input ANDs and inverters. The paper proposes a preprocessing technique for combinational logic before technology mapping. The method alternates DAG‑aware AIG rewriting, which shares common logic to reduce area without increasing delay, with algebraic AIG balancing to minimize delay without increasing area, and is implemented in the public‑domain tool ABC. Experiments on large industrial benchmarks demonstrate that the methodology scales to very large designs, runs several orders of magnitude faster than SIS and MVSIS, and delivers comparable or better quality after mapping.

Abstract

This paper presents a technique for preprocessing combinational logic before technology mapping. The technique is based on the representation of combinational logic using and-inverter graphs (AIGs), a networks of two-input ANDs and inverters. The optimization works by alternating DAG-aware AIG rewriting, which reduces area by sharing common logic without increasing delay, and algebraic AIG balancing, which minimizes delay without increasing area. The new technology-independent flow is implemented in a public-domain tool ABC. Experiments on large industrial benchmarks show that the proposed methodology scales to very large designs and is several orders of magnitude faster than SIS and MVSIS while offering comparable or better quality when measured by the quality of the network after mapping.