Loading...
Publication
Uma proposta de uma variante otimizada do algoritmo A* para sistemas multi-nĂșcleo
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 2.4 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
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.
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.
Description
Keywords
Algoritmo A* Otimização Sistemas multi-nĂșcleo Paralelismo Filas prioritĂĄrias Comunicação entre tarefas A* algorithm Optimization Multi-core systems Parallel processing Priority queues Inter-task communication
Citation
Pires, 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-88
Publisher
Universidade Aberta