Global flow optimization in automatic logic design

Abstract

A method for optimizing digital logic networks is described. This approach uses the techniques of global flow analysis to efficiently gather information about the relationship between different wires in a circuit and uses methods from network flow to use this information to optimize the circuit. It differs from earlier methods for optimization of multilevel logic networks in that valid rearrangements of signal connections depend on the maintenance of global circuit invariants. An algorithm which reduces the problem of finding small circuits in this equivalence class to the problem of finding a min-cut in an associated graph is described. This algorithm has been implemented and forms part of an automatic design system in use within IBM. The authors describe the results of experiments undertaken to evaluate the effect of the techniques.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>