Performance Improvement Analysis of A* Algorithm Using OpenMP

• Eduardo da Silva UTFPR
• Rogério Aparecido Gonçalves UTFPR
• João Fabrício Filho UTFPR

DOI: https://doi.org/10.5753/eradsp.2024.239868

Abstract

Applications can be improved by dividing the work so that multiple tasks are processed simultaneously. The goal of this work is to decrease the response time of the A* search algorithm through parallelization and achieve better performance compared to its serial version. To do this, this work implemented the search in parallel using OpenMP, dividing the search into four threads in the main loop of the algorithm. The result is a time gain from parallelism compared to serial between 8,49% and 9,32%, a percentage below what is expected when considering parallelized codes due to the way the algorithm works, using lists that cannot be updated simultaneously.

References

Chapman, B., Jost, G., and van der Pas, R. (2007). Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation). The MIT Press.

Kirk, D. B. and Wen-Mei, W. H. (2016). Programming massively parallel processors: a hands-on approach. Morgan kaufmann.

Patrick, L. (2005). A* Pathfinding para iniciantes. Traduzido por Reynaldo N. Gayoso, [e-mail] em 04 de Abril de 2005. Atualizado em 04 de junho de 2005.