Detecting support-reducing bound sets using two-cofactor symmetries

ABSTRACT

Detecting support-reducing bound sets is an important step in Boolean decomposition. It affects both the quality and the runtime of several applications in technology mapping and re-synthesis. This paper presents an efficient heuristic method for detecting support-reducing bound sets using two-cofactor symmetries. Experiments on the MCNC and ITC benchmarks show an average 40x speedup over the published exhaustive method for bound set construction.

REFERENCES

• 1: A. Mishchenko, X. Wang, and T. Kam. "A new enhanced constructive decomposition and mapping algorithm". Proc. DAC '03, pp. 143--147, June 2003.
• 2: Victor Nikolayevich Kravets , Karem A. Sakallah, Constructive multi-level synthesis by way of functional properties, 2001
• 3: Victor N. Kravets , Karem A. Sakallah, Constructive library-aware synthesis using symmetries, Proceedings of the conference on Design, automation and test in Europe, p.208-215, March 27-30, 2000, Paris, France [doi>10.1145/343647.343734]
• 4: Victor N. Kravets , Karem A. Sakallah, Resynthesis of multi-level circuits under tight constraints using symbolic optimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.687-693, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774673]
• 5: R. L. Ashenhurst. "The decomposition of switching functions", Computational Lab, Harvard University, Vol. 29, pp. 74--116, 1959.
• 6: A. Curtis. "New approach to the design of switching circuits", Van Nostrand, Princeton, NJ, 1962.
• 7: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 8: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 9: T. Sasao. "FPGA design by generalized functional decomposition", In T. Sasao (ed.), Logic Synthesis and Optimization, Kluwer Academic publishers, 1993.
• 10: C. R. Edward and S. L. Hurst. "A digital synthesis procedure under function symmetries and mapping methods", IEEE Trans. On Computers, vol. C-27, No.11, pp. 985--997, November 1978.
• 11: B.-G. Kim and D. L. Dietmeyer. "Multilevel logic synthesis of symmetric switching functions", IEEE Trans. CAD, 10(4), pp.436--446, April 1991.
• 12: Yung-Te Lai , Sarma Sastry , Massoud Pedram, Boolean Matching Using Binary Decision Diagrams with Applications to Logic Synthesis and Verification, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.452-458, October 11-14, 1992
• 13: Ch. Scholl, D. Möller, P. Molitor, and R. Drechsler. "BDD minimization using symmetries", IEEE Trans. CAD, 18(2) pp. 81--100, February 1999.
• 14: M. Chrzanowska-Jeske, W. Wang, J. Xia, and M. Jeske. "Disjunctive decomposition of switching functions using symmetry information," Proc IEEE SBCCI '00, pp. 67, September 2000.
• 15: 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
• 16: J. S. Zhang, M. Chrzanowska-Jeske, A. Mishchenko, and J. R. Burch. "Fast computation of generalized symmetries in Boolean functions", Proc. IWLS '04, pp. 424--430, June 2004.
• 17: F. Somenzi. CUDD Package, Release 2.3.1. http://vlis.Colorado.EDU/~fabio/CUDD/cuddIntro.html
• 18: A. Mishchenko. EXTRA Library of DD procedures. http://www.ee.pdx.edu/~alanmi/research/extra.htm