Análise da Melhoria de Desempenho do Algoritmo A* Utilizando 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

Resumo

Aplicações podem ser melhoradas quando se divide o trabalho a ser feito de forma com que com que múltiplas tarefas sejam processadas simultaneamente. O objetivo deste trabalho é diminuir o tempo de resposta do algoritmo de busca A* por meio da paralelização e alcançar um melhor desempenho em relação à sua versão serial. Para tanto, este trabalho implementou a busca de forma paralela utilizando OpenMP, dividindo a busca em quatro threads no principal laço do algoritmo. O resultado é um ganho de tempo do paralelo em relação ao serial entre 8,49% e 9,32%, uma porcentagem abaixo do esperado quando se considera códigos paralelizados por conta do modo que o algoritmo trabalha, utilizando de listas que não podem ser atualizadas simultaneamente.

Referências

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.