Scalable State Space Search on the GPU with Multi-Level Parallelism
Egor Shipovalov 1 and Valentin Pryanichnikov 2
1 Sensorika Intl. Laboratory, Moscow, Russia
kogdaugodno @ gmail com
2 Keldysh Institute of Applied Mathematics, Moscow, Russia
Abstract: Modern GPUs offer an accessible and scalable supercomputing platform. However, their use for state-space search has so far been auxiliary or in niche methods such as iterative deepening A* or random walks. We describe a scalable deterministic A* state space search implementation running entirely on the GPU. This is made possible by designing core algorithms for lock-step parallelism as well as using CUDA cooperative grids to implement hash-distributed A* load balancing scheme. Comparative benchmarking showed significant improvements in performance as well as resource efficiency.
Keywords: state space search, heuristic search, A*, automated planning, model checking, parallel computation, GPU, GPGPU, CUDA