Global Flow Optimization in Automatic Logic Design

Abstract

A new method for optimizing digital logic networks is described. Techniques of data flow analysis are used to summarize a circuit efficiently; this summary is used to characterize a class of circuits which are equivalent to the given circuit, and an algorithm is described which reduces the problem of finding small circuits in this equivalence class to the problem of finding a min-cut in an assoicated graph. This algorithm has been implemented and forms part of an automatic design system in use within IBM. We describe the results of experiments undertaken to evaluate the effect of our new techniques. © 1991 IEEE