Asynchronous reordering is the reordering that is triggered automatically by the increase of the number of nodes. Asynchronous reordering takes place when a new internal node must be created, and the number of nodes has reached a given threshold . (The threshold is adjusted by the package every time reordering takes place.)
Those procedures that do not create new nodes (e.g., procedures that count the number of nodes or minterms ) need not worry about asynchronous reordering: No special precaution is necessary in writing them.
Procedures that only manipulate decision diagrams through the exported functions of the CUDD package also need not concern themselves with asynchronous reordering. (See Section 3.2.1 for the one exception.)
The remaining class of procedures is composed of functions that visit the diagrams and may create new nodes. All such procedures in the CUDD package are written so that they can be interrupted by dynamic reordering. The general approach followed goes under the name of ``abort and retry ." As the name implies, a computation that is interrupted by dynamic reordering is aborted and tried again.
A recursive procedure that can be interrupted by dynamic reordering (an interruptible procedure from now on) is composed of two functions. One is responsible for the real computation. The other is a simple wrapper , which tests whether reordering occurred and restarts the computation if it did.
Asynchronous reordering of BDDs and ADDs can only be triggered inside cuddUniqueInter , when a new node is about to be created. Likewise, asynchronous reordering of ZDDs can only be triggered inside cuddUniqueInterZdd . When reordering is triggered, three things happen:
The recursive procedure that receives a NULL value from cuddUniqueInter must free all intermediate results that it may have computed before, and return NULL in its turn.
The wrapper function does not decide whether reordering occurred based on the NULL return value, because the NULL value may be the result of lack of memory. Instead, it checks the reordered flag.
When a recursive procedure calls another recursive procedure that may cause reordering, it should bypass the wrapper and call the recursive procedure directly. Otherwise, the calling procedure will not know whether reordering occurred, and will not be able to restart. This is the main reason why most recursive procedures are internal, rather than static. (The wrappers, on the other hand, are mostly exported.)