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

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.

REFERENCES

• 1: Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. December 2005 Release. http://www-cad.eecs.berkeley.edu/~alanmi/abc
• 2: Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
• 3: P. Bjesse , A. Boralv, DAG-aware circuit compression for formal verification, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.42-49, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382541]
• 4: R. Brayton and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. ISCAS '82, pp. 29--54.
• 5: R. Brayton, G. Hachtel, A. Sangiovanni-Vincentelli, "Multilevel logic synthesis", Proc. IEEE, Vol. 78, Feb.1990.
• 6: S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA
• 7: J. Cong and Y. Ding, "FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs", IEEE Trans. CAD, vol. 13(1), January 1994, pp. 1--12.
• 8: J. Cortadella, "Timing-driven logic bi-decomposition", IEEE TCAD, vol. 22(6), June 2003, pp. 675--685.
• 9: IWLS 2005 Benchmarks. http://iwls.org/iwls2005/benchmarks.html
• 10: Yuji Kukimoto , Robert K. Brayton , Prashant Sawkar, Delay-optimal technology mapping by DAG covering, Proceedings of the 35th annual conference on Design automation, p.348-351, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277142]
• 11: Alan Mishchenko , Robert K. Brayton, SAT-Based Complete Don't-Care Computation for Network Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.412-417, March 07-11, 2005 [doi>10.1109/DATE.2005.264]
• 12: A. Mishchenko and R. Brayton, "Scalable logic synthesis using a simple circuit structure", Proc. IWLS '06. http://www.eecs. berkeley.edu/~alanmi/publications/2006/iwls06_sls.pdf.
• 13: A. Mishchenko, S. Chatterjee, R. Brayton, and N. Eén, "Improvements to combinational equivalence checking", IWLS '06. http://www.eecs.berkeley.edu/~alanmi/publications/2006/iwls06 _cec.pdf
• 14: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, Improvements to technology mapping for LUT-based FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117208]
• 15: Saburo Muroga, Logic Design and Switching Theory, John Wiley & Sons, Inc., New York, NY, 1979
• 16: MVSIS Group. MVSIS: Multi-Valued Logic Synthesis System. UC Berkeley. http://www?cad.eecs.berkeley.edu/mvsis/
• 17: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 18: E. Sentovich et al. "SIS: A system for sequential circuit synthesis". Technical Report, UCB/ERI, M92/41, ERL, Dept. of EECS, UC Berkeley, 1992.
• 19: S. Yang. Logic synthesis and optimization benchmarks. Version 3.0. Tech. Report. Microelectronics Center of North Carolina, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
NPN equivalence, and-inverter graphs, technology mapping, technology-independent logic synthesis