wld - a C++ library for decision diagrams

1.1

Word-level decision diagrams have become an interesting alternative to bit-level decision diagrams, e.g. Bryant's OBDDs.

wld is a software package written in C++ which provides several word-level decision diagrams (*BMDs, K*BMDs, ....) types as well as OBDDs. The wld library provides application independent interfaces to easily adapt your application to the package. The structural concept of the package is analogous to other popular decision diagram packages, i.e. a DD manager provides unique tables, computed tables and memory caches. Furthermore, modern algorithms for DD minimization are available.

Please report bugs or other critics to herbstri@informatik.uni-freiburg.de.

Installation

Obtaining the package

Please appreciate that the author wants to know who is using the wld package. Do not hesitate to contact the author for obtaining the package sources: herbstri@informatik.uni-freiburg.de

Prerequisites

The package is tested under SUN Solaris(TM) and Linux, using GNU g++ version 2.8.1 or later.

For handling multi-precision arithmetic the wld package makes use of the GNU multi precision library gmp, version 2.0.2 or later. The gmp package is available at ftp.gnu.org/gnu/gmp.

You need the graphviz package from http://www.research.att.com/sw/tools/graphviz for

• viewing DDs exported from wld using the .dot-format.
• viewing dependency diagrams of classes, .... in this documentation.

For installing this documentation on your system you need doxygen from http://www.doxygen.org.

Compiling and Linking

In the following $WLD denotes the installation directory of wld.

The package provides a Makefile in $WLD/bin which contains targets to generate several package libraries. Since some libraries need the gmp library, you have to adjust the corresponding path variables in the Makefile (see the GMP_* variables).

For the moment, the following targets are supported:

• libfwld. compile status: optimized, gmp included: no.
• libdwld. compile status: debug, gmp included: no.
• libpwld. compile status: profile. gmp included. no.
• libfmpwld. compile status: optimized, gmp included: yes.
• libdmpwld. compile status: debug, gmp included: yes.
• libpmpwld. compile status: proficle. gmp included. yes.

Please note: For checking wether to include the gmp library or not, a define statement is given on the command line by adding -D_MP_WA_ (multi-precision weight arithmetic) to the g++ options (see variable GMP_DEFINES in the Makefile). Therefore, do not use a #define _MP_WA_ directive in your applications except when you're writing code that depends directly on the gmp library.

In 1986 Bryant introduced Ordered Binary Decision Diagrams representing functions which are still widely used for synthesis, testing and verification in VLSI CAD. In the meantime much work has been done in this area and many extensions to OBDDs were developped. But all in all, those decision diagrams were only able to represent functions which have a boolean image. Therefore these decision diagrams are called bit-level decision diagrams .

In the beginning of the 1990s variants of bit-level decision diagrams were introduced which were able to represent functions . Since these decision diagrams can represent functions which map a boolean vector into the integer values, they are called word-level decision diagrams.

The following table lists the most important decision diagrams which are supported by the wld package.

• bit-level decision diagrams
  1. Ordered Binary Decision Diagram s(OBDD)
• word-level deicion diagrams
  1. Multiplicative Binary Moment Diagram (*BMD)
  2. Positive Multiplicative Binary Moment Diagram (p*BMD)
  3. Kronecker Multiplicative Binary Moment Diagram (K*BMD)
  4. Positive Kronecker Multiplicative Binary Moment Diagram (K*BMD)

Implementation details

The package consists of basic classes for DD managers, unique tables, computed tables, ...

The manager

A DD manager is an object by which all DD related operations are handled, i.e. creation of variables, synthesis of DDs, analyzing DDs, exporting DD data, and so on. A manager provides unique tables for canonical handling of nodes and edges, computed tables for storing already computed results during synthesis, structures for handling variable orders and decomposition type lists. Additionally a manager provides algorithms for DD synthesis, minimization of DD, setting and accessing manager parameters, and so.

Unique tables

The unique tables to ensure canonicity of the created DD are implemented as dynamic hash tables, therefore providing fast access to nodes and edges. The hash tables are dynamic w.r.t. to the size of the hash table so that they dynamically are adapted to application.

Computed table

The computed table is mandatory for efficient DD synthesis. It stores already performed DD operations and aims to cache often used operations, so that these operations must not be recomputed.

Garbage collection

All DD nodes and edges provide a reference counter, counting the incoming pointers to a node or edge. Objects with reference count greater 0 are called alive, i.e. they are in use either by an external reference (the user) or by an internal reference (temporary results during synthesis). Objects with reference count equal to 0 are called dead, i.e. they are not in use. Dead objects are not needed anymore and can therefore be removed. The removal of dead objects is done by the garbage collection. The memory allocated by dead objects is not released to the operating system, but it is kept in so called memory caches. wld provides memory caches for edges and nodes. The garbage collection is called from time to time (depending on the ration between alive edges and dead edges).

The following is a brief overview of publications related to the wld package.

• Brace, K.S., Rudell, R.L. and Bryant, R.E., "Efficient implementation of a BDD package", in Design Automation Conference (DAC), pages 40-45, 1990.
• Bryant, R.E., "Graph-based algorithms for boolean function manipulation", in IEEE Transations on Computers, 35(8):677-691,1986.
• Bryant, R.E. and Chen, Y-A., "Verification of arithmetic functions with binary moment diagrams", in Design Automation Conference (DAC), pages 535-541, 1995.
• Drechsler, R., Sarabi, A., Theobald, M., Becker, B. and Perkowski, M.A., "Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams", in Design Automation Conference (DAC), pages 415-419, 1994.
• Drechsler, R., Becker, B. and Ruppertz, S., "The K*BMD: A verification data structure", in IEEE Design & Test of Computers, pages 2-8,1996.
• Drechsler, R. and Becker, B., "Graphenbasierte Funktionsdarstellung", B.G. Teubner Stuttgart, 1998.
• Drechsler, R., Herbstritt, M. and Becker, B. "Grouping Heuristics for Word-Level Decision Diagrams", in IEEE International Symposium on Circuits and Systems (ISCAS), 1999.
• Ellson, J., et. al., "The Graphviz package", http://www.research.att.com/sw/tools/graphviz
• Hoereth, S. and Drechsler, R., "Dynamic Minimzation of word-level decision diagrams", in Design, Automation and Test Europe (DATE), pages 612-617, 1998.
• Rudell, R., "Dynamic variable ordering for ordered binary decsion diagrams", in International Conference on Computer Aided Design (ICCAD), pages 42-47, 1993.