J. Jain, A. Narayan, C. Coelho, S.P. Khatri, Alberto L. Sangiovanni-Vincentelli, Robert K. Brayton and M. Fujita

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M95/30
April 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/ERL-95-30.pdf

ROBDDs have traditionally been built in a bottom-up fashion, though the recursive use of Bryant's apply procedure [8], or the ITE [4] procedure. With these methods, the peak memory utilization is often larger than the final ROBDD size. Though methods like Dynamic Variable Reordering [21] have been proposed to reduce the memory utilization, such schemas have an associated time penalty. In this paper, we show that for a large number of applications, it is more efficient to construct the ROBDD by a suitable combination of top-down (decomposition based) and bottom-up (composition based) approaches. We suitably select decomposition points during the construction of the ROBDD, and 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 a given combinational netlist, while the other is purely functional, making no assumptions about the underlying topology of the circuit. We demonstrate the utility of our scheme on the standard benchmark circuits. Our results show that for a given variable ordering, our method usually has significantly better time as well as memory characteristics than existing techniques. Our methods are easily extended to many variants of ROBDDs, and in that sense are powerful in their scope.

BibTeX citation:

@techreport{Jain:M95/30,
    Author = {Jain, J. and Narayan, A. and Coelho, C. and Khatri, S.P. and Sangiovanni-Vincentelli, Alberto L. and Brayton, Robert K. and Fujita, M.},
    Title = {Combining Top-Down and Bottom-Up Approaches for ROBDD Construction},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2757.html},
    Number = {UCB/ERL M95/30},
    Abstract = {ROBDDs have traditionally been built in a bottom-up fashion, though the recursive use of Bryant's apply procedure [8], or the ITE [4] procedure.  With these methods, the peak memory utilization is often larger than the final ROBDD size.  Though methods like Dynamic Variable Reordering [21] have been proposed to reduce the memory utilization, such schemas have an associated time penalty. In this paper, we show that for a large number of applications, it is more efficient to construct the ROBDD by a suitable combination of top-down (decomposition based) and bottom-up (composition based) approaches.  We suitably select decomposition points during the construction of the ROBDD, and 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 a given combinational netlist, while the other is purely functional, making no assumptions about the underlying topology of the circuit.  We demonstrate the utility of our scheme on the standard benchmark circuits.  Our results show that for a given variable ordering, our method usually has significantly better time as well as memory characteristics than existing techniques. Our methods are easily extended to many variants of ROBDDs, and in that sense are powerful in their scope.}
}

EndNote citation:

%0 Report
%A Jain, J.
%A Narayan, A.
%A Coelho, C.
%A Khatri, S.P.
%A Sangiovanni-Vincentelli, Alberto L.
%A Brayton, Robert K.
%A Fujita, M.
%T Combining Top-Down and Bottom-Up Approaches for ROBDD Construction
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/ERL M95/30
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2757.html
%F Jain:M95/30