New methods in the analysis of logic minimization data and algorithms

ABSTRACT

This paper introduces techniques from combinatorial and algebraic topology to help in explaining and measuring the performance of modern logic minimizers. The concepts of simple cubical homotopy and the Euler—Poincare characteristic of a logic cover are defined and analyzed. In particular, simple cubical homotopy is related to the minimization algorithms Espresso—EXACT and Roth's Extraction Algorithm. Experimental results on the Euler—Poincare characteristic, along with a new measure, the Euler Ratio are related to the function complexity concepts of “Cyclic constraints” in Espresso_EXACT, the “CyclicKernel” in Roth's Extraction Algorithm, and “cubical homotopy” introduced in this paper.

REFERENCES

• 1: J.W. A(exander, "The combinatorial theory of complexes", Ann. of Math., 31, pp292-320, 1930
• 2: 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
• 3: Dietmeyer, Logic design of digital systems, Allyn & Bacon, Inc., Needham Heights, MA, 1988
• 4: P.J. Hilton and S. Wylie, Homology Theory, Cambridge Press, London, 1967.
• 5: P, Giblin, Graphs, Surfaces and Homology, Chapman and Hall, London, 197'7.
• 6: M.M. Cohen, A Course in Simp}e-Homotopy Theory, Springer-Verlag, New York, 1973.
• 7: J.P. Roth, "Algebraic topological methods for the synthesis of switching systems I", Trans. Am. Math. Sot., Vol. 88, No. 2, pp301-326, July 1 958.
• 8: J. Paul Roth, Computer Logic, Testing and Verification, W. H. Freeman & Co., New York, NY, 1980
• 9: R. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization", IEEE Trans. Computer-Aided Design, Vol. CAD-6, pp727-750, Sept 1987.
• 10: R. Rudell, "Multiple-valued logic minimization for PLA synthesis", Master's report, University of California, Berkeley,
• 11: J.H.C. Whitehead, "Simplicial spaces, nucleii and m-groups, Proc. London Math Soc., 45, pp243-327, 1939.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

Additional Classification:
  B. Hardware
  B.m MISCELLANEOUS
      Subjects: Design management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance