| dc.description.abstract | The A* algorithm has been a key search algorithm and part of AI literature
for a long time. It has applications in computational biology, natural lan-
guage processing, pathfinding, puzzle solving, and more. The complexity of
some of these applications has brought about many improvements and vari-
ations of the original algorithm, and recent research has shown that using
GPUs to accelerate A* search can achieve substantial speed-ups over con-
ventional CPU-based implementations.
Compute nodes with multiple GPUs have become commonplace, and
techniques and methods for programming such systems is a popular area
of research. We bring to life the first implementation of the A* search al-
gorithm that distributes the search space across multiple GPU devices, and
identify challenges that must be addressed in order to achieve appreciable
performance.
Our implementation is based on the GA* algorithm of Zhou and Zeng,
and builds on the asynchronous multi-GPU programming framework Groute
by Ben-Nun, Sutton, Pai, and Pingali. We use Abstract Zobrist Hashing for
distributing the search space across GPUs. The implementation is bench-
marked by solving sliding tile puzzles, a commonly used benchmark for search
algorithms.
Our multi-GPU version of A* allows for solving more difficult search
problems than a single GPU can handle by utilizing the increased memory
capacity of multiple GPUs. However, it does not in general yield improved
performance in terms of wall-clock runtime when increasing the number of
GPUs used. We propose how to eliminate much of the overhead introduced
when scaling horizontally, and show that if this is done successfully, each
additional GPU added may yield a search rate increase of at least 50% of the
performance of a lone GPU. | en |
