loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
27th ACM/IEEE Design Automation Conference (DAC '90)
Orlando, FL, USA
June 24-June 28
ISBN: 0-89791-363-9
Brace, Dept. of Electr. & Comput. Eng., Carnegie Mellon Univ., Pittsburgh, PA, USA
Efficient manipulation of Boolean functions is an important component of many computer-aided design tasks. A package for manipulating Boolean functions based on the reduced, ordered, binary decision diagram (ROBDD) representation is described. The package is based on an efficient implementation of the if-then-else (ITE) operator. A hash table is used to maintain a strong canonical form in the ROBDD and memory use is improved by merging the hash table and the ROBDD into a hybrid data structure. A memory function for the recursive ITE algorithm is implemented using a hash-based cache to decrease memory use. Memory function efficiency is improved by using rules that detect when equivalent functions are computed. The usefulness of the package is enhanced by an automatic and low-cost scheme for recycling memory. Experimental results are given to demonstrate why various implementation trade-offs were made. These results indicate that the package described is significantly faster and more memory-efficient than other ROBDD implementations described in the literature.
Index Terms:
reduced ordered binary decision diagram representation, memory recycling, Boolean functions, computer-aided design, if-then-else, hash table, canonical form, hybrid data structure, recursive ITE algorithm, hash-based cache, implementation trade-offs, ROBDD implementations
Citation:
Brace, Rudell, Bryant, "Efficient implementation of a BDD package," dac, pp.40-45, 27th ACM/IEEE Design Automation Conference (DAC '90), 1990
Usage of this product signifies your acceptance of the Terms of Use.