Dynamic variable ordering for ordered binary decision diagrams
Richard L. Rudell · International Conference on Computer Aided Design · 1993
The ordered binary decision diagram (OBDD) has proven useful in many applications as an efficient data structure for representing and manipulating Boolean functions. A serious drawback of OBDD's is the need for application-specific heuristic algorithms to order the variables before processing. Further, for many problem instances in logic synthesis, the heuristic ordering algorithms which have been proposed are insufficient to allow OBDD operations to complete within a limited amount of memory. The paper proposes a solution to these problems based on having the OBDD package itself determine and maintain the variable order. This is done by periodically applying a minimization algorithm to reorder the variables of the OBDD to reduce its size. A new OBDD minimization algorithm, called the sifting algorithm, is proposed and appears especially effective in reducing the size of the OBDD. Experiments with dynamic variable ordering on the problem of forming the OBDD's for the primary outputs of a combinational circuit show that many computations complete using dynamic variable ordering when the same computation fails otherwise.
Cited by 842 works. doi:10.5555/259794.259802
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Efficient implementation of a BDD package
- Logic verification using binary decision diagrams in a logic synthesis environment
- Evaluation and improvement of Boolean comparison method based on binary decision diagrams
- Proving circuit correctness using formal comparison between expected and extracted behaviour
- Shared binary decision diagram with attributed edges for efficient Boolean function manipulation
- Proving circuit correctness using formal comparison between expected and extracted behaviour
- Shared binary decision diagram with attributed edges for efficient Boolean function manipulation
- Minimization of binary decision diagrams based on exchanges of variables
- On variable ordering of binary decision diagrams for the application of multi-level logic synthesis