Dynamic variable ordering for ordered binary decision diagrams

Dynamic variable ordering for ordered binary decision diagrams,10.1145/259794.259802,Richard L. Rudell

Dynamic variable ordering for ordered binary decision diagrams   (Citations: 666)
BibTex | RIS | RefWorks Download
The Ordered Binary Decision Diagram OBDI)) has proven useful in many applications as an efficient data structure for reprtxenting and manipulating Boolean functions. A serious drawback of OBDD’s is the need for application-specijic 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. In this paper, I propose 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 eflective in reducing the size of the OBDD.Experiments with dynamic variable ordering on the problem of forming the OEIDD’s for the primary outputs of a combinational circuit show that many computations comp!ete using dynamic variable ordering when the same computation fails otherwise.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: