Decomposition Techniques for Efficient ROBDD Construction

Abstract

In this paper, we address the problem of memory-efficient construction of ROBDDs for a given Boolean network. We show that for a large number of applications, it is more efficient to construct the ROBDD by a suitable combination of top-down and bottom-up approaches than a purely bottom-up approach. We first build a decomposed ROBDD of the target function and then follow it by a symbolic composition to get the final ROBDD. We propose two heuristic algorithms for decomposition. One is based on a topological analysis of the given netlist, while the other is purely functional, making no assumptions about the underlying circuit topology. We demonstrate the utility of our methods on standard benchmark circuits as well as some hard industrial circuits. Our results show that this method requires significantly less memory than the conventional bottom-up construction. In many cases, we are able to build the ROBDDs of outputs for which the conventional method fails. In addition, in most cases this memory reduction is accompanied by a significant speed up in the ROBDD construction process.

For comments contact anarayan@ic.eecs.berkeley.edu