Introduction

The initiative of this package is to experiment BDD implementations using Java's high-level languge features such as object-oriented design and garbage collection. Automatic memory management is a key component of BDD packages implemented in C. Popular BDD packages, e.g, Cudd and BuDDy , use a simple reference counting algorithm to manage allocated BDD nodes. (JavaBDD is a Java implementation of BuDDy, and it is more like a C-style program.) There are works on using other GC algorithms.

Garbage collection is the default memory management scheme of the Java programming language. Java programmers are freed from explict object deallocation. A modern JVM may have implemented various GC algorithms. A Java BDD package could utilize the GC support from the language instead of re-implementing a GC by itself. In Java, GC is transparent to applications except some limited interactions provided by java.lang.ref package. In summary, SableJBDD uses following Java langauge features to implement key BDD data structures:

• it is platform-form independent, can run on JDK 1.2 or later versions,
• different types of unique table implementation: regular, weak, phantom references,
• various caches (ITE, apply, replace, etc.) are implemented by either soft or regular references, and
• multi-way caches are supported.

From applications, an efficient and native Java BDD package is desirable for tools written in Java. The object-oriented design and finite-domain interface are suitable for high-level specifications.

Our future work includes improving the efficiency and complete the functionarity of the package:

• the package does intensive object allocations, which triggers garbage collections frequently. This can be improved by pooling dead BDD nodes.
• almost all BDD operations are implemented as recursive calls, transforming them to loops could potentially improve the performance.
• dynamic reordering is not supported right now.

Downloads

Documentation

Acknowledgement

Last updated: $Date: 2004/04/06 21:05:27 $