Ordered binary decision diagrams (BDDs) are used in VLSI CAD, especially for the canonical representation of Boolean functions. In the last decade, the method of choice for optimizing this data structure was minimizing the number of nodes in the associated graph. However, recent works have shown that the number of paths is also important. In this work, minimizing the number of one-paths of BDDs is accomplished by an evolutionary algorithm (EA) acting on the permutation of variables. The optimal operator weights for the EA were determined by a parameter study. Experimental results demonstrate the efficiency of our approach.

Heuristic algorithms for coloring the edges of large undirected single-edge graphs with (or very close to) the minimal number of colors are presented. Compared to simulated annealing and a grouping genetic algorithm for small graphs, the heuristics were not only faster by orders of magnitude, but almost all solutions had the optimal color number; the rest differed by at most two colors. For large graphs, the heuristics were validated by an evolutionary algorithm. Here, the heuristics often found an optimum or a solution very close to it.

We present a new exact algorithm for finding the optimal variable ordering for reduced ordered binary decision diagrams (BDD's). The algorithm makes use of a lower bound technique known from very large scale integration design. Up to now this technique has been used only for theoretical considerations and it is adapted here for this purpose. Furthermore, the algorithm supports symmetry aspects and uses a hashing based data structure. Experimental results are given to demonstrate the efficiency of our approach. We succeeded in minimizing several functions, including adders with up to 64 variables, for which all other previously presented approaches fail.

In this paper we present a Genetic Algorithm (GA) for the Data Ordering Problem (DOP) where Don't Cares (DCs) are assigned during optimization. The DOP has large application in the area of low power design and circuit testing. We implemented a GA to solve this problem and discuss several applications. We carried out a large set of experiments. A comparison of our results to previously published demonstrates the efficiency of our approach.

A symbolic fault simulator is integrated in a Genetic Algorithm (GA) environment to perform Automatic Test Pattern Generation (ATPG) for synchronous sequential circuits. In a two phase algorithm, test length and fault coverage as well are optimized. However, there are circuits with bad random testability properties, that are also hard to test using genetically optimized test patterns. Thus, deterministic aspects are included in the GA environment to improve fault coverage. Experiments demonstrate that tests with higher fault coverages and considerably shorter test sequences than in previously presented approaches are obtained.

The shared binary decision diagram (SBDD) with negative edge attributes can represent many functions in a compact form if a proper variable ordering is used. In this work we describe a technique for reordering the variables in an SBDD to reduce the size of the data structure. We use a heuristic to formulate a technique for the reordering problem based on probability metrics.

We present a new exact algorithm for finding the optimal variable or deringfor r educ edordered Binary Decision Diagrams (BDDs). The algorithm makes use of a lower bound technique known from VLSI design.Up to now this technique has been use donly for the oreticalconsider ationsand it is adapte dhere for our purp ose. Furthermore, the algorithm supports symmetry aspects and makes use of a hashing b aseddata structure. Exp erimental esults are given to demonstrate the efficiency of our appr oach. We succeeded in minimizing adder functions with up to 64 variables, while all other pr eviously pr esente d appr oaches fail.

Ordered Kronecker Functional Decision Diagrams (OKFDDs) are a data structure for efficient representation and manipulation of Boolean functions. OKFDDs are very sensitive to the chosen variable ordering and the decomposition type list, i.e. the size may vary from linear to exponential. In this paper we present an Evolutionary Algorithm (EA) that learns good heuristics for OKFDD minimization starting from a given set of basic operations. The difference to other previous approaches to OKFDD minimization is that the EA does not solve the problem directly. Rather, it develops strategies for solving the problem. To demonstrate the efficiency of our approach experimental results are given. The newly developed heuristics combine high quality results with reasonable time overhead.