Reduced ordered binary decision diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs depends on a chosen variable ordering, i.e. the size may vary from linear to exponential, and the existence of a polynomial algorithm to approximate the optimal variable ordering of BDDs implies P = NP. In this paper, a new approximate BDD minimization algorithm is presented which is based on weighted A*. When compared to the best known previous method, large gains in run time are observed whereas the degradation of solution quality is considerably smaller than for the previous method. The improved behavior now allows for a wider range of time/quality tradeoffs. Experimental results demonstrate the efficiency of the new approach.

For verification of complex system-on-chip designs often constraint-based randomization is used. This allows to simulate scenarios that may be difficult to generate manually. For the system description language SystemC the SystemC Verification (SCV) Library has been introduced. Besides advanced verification features like data introspection and transaction recording the SCV library enables constraint-based randomization forSystemC models. However, the SCV library has two disadvantages that restrict their practical use: There is no support of bit operators in SCV constraintsand the SCV constraint solver cannot guarantee a uniform distribution of the constraint solutions. In this paper we provide a detailed analysis of these problems and present solutions that have been integrated in the library.

Reduced ordered binary decision diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis and formal verification. In recent practical applications, BDDs are optimized with respect to new objective functions. In 1986, Bryant showed that, dependent on a chosen variable ordering, the size of BDDs can vary from linear to exponential. In this paper, we derive similar results for the sensitivity of BDDs with respect to path-related objective functions. First, we provide a theoretical view, giving examples for the large variation in the maximal path length and the expected path length in BDDs. This shows how important it is to choose a good or optimal variable ordering. Experimental results show the sensitivity of benchmark functions with respect to all considered objective functions

In this paper, we present new lower bounds on binary decision diagram (BDD) size. These lower bounds are derived from more general lower bounds that recently were given in the context of exact BDD minimization. The results presented in this paper are twofold. First, we gain deeper insight by looking at the theory behind the new lower bounds. Examples lead to a better understanding, showing that the new lower bounds are effective in situations where this is not the case for previous lower bounds and vice versa. Following the constraints in practice, we then compromise between run time and quality of the lower bounds. Finally, a clever combination of old and new lower bounds results in a final tight lower bound, yielding a significant improvement. Experimental results show the efficiency of our approach.

In this paper we present new lower bounds on BDD size. These lower bounds are derived from more general lower bounds that recently were given in the context of exact BDD minimization. The results presented in this paper are twofold: first, we gain deeper insight by looking at the theory behind the new lower bounds. Examples lead to a better understanding, showing that the new lower bounds are effective in situations where this is not the case for previous lower bounds and vice versa. Following the constraints in practice, we then compromise between runtime and quality of the lower bounds. Finally, a clever combination of old and new lower bounds results in a final lower bound, yielding a significant improvement. Experimental results show the efficiency of our approach.

Reduced-ordered binary decision diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs depends on a chosen variable ordering, i.e., the size may vary from linear to exponential, and the problem of improving the variable ordering is known to be NP-complete. In this paper, a new exact BDD minimization algorithm called A/sup stute/ is presented. Here, ordered best-first search, i.e., the A/sup */ algorithm, is combined with a classical branch-and-bound (B&B) algorithm. A/sup */ operates on a state space large parts of which are pruned by a best-first strategy expanding only the most promising states. Combining A/sup */ with B&B allows to avoid unnecessary computations and to save memory. Experimental results demonstrate the efficiency of our approach.

Ordered binary decision diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis and formal verification. The size of the BDDs depends on a chosen variable ordering, i.e., the size may vary from linear to exponential, and the problem of Improving the variable ordering is known to be NP-complete. In this paper, we present a new exact branch and bound technique for determining an optimal variable order. In contrast to all previous approaches that only considered one lower bound, our method makes use of a combination of three bounds and, by this, avoids unnecessary computations. The lower bounds are derived by generalization of a lower bound known from very large scale integration design. They allow one to build the BDD either top down or bottom up. Experimental results are given to show the efficiency of our approach.