A fast GPU algorithm for graph connectivity

Jyothish Soman, Kothapalli Kishore, P. J. Narayanan
IIIT-Hyderabad, Gachibowli, Hyderabad, Andhra Pradesh, India-500032
2010 IEEE International Symposium on Parallel Distributed Processing Workshops and Phd Forum IPDPSW (2010) Publisher: Ieee, Pages: 1-8


   title={A fast GPU algorithm for graph connectivity},

   author={Soman, J. and Kishore, K. and Narayanan, PJ},

   booktitle={Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on},




Download Download (PDF)   View View   Source Source   



Graphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: