Multi-GPU sliding tile puzzle solving with GA*, Groute and Abstract Zobrist Hashing

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