Compositional Techniques for Mixed Bottom-Up/Top-Down Constructions of ROBDDs

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

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

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

Reduced Ordered Binary Decision Diagrams (ROBDDs) have traditionally been built in a bottom-up fashion, through the recursive use of Bryant's apply procedure [4], or the ITE [2] procedure. With these methods, the intermediate peak memory utilization is often larger than the final ROBDD size. This peak memory requirement limits the complexity of the circuits which can be processed using ROBDDs. Recently it was shown in [9] that for a large number of applications, the peak memory requirement can be substantially reduced by a suitable combination of bottom-up (decomposition based) and top-down (composition based) approaches of building ROBDDs. This approach consists of selecting suitable decomposition points during the construction of the ROBDD using the apply procedure, followed by a symbolic composition to obtain the final ROBDD. In this paper, we focus on the composition process. We detail four heuristic algorithms for finding good composition orders, and compare their utility on a set of standard benchmark circuits. Our schemes offer a matrix of time-memory tradeoff points.

BibTeX citation:

@techreport{Narayan:M95/51,
    Author = {Narayan, A. and Khatri, S.P. and Jain, J. and Fujita, M. and Brayton, Robert K. and Sangiovanni-Vincentelli, Alberto L.},
    Title = {Compositional Techniques for Mixed Bottom-Up/Top-Down Constructions of ROBDDs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2801.html},
    Number = {UCB/ERL M95/51},
    Abstract = {Reduced Ordered Binary Decision Diagrams (ROBDDs) have traditionally been built in a bottom-up fashion, through the recursive use of Bryant's apply procedure [4], or the ITE [2] procedure. With these methods, the intermediate peak memory utilization is often larger than the final ROBDD size. This peak memory requirement limits the complexity of the circuits which can be processed using ROBDDs. Recently it was shown in [9] that for a large number of applications, the peak memory requirement can be substantially reduced by a suitable combination of bottom-up (decomposition based) and top-down (composition based) approaches of building ROBDDs. This approach consists of selecting suitable decomposition points during the construction of the ROBDD using the apply procedure, followed by a symbolic composition to obtain the final ROBDD. In this paper, we focus on the composition process. We detail four heuristic algorithms for finding good composition orders, and compare their utility on a set of standard benchmark circuits. Our schemes offer a matrix of time-memory tradeoff points.}
}

EndNote citation:

%0 Report
%A Narayan, A.
%A Khatri, S.P.
%A Jain, J.
%A Fujita, M.
%A Brayton, Robert K.
%A Sangiovanni-Vincentelli, Alberto L.
%T Compositional Techniques for Mixed Bottom-Up/Top-Down Constructions of ROBDDs
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/ERL M95/51
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2801.html
%F Narayan:M95/51