The relationship between two important means of representing Boolean functions, combinational circuits and ordered binary decision diagrams (OBDDs), is studied. Circuit width is related to OBDD size. and it is shown how algorithms for register allocation can be used to determine a good variable order for OBDD construction. In particular, it is shown that if C has n inputs, moutputs, and width w(C), then there is a variable ordering for which the directed-acyclic-graph-based representation for C has at most n*m*2/sup w(C)/ modes. Since the width of a circuit is closely related to the number of registers required to evaluate the circuit, the result indicates that register allocation techniques can be used to compute good variable orderings. How these ideas can be used in decomposing a function either for representation as a set of OBDDs or for implementation in a cascode technology is outlined. A class of multioutput functions, which includes addition, whose members have particularly small OBDDs is characterized.>

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.>

A method is described for circuit equivalence which proceeds by reducing the question of whether two circuits are equivalent to a number of a more easily answered questions concerning the equivalence of smaller, related circuits. The primary technical contribution is a technique for discovering internal equivalences and using them to show the equivalence of the outputs. The method involves the use of signatures to reduce the number of potentially equivalent signals, and the use of the min-cut algorithm to reduce the original problem to related problems with fewer independent inputs. The method can be used to extend the power of any given equivalence checking algorithm. The authors report the result of experiments evaluating their technique.>

The relationship between two important means of representing Boolean functions, combinational circuits and ordered binary decision diagrams (OBDDs), is studied. Circuit width is related to OBDD size, and it is shown how register allocation can be used to determine a good variable order of OBDD construction. It is shown that if C has n inputs, m outputs, and width w(C), then there is a variable ordering for which the directed-acyclic-graph-based representation for C has at most n*m*2/sup w(C)/ nodes. Since the width of a circuit is closely related to the number of registers required to evaluate the circuit, the result shows that register allocation techniques can be used to compute variable orderings with predicted behavior. The use of these ideas in decomposing a function either for representation as a set of OBDDs or for implementation in a cascode technology is outlined. A characterization is given of a class of multioutput functions which includes addition whose members have particularly small OBDDs.>

Methods are presented for generating bounds on interconnection delays in a combinational network having specified timing requirements at its input and output terminals. An automatic placement program that uses wirability as its primary objective could use these delay bounds to generate length or capacitance bounds for interconnection nets as secondary objectives. Thus, unlike previous timing-driven placement algorithms, the desired performance of the circuit is guaranteed when a wirable placement meeting these objectives is found. Fast algorithms are provided that maximize the delay range, and hence the margin for error in layout, for various types of timing constraint.>

Techniques for automatically reducing circuit size and improving testability are considered. Two extensions to a previously published method for circuit optimization based on ideas of global flow analysis are described. The first is a basic improvement in the primary results on which the earlier optimization was based; the second extends the applicability of the method to conditional optimizations as well. Together these enhancements result in improved performance for the original algorithm, as well as the ability to handle designer-specified don't cares and redundancy-removal uniformly in the framework of a graph-based synthesis system such as LSS.>

This correspondence concerns applications of optimization techniques based on global flow analysis to the automated design of logic. Previous optimization work on logic design has relied primarily on either local transformations on the circuit graph or on the use of two-level Boolean minimization. Our methods involve linear time algorithms which extend the scope of local optimizations to the entire design. Their use, in some cases, has resulted in a reduction in gate count, in improved control over path length, and in better detection and elimination of redundancy.