Implementation and Visualization of a BDD Package in JAVA
by Rolf Drechsler and Jochen Römmler
Abstract
Decision Diagrams (DDs) are often used in VLSI CAD systems for efficient
representation and manipulation of Boolean functions. The most popular
data structure are reduced ordered Binary Decision Diagrams (BDDs) [Bry86,DB98],
also called ROBDDs. They are part of almost all courses on function representation
in VLSI CAD education. BDDs are very sensitive to the variable ordering,
i.e. the size of a BDD (measured in the number of nodes) may vary from
linear to exponential.
Finding the optimal variable ordering is an NP-hard
problem and the best known algorithm has runtime exponential in the number
of variables. This is the reason why many authors presented heuristics
for finding good variable orderings from circuit descriptions in the last
few years. The most promising methods for BDD minimization are based on
dynamic variable ordering.
We describe the JAVA implementation of the BDD package JADE (=JAVA DEcision
diagram package). The BDD package has an interactive interface that allows
to display the construction and minimization process and by this gives
further insight in the data structure. Almost every formula can be entered
and immediately translated into a corresponding BDD. Users can easily
change the global variable ordering in a given BDD simply by selecting
a certain variable with the mouse and exchange its position with adjacent
variables. The effects on the BDD can be seen immediately. This allows
the user to manually optimize the BDD if the automatic minimization algorithm
returns unsatisfying results. The view area can also be changed using
the mouse in order to zoom into very large structures. New minimization
algorithms can easily be evaluated and their performance can be analyzed.
The tool can be directly applied in on-line learning and tele-education.
The user gets “hands-on” experience while working with the
software.
GUI - Graphical User Interface
The visualization of BDDs is an important topic, since this gives some
feedback how well the minimization techniques, like sifting, are doing.
For this, most BDD packages presented so far have an output option to
display the graph already build. But none of them allow any user interaction
or visualization of the BDD manipulation, i.e. minimization and graph
construction. The key advantage of this BDD package implementation is
the ability to change the global variable ordering. This can be achieved
in different ways. Another important improvement is the visualization
during automatic minimization using sifting heuristic and during BDD
construction.
In the following we briefly mention some features of the Graphical User
Interface (GUI) of our JAVA based BDD package (see figure below and [DR02]
for more details): trace mode, automatic minimization, setting the variable
ordering, interactively changing variable ordering, verbose mode, simple
input format, resizing the BDD, swap high/low edges, and keeping of configuration.
References
- [Bry86] R.E. Bryant. Graph - based algorithms for Boolean function manipulation.
IEEE Trans. on Comp., 35(8):677-691, 1986.
- [DB98] R. Drechsler and B. Becker. Binary Decision Diagrams - Theory
and Implementation. Kluwer Academic Publishers, 1998.
- [DR02] R. Drechsler and J. Römmler. Implementation and Visualization
of a BDD Package in JAVA, GI/ITG/GMM Workshop "Methoden und Beschreibungssprachen
zur Modellierung und Verifikation von Schaltungen und Systemen",
2002.
Download JADE
- User (binary) Package:
1.5.1 vom 20.März 2002,
jade-1.5.2.zip.
Bitte beachten Sie die Installationshinweise.
- Source-Code Release Package:
1.5.1 vom 20.März 2002,
jade-1.5.2-src.zip.
Enthaelt die komplette Entwicklungsumgebung inkl. Benutzerhandbuch,
Sourcecode-Dokumentation, Quelltexte, Grafiken, Skripte und Authoring Daten.
- Benutzerhandbuch
ansehen (online)
- Eine aktuelle Java Version bzw. Runtime Java Version gibt es für
verschiedene Plattformen
hier.
