masterThesis
Otimização de pathfinding em GPU
Registro en:
Autor
SILVA
Institución
Resumen
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.