Pires, CarlosShirley, Paulo2023-12-202023-12-202023-12Pires, Carlos; Shirley, Paulo - Uma proposta de uma variante otimizada do algoritmo A* para sistemas multi-núcleo. "Revista de Ciências da Computação" [Em linha]. ISSN 1646-6330 (Print) 2182-1801 (Online). Vol. 18 (2023), p. 67-881646-6330http://hdl.handle.net/10400.2/15284Este 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.porAlgoritmo A*OtimizaçãoSistemas multi-núcleoParalelismoFilas prioritáriasComunicação entre tarefasA* algorithmOptimizationMulti-core systemsParallel processingPriority queuesInter-task communicationjournal articlehttps://doi.org/10.34627/rcc.v18i0.2972182-1801