Analysis of the Performance of Genetic Algorithm Parallelized with OpenMP Through Execution Traces

Gabriella Lopes Andrade, Marcia Cristina Cera

Abstract


Run tracing allows you to identify issues affecting the performance of parallel applications. This work consists in evaluating the parallelization of a Genetic Algorithm applied to the Vehicle Routing Problem with OpenMP, where the performance obtained was not ideally expected. Being that it was possible to obtain a performance increase of 1.4 times in the architecture used, however, but still below ideal. Therefore, the general objective of this work is to investigate the causes of the low performance obtained by the Genetic Algorithm, performing an analysis from the execution traces. Our results showed that the parallelization of the Genetic Algorithm is according to the model in which it was implemented and to the set of instances of the target Vehicle Routing Problem used.


Keywords


Genetic Algorithms; OpenMP; Paralelization; Performance; Score-P; Tracking; Vampir; Vehicle Routing Problem

Full Text:

PDF

References


SCHNORR, L. M. Ana ́lise de desempenho de programas paralelos. In: Anais da ERAD/RS 2014. Alegrete, RS: SBC, 2014. p. 57–81.

GRESSLER, H. d. O.; CERA, M. C. O impacto da paralelizac ̧a ̃o com openmp no desempenho e na qualidade das soluc ̧o ̃es de um algoritmo gene ́tico. Revista Brasileira de Computac ̧a ̃o Aplicada, SBC, Porto Alegre, RS, p. 35–47, 2014.

REGO, C.; ALIDAEE, B. Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search. USA: Springer, 2006. (Operations Research/Computer Science Interfaces Series).

CHAPMAN, B.; JOST, G.; PAS, R. V. D. Using OpenMP: portable shared memory parallel programming. Cambridge, MA, USA: MIT Press, 2008.

ANDRADE, G. L.; CERA, M. C. Avaliando a paralelizac ̧a ̃o de um algoritmo gene ́tico com openMP. In: Anais do WSCAD-WIC 2016. Aracaju, SE: SBC, 2016. p. 68–73.

ANDRADE, G. L.; CERA, M. C. Avaliando o uso de sections openmp na paralelizac ̧a ̃o de um algoritmo gene ́tico. In: Anais do Sala ̃o Internacional de Ensino, Pesquisa e Extensa ̃o. Uruguaiana, RS: SBC, 2016.

ANDRADE, G. L.; CERA, M. C. Avaliac ̧a ̃o da eficieˆncia da paralelizac ̧a ̃o com sections OpenMP em um algoritmo gene ́tico atrave ́s de rastros de execuc ̧a ̃o. In: Anais do ERAD/RS 2017. Iju ́ı, RS: SBC, 2017. p. 68–73.

LINDEN, R. Algoritmos gene ́ticos: uma importante ferramenta da inteligeˆncia computacional. 2a. ed. Rio de Janeiro, RJ: Brasport, 2008.

PIOLA, T. d. F. Tracing de aplicac ̧o ̃es paralelas com informac ̧o ̃es de alto n ́ıvel de abstrac ̧a ̃o. Tese (Doutorado em F ́ısica Aplicada) — Instituto de F ́ısica de Sa ̃o Carlos, Universidade de Sa ̃o Paulo, Sa ̃o Carlos, 2007. Dispon ́ıvel em: ⟨http://www.teses.usp.br/teses/disponiveis/76/76132/ tde-25102007-114809/⟩. Acesso em: 18 de maio de 2016.

VI-HPS. Score-P User Manual 2.0.2. [S.l.], 2016. Dispon ́ıvel em: ⟨https://silc.zih.tu-dresden.de/scorep-current/ pdf/scorep.pdf⟩. Acesso em: 27 jul. 2018.

SHENDE, S. S.; MALONY, A. D. The tau parallel performance system. In: The International Journal of High Performance Computing Applications. Thousand Oaks, CA, USA: Sage, 2006. v. 20, n. 2, p. 287–311.

GWT-TUD GmbH. Vampir 9.1. [S.l.], 2016. Dispon ́ıvel em: ⟨https://www.vampir.eu/⟩. Acesso em: 15 ago. 2016.

COULOMB, K. et al. ViTE - Visual Trace Explorer. [S.l.], 2010. Dispon ́ıvel em: ⟨http://vite.gforge.inria.fr/index.php⟩. Acesso em: 23 jul. 2018.

WICKHAM, H. ggplot2. 2013. ⟨http://ggplot2.org/⟩. Acessado em 15/08/2017.

MATLOFF, N. The Art of R Programming: A Tour of Statistical Software Design. San Francisco: No Starch Press, 2011. (No Starch Press Series).

CHRISTOFIDES, N. et al. Combinatorial optimization. John Wiley & Sons, Chichester, UK, 1979.

DA ROSA, M. F. G.; CERA, M. C. Estudo preliminar sobre a escalabilidade de um algoritmo gene ́tico paralelizado com openmp. In: Anais da ERAD/RS 2015. Gramado, RS: SBC, 2015. p. 217–220.

DA ROSA, M. F. G.; CERA, M. C. Ana ́lise da escabilidade de um algoritmo gene ́tico paralelizado usando openmp. In: Anais do WSCAD-WIC 2015. Floriano ́polis, SC: SBC, 2015. p. 51–56.

CORMEN, T. H. et al. Introduction to Algorithms. 3. ed. Cambridge, Massachusetts, EUA: MIT Press, 2009.

GRIFFITHS, D.; GRIFFITHS, D. Use a Cabec ̧a! C. Rio de Janeiro, RJ: Alta Books Editora, 2013. (Use a Cabec ̧a!).

WHITLEY, D.; RANA, S.; HECKENDORN, R. B. The island model genetic algorithm: On separability, population size and convergence. Journal of Computing and Information Technology, University Computing Centre Zagreb, v. 7, p. 33–48, 1999.




DOI: https://doi.org/10.22456/2175-2745.85091

Copyright (c) 2019 Gabriella Lopes Andrade

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.