Paralelização de Algoritmos Genéticos Aplicados ao Problema de Placement em Clusters de Estações de Trabalho
Resumo
Este artigo analisa alternativas eficientes de paralelização de algoritmos genéticos aplicados ao problema de placement em circuitos VLSI ou em placas de circuito impresso, considerando o uso de PVM em uma plataforma formada por uma rede de estações de trabalho. Com o objetivo de obter-se inicialmente um algoritmo seqüencial capaz de produzir resultados próximos do ótimo, foi verificado, através de uma análise experimental extensa e detalhada, ser necessário ajustar corretamente os parâmetros de controle do algoritmo. Com estes parâmetros ajustados, o algoritmo mostrou-se bastante adequado à exploração de paralelismo. O artigo apresenta, então, uma proposta de implementação paralela do algoritmo que alcança uma redução significativa da necessidade de comunicação entre os processadores. Esta implementação produziu resultados de mesma qualidade que a versão seqüencial, porém com um speed-up aproximadamente igual a 6 em uma rede composta de 8 estações de trabalho.
Referências
Baluja, S., A Massively Distributed Parallel Genetic Algorithm (mdpGA), Technical Report, School of Computer Science, Carnegie Mellon University, 1992.
Geist A. et al., PVM3 Users 's Guide and Reference Manual, Oak Ridge National Laboratory, 1994.
Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
Kling, R.M. and Banerjee, P., ESP: A new standard cell placement package using simulated evolution, in Proc. 24th ACM/IEEE Design Automation Conference, 1987.
Mazumder P. and Mohan S., Wolverines: Standard Cell Placement on a Network of Workstations, IEEE Transactions on Computer-Aided Design, Vol 12, N. 9, September 1993.
Sechen, C., VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, 1988.
Spears W.M. and De Jong, K.A., On the Virtues of Parametrized Uniform Crossover, Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, Los Altos, CA, 1991.
Srinivas, M. and Patnaik, L.M., Genetic Algorithms: A Survey, IEEE Computer, p. 17-26, June 1994.
Syswerda, G., Uniform Crossover in Genetic Algorithms, in Proceedings of the Third lnternational Conference on Genetic Algorithms, Morgan Kaufmann Publishers, Los Altos, CA, 1989.
