New Methods in the Analysis of Logic Minimization Data and Algorithms

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.