AAAI Publications, Twentieth International Conference on Automated Planning and Scheduling

Font Size: 
Perfect Hashing for State Space Exploration on the GPU
Stefan Edelkamp, Damian Sulewski, Cengizhan Yücel

Last modified: 2010-04-20


This paper exploits parallel computing power of graphics cards to accelerate state space search. We illustrate that modern graphics processing units (GPUs) have the potential to speed up breadth-first search significantly. For a bitvector representation of the search frontier, GPU algorithms with one and two bits per state are presented. Efficient perfect hash functions and their inverse are explored in order to achieve enhanced compression. We report maximal speed-ups of up to a factor of 27 wrt. single core CPU computation.

Full Text: PDF