Otimização de pathfinding em GPU

Nos últimos anos, as unidades de processamento gráfico (GPU) têm apresentado um avanço significativo dos recursos computacionais disponíveis para o uso de aplicações não-gráficas. A capacidade de resolução de problemas envolvendo computação paralela, onde o mesmo programa é executado em diversos elementos de dados diferentes ao mesmo tempo, bem como o desenvolvimento de novas arquiteturas que suportem esse novo paradigma, como CUDA (Computed Unified Device Architecture), tem servido de motivação para a utilização da GPU em aplicações de propósito geral, especialmente em jogos. Em contrapartida, a performance das CPUs, mesmo com a presença de múltiplos núcleos (multi-core), tem diminuído, limitando o avanço tecnológico de diversas técnicas desenvolvidas na área de jogos e favorecendo a transição e o desenvolvimento das mesmas para a GPU. Alguns algoritmos de Inteligência Artificial que podem ser decompostos e demonstram certo nível de paralelismo, como o pathfinding, utilizado na navegação de agentes durante o jogo, têm sido desenvolvidos em GPU e demonstrado um desempenho melhor quando comparado à CPU. De modo semelhante, este trabalho tem como proposta a investigação e o desenvolvimento de possíveis otimizações ao algoritmo de pathfinding em GPU, por meio de CUDA, com ênfase em sua utilização na área de jogos, escalando a quantidade de agentes e nós de um mapa, possibilitando um comparativo com seu desempenho apresentado na CPU.In recent years, graphics processing units (GPUs) have shown a significant advance of computational resources available for the use of non-graphical applications. The ability to solve problems involving parallel computing as well as the development of new architectures that supports this new paradigm, such as CUDA, has encouraged the use of GPU for general purpose applications, especially in games. Some parallel tasks which were CPU based are being ported over to the GPU due to their superior performance. One of these tasks is the pathfinding of an agent over a game map, which has already achieved a better performance on GPU, but is still limited. This work describes some optimizations to a GPU pathfinding implementation, addressing a larger work set (agents and nodes) with good performance compared to a CPU implementation