next up previous index
Next: Allowing Asynchronous Reordering Up: Programmer's Manual Previous: The Cache

The Unique Table


A recursive procedure typically splits the operands by expanding with respect to the topmost variable. Topmost in this context refers to the variable that is closest to the roots in the current variable order. The nodes, on the other hand, hold the index, which is invariant with reordering. Therefore, when splitting, one must use the permutation  array maintained by the package to get the right level. Access to the permutation array is provided by the macro cuddI  for BDDs and ADDs, and by the macro cuddIZ  for ZDDs.

The unique table consists of as many hash  tables as there are variables in use. These has tables are called unique subtables. The sizes of the unique subtables are determined by two criteria:

  1. The collision  lists should be short to keep access time down.
  2. There should be enough room for dead  nodes, to prevent too frequent garbage  collections.
While the first criterion is fairly straightforward to implement, the second leaves more room to creativity. The CUDD package tries to figure out whether more dead node should be allowed to increase performance. (See also Section 3.4.) There are two reasons for not doing garbage collection too often. The obvious one is that it is expensive. The second is that dead nodes may be reclaimed , if they are the result of a successful cache lookup. Hence dead nodes may provide a substantial speed-up if they are kept around long enough. The usefulness of keeping many dead nodes around varies from application to application, and from problem instance to problem instance. As in the sizing of the cache, the CUDD package adopts a ``reward-based " policy to decide how much room should be used for the unique table. If the number of dead nodes reclaimed is large compared to the number of nodes directly requested from the memory manager, then the CUDD package assumes that it will be beneficial to allow more room for the subtables, thereby reducing the frequency of garbage collection. The package does so by switching between two modes of operation:
  1. Fast growth : In this mode, the ratio of dead nodes to total nodes required for garbage collection is higher than in the slow growth mode to favor resizing of the subtables.
  2. Slow growth : In this mode keeping many dead nodes around is not as important as keeping memory requirements low.
Switching from one mode to the other is based on the following criteria:
  1. If the unique table is already large, only slow growth is possible.
  2. If the table is small and many dead nodes are being reclaimed, then fast growth is selected.
This policy is especially effective when the diagrams being manipulated have lots of recombination. Notice the interplay of the cache sizing and unique sizing: Fast growth normally occurs when the cache hit rate is large. The cache and the unique table then grow in concert, preserving a healthy balance between their sizes.

next up previous index
Next: Allowing Asynchronous Reordering Up: Programmer's Manual Previous: The Cache

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