Perfect Hashing for State Space Exploration on the GPU

Authors

  • Stefan Edelkamp TZI, Universität Bremen
  • Damian Sulewski TZI, Universität Bremen
  • Cengizhan Yücel Technische Universität Dortmund

DOI:

https://doi.org/10.1609/icaps.v20i1.13414

Keywords:

search, hashing, GPU

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.

Downloads

Published

2010-05-05

How to Cite

Edelkamp, S., Sulewski, D., & Yücel, C. (2010). Perfect Hashing for State Space Exploration on the GPU. Proceedings of the International Conference on Automated Planning and Scheduling, 20(1), 57-64. https://doi.org/10.1609/icaps.v20i1.13414

Issue

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

Section

Full Technical Papers