Fast and scalable list ranking on the GPU

M. Suhail Rehman, Kishore Kothapalli, P. J. Narayanan
International Institute of Information Technology, Hyderabad, India
In ICS ’09: Proceedings of the 23rd international conference on Supercomputing (2009), pp. 235-243.


   title={Fast and scalable list ranking on the GPU},

   author={Rehman, M.S. and Kothapalli, K. and Narayanan, PJ},

   booktitle={Proceedings of the 23rd international conference on Supercomputing},





Download Download (PDF)   View View   Source Source   



General purpose programming on the graphics processing units (GPGPU) has received a lot of attention in the parallel computing community as it promises to offer the highest performance per dollar. The GPUs have been used extensively on regular problems that can be easily parallelized. In this paper, we describe two implementations of List Ranking, a traditional irregular algorithm that is difficult to parallelize on such massively multi-threaded hardware. We first present an implementation of Wyllie’s algorithm based on pointer jumping. This technique does not scale well to large lists due to the suboptimal work done. We then present a GPU-optimized, Recursive Helman-JaJa (RHJ) algorithm. Our RHJ implementation can rank a random list of 32 million elements in about a second and achieves a speedup of about 8-9 over a CPU implementation as well as a speedup of 3-4 over the best reported implementation on the Cell Broadband engine. We also discuss the practical issues relating to the implementation of irregular algorithms on massively multi-threaded architectures like that of the GPU. Regular or coalesced memory accesses pattern and balanced load are critical to achieve good performance on the GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: