17229

Block-Parallel IDA* for GPUs

Satoru Horie, Alex Fukunaga
Graduate School of Arts and Sciences, The University of Tokyo
arXiv:1705.02843 [cs.AI], (8 May 2017)

@article{horie2017blockparallel,

   title={Block-Parallel IDA* for GPUs (Extended Manuscript)},

   author={Horie, Satoru and Fukunaga, Alex},

   year={2017},

   month={may},

   archivePrefix={"arXiv"},

   primaryClass={cs.AI}

}

Download Download (PDF)   View View   Source Source   Source codes Source codes

Package:

538

views

We investigate GPU-based parallelization of Iterative-Deepening A* (IDA*). We show that straightforward thread-based parallelization techniques which were previously proposed for massively parallel SIMD processors perform poorly due to warp divergence and load imbalance. We propose Block-Parallel IDA* (BPIDA*), which assigns the search of a subtree to a block (a group of threads with access to fast shared memory) rather than a thread. On the 15-puzzle, BPIDA* on a NVIDIA GRID K520 with 1536 CUDA cores achieves a speedup of 4.98 compared to a highly optimized sequential IDA* implementation on a Xeon E5-2670 core.
Rating: 1.5. From 2 votes.
Please wait...

Recent source codes

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: