Applications of global flow analysis in logic synthesis

Abstract

The authors describe a representation for multilevel circuits derived using the techniques of data-flow analysis. The usefulness of this representation is illustrated by describing algorithms for two of the fundamental problems of logic design: reducing the size of a circuit and increasing its testability. The authors obtain algorithms for circuit- size reduction by characterizing a class of function-preserving circuit transformations in terms of the representation and describe a novel algorithm from this class that uses approximate summary information to map the problem of reducing circuit size to that of finding a small cut in an associated graph. The algorithms for improving testability rely on the fact that the proposed representation permits conditional deductions to be performed efficiently. These algorithms have been implemented as part of an automatic design system in use within IBM.