Exploring the Limits of GPUs With Parallel Graph Algorithms

Frank Dehne, Kumanan Yogaratnam
School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6
arXiv:1002.4482 [cs.DC] (24 Feb 2010)


   title={Exploring the Limits of GPUs With Parallel Graph Algorithms},

   author={Dehne, F. and Yogaratnam, K.},

   journal={Arxiv preprint arXiv:1002.4482},



Download Download (PDF)   View View   Source Source   



In this paper, we explore the limits of graphics processors (GPUs) for general purpose parallel computing by studying problems that require highly irregular data access patterns: parallel graph algorithms for list ranking and connected components. Such graph problems represent a worst case scenario for coalescing parallel memory accesses on GPUs which is critical for good GPU performance. Our experimental study indicates that PRAM algorithms are a good starting point for developing efficient parallel GPU methods but require non-trivial modifications to ensure good GPU performance. We present a set of guidelines that help algorithm designers adapt PRAM graph algorithms for parallel GPU computation. We point out that the study of parallel graph algorithms for GPUs is of wider interest for discrete and combinatorial problems in general because many of these problems require similar irregular data access patterns.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: