AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 20

Perfect Hashing for State Space Exploration on the GPU

Authors

Stefan Edelkamp,Damian Sulewski,Cengizhan Yücel

TZI, Universität Bremen,TZI, Universität Bremen,Technische Universität Dortmund


Proceedings:

Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling

Volume

Issue:

Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling

Track:

Full Technical Papers

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/icaps.v20i1.13414


ICAPS

Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling