A study of composition schemes for mixed apply/compose based construction of ROBDDs

Author

Narayan, A. ; Khatri, S.P. ; Jain, J. ; Fujita, M. ; Brayton, R.K. ; Sangiovanni-Vincentelli, A.

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA

fYear

1996

fDate

3-6 Jan 1996

Firstpage

249

Lastpage

253

Abstract

Reduced Ordered Binary Decision Diagrams (ROBDDs) have traditionally been built in a bottom-up fashion. In this scheme, the intermediate peak memory utilization is often larger than the final ROBDD size, limiting the complexity of the circuits which can be processed using ROBDDS. Recently we showed 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. 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

Keywords

circuit CAD; graph theory; network synthesis; ROBDD; bottom up method; circuit CAD; composition; decomposition; heuristic algorithm; mixed apply/compose based construction; reduced ordered binary decision diagram; time-memory tradeoff; top down method; Benchmark testing; Binary decision diagrams; Boolean functions; Circuits; Costs; Data structures; Heuristic algorithms; Laboratories; Matrix decomposition;

fLanguage

English

Publisher

ieee

Conference_Titel

VLSI Design, 1996. Proceedings., Ninth International Conference on

Conference_Location

Bangalore

ISSN

1063-9667

Print_ISBN

0-8186-7228-5

Type

conf

DOI

10.1109/ICVD.1996.489494

Filename

489494