BDD minimization by scatter search
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems - Tập 21 Số 8 - Trang 974-979 - 2002
Tóm tắt
Reduced-ordered binary decision diagrams (BDDs) are a data structure for representation and manipulation of Boolean functions. The variable ordering largely influences the size of the BDD, varying from linear to exponential. In this paper, the authors study the BDD minimization problem based on scatter search optimization. Scatter search offers a reasonable compromise between quality (BDD reduction) and time. On smaller benchmarks it delivers almost optimal BDD size with less time than the exact algorithm. For larger benchmarks it delivers smaller BDD sizes than genetic algorithm or simulated annealing at the expense of longer runtime.
Từ khóa
#Binary decision diagrams #Scattering #Boolean functions #Data structures #Logic design #Logic testing #Minimization #Benchmark testing #Genetic algorithms #Simulated annealingTài liệu tham khảo
10.1109/43.184839
tani, 1993, Complexity of the optimal variable ordering of a shared binary decision diagram
10.1109/ICCAD.1993.580029
10.1109/12.53586
jeong, 1993, an efficient method for optimal bdd ordering computation, Int Conf VLSI and CAD
10.1049/ip-cdt:19960789
bollig, 1995, simulated annealing to improve variable orderings for obdd's, Int Workshop Logic Synthesis
10.1109/12.537122
10.1109/43.833206
10.1109/43.905674
10.1109/12.736442
shiple, 1994, heuristic minimization of bdd's using don't cares, Proc Design Automation Conference, 225
10.1109/TC.1986.1676819
hung, 1997, heuristic symmetry reduction for invariant verification, Int Workshop on Logic Synthesis
10.1109/EDAC.1992.205975
10.1109/EDAC.1991.206358
glover, 0, a template for scatter search and path relinking, Artificial Evolution Lecture Notes in Computer Science, 1363, 13
glover, 2000, scatter search, Theory and Applications of Evolutionary Computation Recent Trends
minato, 1996, Binary Decision Diagrams and Applications for VLSI CAD, 10.1007/978-1-4613-1303-8
10.1109/43.743706
somenzi, 1998, CUDD CU Decision Diagram Package Release 2 3 0
10.1109/EURDAC.1993.410627