Alan Mishchenko
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.
- Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. December 2005 Release. http://www-cad.eecs.berkeley.edu/~alanmi/abcGoogle Scholar
- V. Bertacco and M. Damiani, "Disjunctive decomposition of logic functions," Proc. ICCAD '97, pp. 78--82. Google ScholarDigital Library
- P. Bjesse and A. Boralv, "DAG-aware circuit compression for formal verification", Proc. ICCAD '04, pp. 42--49. Google ScholarDigital Library
- R. Brayton and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. ISCAS '82, pp. 29--54.Google Scholar
- R. Brayton, G. Hachtel, A. Sangiovanni-Vincentelli, "Multilevel logic synthesis", Proc. IEEE, Vol. 78, Feb.1990.Google Scholar
- S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang, and T. Kam, "Reducing structural bias in technology mapping", Proc. ICCAD '05, pp. 519--526. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- J. Cortadella, "Timing-driven logic bi-decomposition", IEEE TCAD, vol. 22(6), June 2003, pp. 675--685. Google ScholarDigital Library
- IWLS 2005 Benchmarks. http://iwls.org/iwls2005/benchmarks.htmlGoogle Scholar
- E. Y. Kukimoto, R. Brayton, P. Sawkar, "Delay-optimal technology mapping by DAG covering", Proc. DAC '98, pp. 348--351. Google ScholarDigital Library
- A. Mishchenko and R. Brayton, "SAT-based complete don't-care computation for network optimization", DATE '05, pp. 418--423. Google ScholarDigital Library
- 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.Google Scholar
- 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.pdfGoogle Scholar
- A. Mishchenko, S. Chatterjee, and R. Brayton, "Improvements to technology mapping for LUT-based FPGAs", FPGA '06, pp. 41--49. Google ScholarDigital Library
- S. Muroga, Logic design and switching theory, John Wiley & Sons, Inc., New York, NY, 1979. Google ScholarDigital Library
- MVSIS Group. MVSIS: Multi-Valued Logic Synthesis System. UC Berkeley. http://www?cad.eecs.berkeley.edu/mvsis/Google Scholar
- P. Pan and C.-C. Lin, "A new retiming-based technology mapping algorithm for LUT-based FPGAs," Proc. FPGA '98, pp. 35--42. Google ScholarDigital Library
- E. Sentovich et al. "SIS: A system for sequential circuit synthesis". Technical Report, UCB/ERI, M92/41, ERL, Dept. of EECS, UC Berkeley, 1992.Google Scholar
- S. Yang. Logic synthesis and optimization benchmarks. Version 3.0. Tech. Report. Microelectronics Center of North Carolina, 1991.Google Scholar
Index Terms
- DAG-aware AIG rewriting a fresh look at combinational logic synthesis
Recommendations
Quaternary CMOS Combinational Logic Circuits
ICIMT '09: Proceedings of the 2009 International Conference on Information and Multimedia TechnologyGood Characteristics and advantages of multi-valued logic (MVL) electronic systems and circuits are created great interest for its practical implementation. This paper presents voltage mode quaternary CMOS circuit design using 90nm technology. Basic ...
Balanced Factorization and Rewriting Algorithms for Synthesizing Single Flux Quantum Logic Circuits
GLSVLSI '19: Proceedings of the 2019 on Great Lakes Symposium on VLSISingle Flux Quantum (SFQ) logic with switching energy of 100zJ1 and switching delay of 1ps is a promising post-CMOS candidate. Logic synthesis of these magnetic-pulse-based circuits is a very important step in their design flow with a big impact on the ...
Comments