A cache-based parallel genetic algorithm for the BDD variable ordering problem
Resumo
Binary Decision Diagrams (BDDs) have proved to be a powerful representation for Boolean functions. Particulary, they are a very useful data structure for the symbolic model checking of a digital circuits and other finite state systems, as well as other problems. Nevertheless, the size of the BDD representation of these functions is highly dependent on the order of the function arguments, also called variables, and to find such good ordering is an NP-Complete problem. Many heuristics have been proposed to solve this problem, as our Parallel Genetic Algorithm presented in [4], where we got excellent results in terms of paralelization. Now, we present a new version of our algorithm, this time with a cache system, together with experimental results.
Referências
R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 1986.
E. Cantú-Paz. A summary of research on parallel genetic algorithms. Technical report, Illinois Genetic Algorithms Laboratory, 1995.
U. S. Costa, D. Debarba, and A. M. Moreira. Variable ordering of bdds with parallel genetic algorithms. In Proceedings of PDPTA’2000, 2000.
P. S. de Souza. Asynchronous Organizations for Multi-Algorithm Problems. PhD thesis, Department of Electrical and Computer Engineering, Carnegie Mellon University, 1993.
H. Fujii, O. Ootomo, and C. Hori. Interleaving based variable ordering methods for ordered binary decision diagrams. In 1996 IEEE/ACM International Conference on Computer-Aided Design (ICCAD’93), pages 38–41. IEEE/ACM, 1993.
A. Geist et al. PVM: Parallel Virtual Machine – A User’s Guide and Tutorial for Networked Parallel Computing. MIT Press, 1994.
K. Hwang and P. A. Briggs. Computer Architecture and Parallel Processing. McGraw-Hill, 3rd edition, 1987.
D. Long. bddlib – a binary decision diagram (bdd) package. Available on [link].
F. Marin, O. Trellez-Salazar, and P. Sandon. Genetic algorithms on an message-passing architecture using PVM applied on the routing problem. In Springer-Verlag, editor, Parallel Problem Solving from Nature – PPSN III. Lecture Notes in Computer Science, pages 534–543, 1994.
K. E. Partridge. Bddtcl: an environment for visualizing and manipulating binary decision diagrams. In CHI’96 conference companion on human factors in computing systems, pages 111–112, 1996.
M. G. Resende. Parallel metaheuristics for combinatorial optimization. International School on Advanced Algorithmic Techniques for Parallel Computation with Applications, 1996.
B. Yang, R. E. Bryant, D. R. O’Hallaron, A. Biere, O. Shmueli, G. Janssen, R. K. Ranjan, and F. Somenzi. A performance study of bdd-based model checking. In FMCAD’98 – Formal Methods in Computer-Aided Design, number 1512 in Lecture Notes in Computer Science, Palo Alto, CA, 1998. Springer-Verlag.
