Wenlong Yang
ABSTRACT
Deriving a circuit for a Boolean function or improving an available circuit are typical tasks solved by logic synthesis. Numerous algorithms in this area have been proposed and implemented over the last 50 years. This paper presents a "lazy" approach to logic synthesis based on the following observations: (a) optimal or near-optimal circuits for many practical functions are already derived by the tools, making it unnecessary to implement new algorithms or even run the old ones repeatedly; (b) larger circuits are composed of smaller ones, which are often isomorphic up to a permutation/negation of inputs/outputs. Experiments confirm these observations. Moreover, a case-study shows that logic level minimization using lazy man's synthesis improves delay after LUT mapping into 4- and 6-input LUTs, compared to earlier work on high-effort delay optimization.
- A. Abdollahi and M. Pedram, "A new canonical form for fast boolean matching in logic synthesis and verification". Proc. DAC'05, 379--384. Google Scholar
Digital Library
- Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. http://www-cad.eecs.berkeley.edu/~alanmi/abcGoogle Scholar
- V. Bertacco and M. Damiani. "The 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
- R. Brayton and A. Mishchenko, "ABC: An academic industrial-strength verification tool", Proc. CAV'10, LNCS 6174, pp. 24--40. Google ScholarDigital Library
- F. Brglez, D. Bryan, and K. Kozminski, "Combinational profiles of sequential benchmark circuits," Proc. ISCAS '89, pp. 1929--1934.Google Scholar
- D. Chai and A. Kuehlmann, "Building a better Boolean matcher and symmetry detector". Proc. DATE 2006, pp. 1079--1084. Google ScholarDigital Library
- S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang, and T. Kam, "Reducing structural bias in technology mapping", IEEE TCAD'06, Vol. 25(12), pp. 2894--2903. Google ScholarDigital Library
- ITC '99 Benchmarks. http://www.cad.polito.it/tools/itc99.htmlGoogle Scholar
- A. Kennings, A. Mishchenko, K. Vorwerk, V. Pevzner, and A. Kundu, "Generating efficient libraries for use in FPGA resynthesis algorithms". Proc. IWLS'10, pp. 147--154.Google Scholar
- E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," IEEE Trans. CAD, Vol. 16(8), Aug. 1997, pp. 813--833. Google ScholarDigital Library
- N. Li and E. Dubrova, "AIG rewriting using 5-input cuts", Proc. IWLS'11.Google Scholar
- S. Minato: "Fast generation of prime-irredundant covers from binary decision diagrams," IEICE Trans. Fundamentals, Vol. E76-A, No. 6, pp. 967--973, June 1993.Google Scholar
- A. Mishchenko, B. Steinbach, and M. A. Perkowski, "An algorithm for bi-decomposition of logic functions", Proc. DAC '01, 103--108. Google ScholarDigital Library
- A. Mishchenko, S. Chatterjee, and R. Brayton, "DAG-aware AIG rewriting: A fresh look at combinational logic synthesis", Proc. DAC '06, pp. 532--536. Google ScholarDigital Library
- A. Mishchenko, S. Chatterjee, R. Brayton, and N. Een, "Improvements to combinational equivalence checking", Proc. ICCAD '06, pp. 836--843. Google ScholarDigital Library
- A. Mishchenko and R. K. Brayton, "Scalable logic synthesis using a simple circuit structure", Proc. IWLS '06, pp. 15--22.Google Scholar
- A. Mishchenko, S. Cho, S. Chatterjee, R. Brayton, "Combinational and sequential mapping with priority cuts", Proc. ICCAD '07, pp. 354--361. Google ScholarDigital Library
- A. Mishchenko, R. Brayton, S. Jang, and V. Kravets, "Delay optimization using SOP balancing", Proc. ICCAD'11, pp. 375--382. Google ScholarDigital Library
- 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
- J. Pistorius, M. Hutton, A. Mishchenko, and R. Brayton. "Benchmarking method and designs targeting logic synthesis for FPGAs", Proc. IWLS '07, pp. 230--237.Google Scholar
- J. Rajski and J. Vasudevamurthy, "The testability-preserving concurrent decomposition and factorization of Boolean expressions". IEEE TCAD'92, vol. 11(6), pp. 778--793. Google ScholarDigital Library
- S. Ray, A. Mishchenko, N. Een, R. Brayton, S. Jang, and C. Chen, "Mapping into LUT structures", Proc. DATE'12. Google ScholarDigital Library
- E. Sentovich et al, "SIS: A system for sequential circuit synthesis", Tech. Rep. UCB/ERI, M92/41, ERL, Dept. of EECS, Univ. of California, Berkeley, 1992.Google Scholar
- C. Yang and M. Ciesielski. "BDS: a BDD-based logic optimization system", IEEE TCAD'02, vol. 21(7), pp. 866--876. Google ScholarDigital Library
- S. Yang. "Logic synthesis and optimization benchmarks". Version 3.0. Tech. Report. Microelectronics Center of North Carolina, 1991.Google Scholar
- L. Wang, and A. E. A. Almaini, "Multilevel logic simplification based on containment recursive paradigm", IEE Proceedings Computers and Digital Techniques, 2003, Vol. 150, No. 4, pp, 218--226.Google ScholarCross Ref
- D. Wu and J. Zhu, "FBDD: a folded logic synthesis system", Proc. DAC'05, pp. 746--751.Google Scholar
- https://skydrive.live.com/redir.aspx?cid=76d4b8991df82cf3&resid=76D4B8991DF82CF3!152&parid=rooGoogle Scholar
Index Terms
- Lazy man's logic synthesis
Recommendations
Synthesis of skewed logic circuits
Skewed logic circuits belong to a noise-tolerant high-performance static circuit family. Skewed logic circuits can achieve performance comparable to that of Domino logic circuits but with much lower power consumption. Two factors contribute to the ...
Fredkin/Toffoli Templates for Reversible Logic Synthesis
ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided designReversible logic has applications in quantum computing, lowpower CMOS, nanotechnology, optical computing, and DNAcomputing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of ...
Reversible logic synthesis with Fredkin and Peres gates
Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis ...
Comments