SOME GPU ALGORITHMS FOR GRAPH CONNECTED COMPONENTS AND SPANNING TREE
Abstract
Graphics Processing Units (GPU) are application specific accelerators which provide high performance to cost ratio and are widely available and used, hence places them as a ubiquitous accelerator. A computing paradigm based on the same is the general purpose computing on the GPU (GPGPU) model. The GPU due to its graphics lineage is better suited for the data-parallel, data-regular algorithms. The hardware architecture of the GPU is not suitable for the data parallel but data irregular algorithms such as graph connected components and list ranking.
In this paper, we present results that show how to use GPUs efficiently for graph algorithms which are known to have irregular data access patterns. We consider two fundamental graph problems: finding the connected components and finding a spanning tree. These two problems find applications in several graph theoretical problems. In this paper we arrive at efficient GPU implementations for the above two problems. The algorithms focus on minimising irregularity at both algorithmic and implementation level. Our implementation achieves a speedup of 11-16 times over a corresponding best sequential implementation.
References
B. AWERBUCH and Y. SHILOACH , New connectivity and msf algorithms for ultracomputer and pram, ICPP pp. 175–179. Google ScholarL. BACKSTROM , Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (ACM) p. 54. Google Scholar- BADER, D., AND MADDURI, K. GTgraph: A suite of synthetic graph generators. url: , http://wwwstatic.cc.gatech.edu/kamesh . Google Scholar
- Journal of Parallel and Distributed Computing 65(9), 994 (2005), DOI: 10.1016/j.jpdc.2005.03.011. Crossref, ISI, Google Scholar
-
I. BUCK , GPU Computing with NVIDIA CUDA , SIGGRAPH '07: ACM SIGGRAPH 2007 courses . Google Scholar - SIAM Data Mining 6, (2004). Google Scholar
- CORMEN, T., LEISERSON, C., RIVEST, R., AND STEIN, C. Introduction to algorithms, 1990 . Google Scholar
Y. DOTSENKO , Fast scan algorithms on graphics processors, In Proceedings of ICS pp. 205–213. Google ScholarD. GREGOR and A. LUMSDAINE , Lifting sequential graph algorithms for distributed-memory parallel computation, Proceedings of the OOPSLA40 (ACM, New York, NY, USA) pp. 423–437. Google ScholarJ. GREINER , A comparison of parallel algorithms for connected components, Symposium on Parallel Algorithms and Architectures pp. 16–25. Google Scholar-
P. HARISH and P. J. NARAYANAN , Accelerating Large Graph Algorithms on the GPU using CUDA , Proc. of HiPC . Google Scholar - HARRIS, M., OWENS, J., SENGUPTA, S., ZHANG, Y., AND DAVIDSON, A. Cudpp: Cuda data parallel primitives library. 2008 , http://gpgpu.org/developer/cudpp . Google Scholar
D. S. HIRSCHBERG , Parallel algorithms for the transitive closure and the connected components problem, Proc. of the ACM STOC pp. 55–57. Google Scholar- Communications of the ACM 22(8), 461 (1979), DOI: 10.1145/359138.359141. Crossref, ISI, Google Scholar
T. HSU , V. RAMACHANDRAN and N. DEAN , Parallel implementation of algorithms for finding connected components in graphs, Parallel algorithms: third DIMACS implementation challenge p. 20. Google Scholar-
J. JAJA , An Introduction to Parallel Algorithms ( Addison Wesley , 1992 ) . Google Scholar J. LESKOVEC , J. KLEINBERG and C. FALOUTSOS , Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of ACM SIGKDD (ACM) pp. 177–187. Google ScholarM. MÉNDEZ-LOJO , Structure-driven optimizations for amorphous data-parallel programs, PPoPP '10: Proceedings of the 15th ACM SIGPLAN symposium on Principles and practice of parallel computing (ACM) pp. 3–14. Google Scholar-
D. MOUNT and S. ARYA , ANN: A library for approximate nearest neighbor searching , CGC 2nd Annual Fall Workshop on Computational Geometry . Google Scholar - NVIDIA, C. Cuda: Compute unified device architecture programming guide. Technical report, NVIDIA, 2007 . Google Scholar
M. S. REHMAN , K. KOTHAPALLI and P. J. NARAYANAN , Fast and Scalable List Ranking on the GPU, In Proceedings of ICS pp. 152–160. Google Scholar- IEEE Transactions on Parallel and Distributed Systems 19(10), 1381 (2008), DOI: 10.1109/TPDS.2007.70811. Crossref, ISI, Google Scholar
S. SENGUPTA , Scan primitives for gpu computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware pp. 97–106. Google Scholar- Journal of Algorithms 3(1), 57 (1982), DOI: 10.1016/0196-6774(82)90008-6. Crossref, ISI, Google Scholar
-
V. VINEET , Fast minimum spanning tree for large graphs on the gpu , In Proc. of High Performance Graphics . Google Scholar -
V. VINEET and P. J. NARAYANAN , Proceedings of the CVPR Workshop on Visual Computer Vision on GPUs ,CUDA Cuts: Fast Graph Cuts on the GPU . Google Scholar A. YOO , A scalable distributed parallel breadth-first search algorithm on BlueGene/L, Proceedings of ICS (IEEE Computer Society) p. 25. Google Scholar


