next up previous index
Next: Initializing and Shutting Down Up: User's Manual Previous: Compiling and Linking

Basic Data Structures

 

Nodes

 

BDDs, ADDs, and ZDDs are made of DdNode's. A DdNode  (node  for short) is a structure with several fields. Those that are of interest to the application that uses the CUDD package as a black box are the variable index , the reference  count, and the value. The remaining fields are pointers that connect nodes among themselves and that are used to implement the unique  table. (See Section 3.2.2.)

The index field holds the name of the variable that labels the node. The index of a variable is a permanent attribute that reflects the order  of creation. Index 0 corresponds to the variable created first. On a machine with 32-bit pointers, the maximum number of variables is the largest value that can be stored in an unsigned short integer minus 1. The largest index is reserved for the constant  nodes. When 64-bit pointers are used, the maximum number of variables is the largest value that can be stored in an unsigned integer minus 1.

When variables are reordered to reduce the size of the decision diagrams, the variables may shift in the order, but they retain their indices. The package keeps track of the variable permutation  (and its inverse). The application is not affected by variable reordering , except in one case. If the application uses generators  (Cudd_ForeachCube   and Cudd_ForeachNode  ) and reordering is enabled, then it must take care not to call any operation that may create new nodes (and hence possibly trigger reordering). This is because the cubes (i.e., paths) and nodes of a diagram change as a result of reordering.

The CUDD package relies on garbage  collection to reclaim the memory used by diagrams that are no longer in use. The scheme employed for garbage collection is based on keeping a reference  count for each node. The references that are counted are both the internal references (references from other nodes) and external references (typically references from the calling environment). When an application creates a new BDD , ADD  , or ZDD , it must increase its reference count explicitly, through a call to Cudd_Ref . Similarly, when a diagram is no longer needed, the application must call Cudd_RecursiveDeref  (for BDDs and ADDs) or Cudd_RecursiveDerefZdd  (for ZDDs) to ``recycle " the nodes of the diagram.

Terminal  nodes carry a value. This is especially important for ADDs. By default, the value is a double . To change to something different (e.g., an integer), the package must be modified and recompiled. Support for this process is currently very rudimentary.

The Manager

  

All nodes used in BDDs, ADDs, and ZDDs are kept in special hash  tables called the unique  tables. Specifically, BDDs and ADDs share the same unique table, whereas ZDDs have their own table. As the name implies, the main purpose of the unique table is to guarantee that each node is unique; that is, there is no other node labeled by the same variable and with the same children. This uniqueness property makes decision diagrams canonical . The unique  tables and some auxiliary data structures make up the DdManager  (manager  for short). Though the application that uses only the exported functions needs not be concerned with most details of the manager, it has to deal with the manager in the following sense. The application must initialize the manager by calling an appropriate function. (See Section 3.3.) Subsequently, it must pass a pointer to the manager to all the functions that operate on decision diagrams.

With the exception of a few statistical counters  , there are no global  variables in the CUDD package.gif Therefore, it is quite possible to have multiple managers simultaneously active in the same application. It is the pointers to the managers that tell the functions on what data they should operate.

Cache

  

Efficient recursive manipulation of decision diagrams requires the use of a table to store computed results. This table  is called here the cache  because it is effectively handled like a cache of variable but limited capacity. The CUDD package starts by default with a small cache, and increases its size until either no further benefit is achieved, or a limit size is reached. The user can influence this policy by choosing initial and limit values for the cache size.

Too small a cache will cause frequent overwriting of useful results. Too large a cache will cause overhead, because the whole cache is scanned every time garbage  collection takes place. The optimal parameters depend on the specific application. The default parameters work reasonably well for a large spectrum of applications.

The cache  of the CUDD package is used by most recursive functions of the package, and can be used by user-supplied functions as well. (See Section 4.4.)


next up previous index
Next: Initializing and Shutting Down Up: User's Manual Previous: Compiling and Linking

Fabio Somenzi
Tue May 12 18:47:58 MDT 1998