Paper #14

Paper #14

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