Next: Allowing Asynchronous Reordering
Up: Programmer's Manual
Previous: The Cache
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:
- The collision lists should be short
to keep access time down.
- 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:
- 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.
- 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:
- If the unique table is already large, only slow growth is
possible.
- 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: Allowing Asynchronous Reordering
Up: Programmer's Manual
Previous: The Cache
Fabio Somenzi
Thu Sep 24 23:44:34 MDT 1998