Proposal for an optimized variant of A* Algorithm for multi-core systems

Este artigo propõe uma variante otimizada do algoritmo A* para melhorar o desempenho em sistemas multi-núcleo. A abordagem proposta envolve a utilização de filas prioritárias locais (min-heaps) em cada tarefa ou núcleo, permitindo o processamento em paralelo. A comunicação entre as tarefas é realizada por meio de um buffer compartilhado do tipo produtor/consumidor, permitindo a troca de informações sobre os nós sucessores. Um protótipo é descrito, envolvendo a implementação das estruturas de dados, a lógica das tarefas, a comunicação entre as tarefas e a avaliação do desempenho em sistemas multi-núcleo. Os resultados preliminares mostram um ganho de desempenho em comparação com a versão sequencial do algoritmo A*.This paper proposes an optimized variant of the A* algorithm to improve performance in multi-core systems. The proposed approach involves the use of local priority queues (min-heaps) in each task or core, enabling parallel processing. Communication between tasks is facilitated through a producer/consumer buffer, allowing for the exchange of information regarding successor nodes. A prototype is described, covering the implementation of data structures, task logic, inter-task communication, and performance evaluation in multi-core systems. Preliminary results demonstrate a performance gain compared to the sequential version of the A* algorithm.