Large-scale SOP minimization using decomposition and functional properties

ABSTRACT

In some cases, minimum Sum-Of-Products (SOP) expressions of Boolean functions can be derived by detecting decomposition and observing the functional properties such as unateness, instead of applying the classical minimization algorithms. This paper presents a systematic study of such situations and develops a divide-and-conquer algorithm for SOP minimization, which can dramatically reduce the computational effort, without sacrificing the minimality of the solutions. The algorithm is used as a preprocessor to a general-purpose exact or heuristic minimizer, such as ESPRESSO. The experimental results show significant improvements in runtime. The exact solutions for some large MCNC benchmark functions are reported for the first time.

REFERENCES

• 1: R. L. Ashenhurst, "The decomposition of switching functions". Computation Lab, Harvard University, 1959, Vol. 29, pp. 74--116.
• 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: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 4: R. K. Brayton and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. ISCAS '82, pp. 29--54.
• 5: 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]
• 6: M.J. Ciesielski, S. Yang, and M.A. Perkowski, "Multiple-valued minimization based on graph coloring," Proc. ICCD '89, pp.262--265.
• 7: O. Coudert and J. C. Madre, "Towards a symbolic logic minimization algorithm", Proc. VLSI Design, January 1993.
• 8: Olivier Coudert, Two-level logic minimization: an overview, Integration, the VLSI Journal, v.17 n.2, p.97-140, Oct. 1994 [doi>10.1016/0167-9260(94)00007-7]
• 9: Olivier Coudert, Exact coloring of real-life graphs is easy, Proceedings of the 34th annual conference on Design automation, p.121-126, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266047]
• 10: J. Jacob and A. Mishchenko, "Unate decomposition of Boolean functions", Proc. IWLS '01, pp. 66--71.
• 11: Abdul A. Malik , Robert K. Brayton , A. Richard Newton , Alberto L. Sangiovanni-Vincentelli, Reduced offsets for two-level multi-valued logic minimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.290-296, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123279]
• 12: Y. Matsunaga, "An exact and efficient algorithm for disjunctive decomposition", Proc. SASIMI '98, pp. 44--50.
• 13: Patrick McGeer , Jagesh Sanghavi , Robert Brayton , Alberto Sangiovanni Vincentelli, Espresso-signature: a new exact minimizer for logic functions, Proceedings of the 30th international conference on Design automation, p.618-624, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165069]
• 14: S. Minato, "Fast generation of irredundant sum-of-products forms from binary decision diagrams. Proc. SASIMI'92, pp. 64--73.
• 15: A. Mishchenko, EXTRA Library of DD procedures. http://www.ee.pdx.edu/~alanmi/research/ extra.htm
• 16: R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization", IEEE Trans. CAD, Vol. 6(5), pp. 727--750, Sep. 1987.
• 17: T. Sasao, "An algorithm to derive the complement of a binary function with multiple-valued inputs," IEEE Trans. Comp. Vol. C-34, No. 2, pp. 131--140, Feb. 1985.
• 18: Tsutomu Sasao , Jon T. Butler, On the minimization of SOPs for bi-decomposition functions, Proceedings of the 2001 conference on Asia South Pacific design automation, p.219-224, January 2001, Yokohama, Japan [doi>10.1145/370155.370327]
• 19: Tsutomu Sasao , Jon T. Butler, Worst and Best Irredundant Sum-of-Products Expressions, IEEE Transactions on Computers, v.50 n.9, p.935-948, September 2001 [doi>10.1109/12.954508]
• 20: T. Sasao, S. J. Hong, and R. K. Brayton, "Minimization of PLA's by decomposition", Unpublished technical report, 1984.
• 21: T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," Proc. IWLS '98, pp. 471--477.
• 22: 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.
• 23: F. Somenzi, BDD package "CUDD v. 2.3.0." http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
• 24: http://www.lsi-cad.com/dac2003/appendix.pdf.

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:
BDDs, SOP minimization, disjoint-support decomposition, divide-and-conquer strategy, orthodox functions