Multi-GPU sliding tile puzzle solving with GA*, Groute and Abstract Zobrist Hashing
Master thesis
Permanent lenke
http://hdl.handle.net/11250/2615873Utgivelsesdato
2018Metadata
Vis full innførselSamlinger
Sammendrag
The A* algorithm has been a key search algorithm and part of AI literaturefor a long time. It has applications in computational biology, natural lan-guage processing, pathfinding, puzzle solving, and more. The complexity ofsome of these applications has brought about many improvements and vari-ations of the original algorithm, and recent research has shown that usingGPUs to accelerate A* search can achieve substantial speed-ups over con-ventional CPU-based implementations.
Compute nodes with multiple GPUs have become commonplace, andtechniques and methods for programming such systems is a popular areaof research. We bring to life the first implementation of the A* search al-gorithm that distributes the search space across multiple GPU devices, andidentify challenges that must be addressed in order to achieve appreciableperformance.
Our implementation is based on the GA* algorithm of Zhou and Zeng,and builds on the asynchronous multi-GPU programming framework Grouteby Ben-Nun, Sutton, Pai, and Pingali. We use Abstract Zobrist Hashing fordistributing the search space across GPUs. The implementation is bench-marked by solving sliding tile puzzles, a commonly used benchmark for searchalgorithms.
Our multi-GPU version of A* allows for solving more difficult searchproblems than a single GPU can handle by utilizing the increased memorycapacity of multiple GPUs. However, it does not in general yield improvedperformance in terms of wall-clock runtime when increasing the number ofGPUs used. We propose how to eliminate much of the overhead introducedwhen scaling horizontally, and show that if this is done successfully, eachadditional GPU added may yield a search rate increase of at least 50% of theperformance of a lone GPU.