Técnicas de otimização em memória para algoritmos genéticos usando computadores multicore
Resumo
Os algoritmos genéticos são heurísticas da computação evolucionária com características que permitem otimizações de memória em arquiteturas de computadores paralelos. Neste trabalho são apresentadas técnicas que tiram proveito destas características em relação a uma arquitetura específica, neste caso, de computadores com múltiplos núcleos e memória compartilhada. Os experimentos mostram que o ganho de desempenho em relação ao tempo de implementação motiva realizar tais procedimentos em algoritmos com casos similares.Referências
Chang, F.-C. and Huang, H.-C. (2009). A study on the cache miss rate in a genetic algorithm implementation. In Intelligent Information Hiding and Multimedia Signal Processing, 2009. IIH-MSP ’09. Fifth International Conference on, pages 795–798.
Cruz, E., Alves, M., and Navaux, P. (2010). Process mapping based on memory access traces. In Computing Systems (WSCAD-SCC), 2010 11th Symposium on, pages 72–79.
Dagum, L. and Menon, R. (1998). Openmp: An industry-standard api for shared-memory programming. IEEE Comput. Sci. Eng., 5(1):46–55.
De Jong, K. (2006). Evolutionary Computation:A Unied Approach. MIT Press.
Foster, C. (1972). Computer architecture. Computer, 5(2):18–19.
Gabb, H., Corden, M., Rosenquist, T., Fischer, P., Fedorova, J., Breshears, C., Zipplies, T., Tsymbal, V., Akyil, L., Pegushin, A., Kukanov, A., Petersen, P., Voss, M., Tersteeg, A., and Hoeinger, J. (2009). Intel Guide for Developing Multithreaded Applications. Intel Corporation.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition.
Holland, J. (1959). A universal computer capable of executing an arbitrary number of subprograms simultaneously. In Papers Presented at the December 1-3, 1959, Eastern Joint IRE-AIEE-ACM Computer Conference, IRE-AIEE-ACM ’59 (Eastern), pages 108–113, New York, NY, USA. ACM.
Holland, J. H. (1975). Adaptation in Natural and Articial Systems. University of Michi gan Press, Ann Arbor, MI, USA.
Innity, R. (2008). BareMetal Operating System.
INTEL CORPORATION (2011). Especicações Intel core i5-2400. online.
Patterson, D. A. and Hennessy, J. L. (2007). Computer Organization and Design: The Hardware/Software Interface. Third Edition, Revised. Morgan Kaufmann, 3 edition.
Paz, C. E. (1998). A Survey of Parallel Genetic Algorithms.
Pedemonte, M., Alba, E., and Luna, F. (2011). Bitwise operations for GPU implementation of genetic algorithms. In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO ’11, pages 439–446, New York, NY, USA. ACM.
Silva, H. and Martins, C. A. (2012). Avaliação de implementações do algoritmo genético paralelo para solução do problema do caixeiro viajante usando openmp e pthreads. In WSCAD-WIC 2012.
Soares, G. L. (1997). Algoritmos genético: Estudo, novas técnicas e aplicações. Master’s thesis, Universidade Federal de Minas Gerais, Conselho Nacional de Desenvolvimento Cientíco e Tecnológico.
Stallman, R. M. and Community, G. D. (2009). Using The GNU Compiler Collection: A GNU Manual For GCC Version 4.3.3. CreateSpace, Paramount, CA.
Stroustrup, B. (2013). The C++ Programming Language, 4th Edition. Addison-Wesley Professional, 4 edition.
Trobec, R., Vajtersic, M., and Zinterhof, P., editors (2009). Parallel Computing: Nume rics, Applications, and Trends. Springer.
Viana, I. E. M., Machado-Coelho, T. M., Silva, H. H., Drumond, L., and Martins, C. A. P. S. (2009). Valorização acadêmica no processo de formação de um verdadeiro cientista da computação. In Anais X Simpósio em Sistemas Computacionais, volume X, pages 103–106. Workshop sobre Educação em Arquitetura de Computadores.
Widmer, N. S. and Tocci, R. J. (2011). Sistemas digitais. Pearson.
Cruz, E., Alves, M., and Navaux, P. (2010). Process mapping based on memory access traces. In Computing Systems (WSCAD-SCC), 2010 11th Symposium on, pages 72–79.
Dagum, L. and Menon, R. (1998). Openmp: An industry-standard api for shared-memory programming. IEEE Comput. Sci. Eng., 5(1):46–55.
De Jong, K. (2006). Evolutionary Computation:A Unied Approach. MIT Press.
Foster, C. (1972). Computer architecture. Computer, 5(2):18–19.
Gabb, H., Corden, M., Rosenquist, T., Fischer, P., Fedorova, J., Breshears, C., Zipplies, T., Tsymbal, V., Akyil, L., Pegushin, A., Kukanov, A., Petersen, P., Voss, M., Tersteeg, A., and Hoeinger, J. (2009). Intel Guide for Developing Multithreaded Applications. Intel Corporation.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition.
Holland, J. (1959). A universal computer capable of executing an arbitrary number of subprograms simultaneously. In Papers Presented at the December 1-3, 1959, Eastern Joint IRE-AIEE-ACM Computer Conference, IRE-AIEE-ACM ’59 (Eastern), pages 108–113, New York, NY, USA. ACM.
Holland, J. H. (1975). Adaptation in Natural and Articial Systems. University of Michi gan Press, Ann Arbor, MI, USA.
Innity, R. (2008). BareMetal Operating System.
INTEL CORPORATION (2011). Especicações Intel core i5-2400. online.
Patterson, D. A. and Hennessy, J. L. (2007). Computer Organization and Design: The Hardware/Software Interface. Third Edition, Revised. Morgan Kaufmann, 3 edition.
Paz, C. E. (1998). A Survey of Parallel Genetic Algorithms.
Pedemonte, M., Alba, E., and Luna, F. (2011). Bitwise operations for GPU implementation of genetic algorithms. In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO ’11, pages 439–446, New York, NY, USA. ACM.
Silva, H. and Martins, C. A. (2012). Avaliação de implementações do algoritmo genético paralelo para solução do problema do caixeiro viajante usando openmp e pthreads. In WSCAD-WIC 2012.
Soares, G. L. (1997). Algoritmos genético: Estudo, novas técnicas e aplicações. Master’s thesis, Universidade Federal de Minas Gerais, Conselho Nacional de Desenvolvimento Cientíco e Tecnológico.
Stallman, R. M. and Community, G. D. (2009). Using The GNU Compiler Collection: A GNU Manual For GCC Version 4.3.3. CreateSpace, Paramount, CA.
Stroustrup, B. (2013). The C++ Programming Language, 4th Edition. Addison-Wesley Professional, 4 edition.
Trobec, R., Vajtersic, M., and Zinterhof, P., editors (2009). Parallel Computing: Nume rics, Applications, and Trends. Springer.
Viana, I. E. M., Machado-Coelho, T. M., Silva, H. H., Drumond, L., and Martins, C. A. P. S. (2009). Valorização acadêmica no processo de formação de um verdadeiro cientista da computação. In Anais X Simpósio em Sistemas Computacionais, volume X, pages 103–106. Workshop sobre Educação em Arquitetura de Computadores.
Widmer, N. S. and Tocci, R. J. (2011). Sistemas digitais. Pearson.
Publicado
08/10/2014
Como Citar
SILVA, Harison; MARTINS, Carlos; SOARES, Gustavo.
Técnicas de otimização em memória para algoritmos genéticos usando computadores multicore. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 15. , 2014, São José dos Campos.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 15-26.
DOI: https://doi.org/10.5753/wscad.2014.14996.
