Title :
DAG-aware AIG rewriting: a fresh look at combinational logic synthesis
Author :
Mishchenko, Alan ; Chatterjee, Satrajit ; Brayton, Robert
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA
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
Keywords :
combinational circuits; directed graphs; logic design; logic gates; DAG-aware AIG rewriting; algebraic AIG balancing; and-inverter graphs; combinational logic synthesis; industrial benchmarks; technology mapping; Circuit synthesis; Computer industry; Cost function; Delay estimation; Industrial control; Logic design; Logic functions; Network synthesis; Pulse inverters; Robustness; Algorithms; And-Inverter Graphs; Experimentation; NPN equivalence; Performance; Technology-independent logic synthesis; Theory; technology mapping;
Conference_Titel :
Design Automation Conference, 2006 43rd ACM/IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
1-59593-381-6
DOI :
10.1109/DAC.2006.229287