Circuit Width, Register Allocation, and Ordered Binary Decision Diagrams

Abstract

In this paper we study the relationship between two important means of representing Boolean functions: combinational circuits and ordered binary decision diagrams (OBDD’s). We relate circuit width to OBDD size and show how algorithms for register allocation can be used to determine a good variable order for OBDD construction. In particular, we show that if e has n inputs, m outputs, and width w(e) then there is a variable ordering for which the DAG-based representation for e has at most n × m × 2^w(e) nodes. Since the width of a circuit is closely related to the number of registers required to evaluate the circuit, our result shows that register allocation techniques can be used to compute good variable orderings. We also outline how these ideas can be used in decomposing a function either for representation as a set of OBDD’s or for implementation in a cascode technology. Finally, we characterize a class of multioutput functions, which includes addition, whose members have particularly small OBDD’s. © 1991 IEEE