World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SOME GPU ALGORITHMS FOR GRAPH CONNECTED COMPONENTS AND SPANNING TREE

    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 Scholar
    • L. BACKSTROMet al., 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
    • D. A. BADER and G. CONG, Journal of Parallel and Distributed Computing 65(9), 994 (2005), DOI: 10.1016/j.jpdc.2005.03.011. Crossref, ISIGoogle Scholar
    • I.   BUCK , GPU Computing with NVIDIA CUDA , SIGGRAPH '07: ACM SIGGRAPH 2007 courses . Google Scholar
    • D. CHAKRABARTI, Y. ZHAN and C. FALOUTSOS, SIAM Data Mining 6, (2004). Google Scholar
    • CORMEN, T., LEISERSON, C., RIVEST, R., AND STEIN, C. Introduction to algorithms, 1990 . Google Scholar
    • Y. DOTSENKOet al., Fast scan algorithms on graphics processors, In Proceedings of ICS pp. 205–213. Google Scholar
    • D. 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 Scholar
    • J. 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
    • D. S. HIRSCHBERG, A. K. CHANDRA and D. V. SARWATE, Communications of the ACM 22(8), 461 (1979), DOI: 10.1145/359138.359141. Crossref, ISIGoogle 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 Scholar
    • M. MÉNDEZ-LOJOet al., 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
    • D. P. SCARPAZZA, O. VILLA and F. PETRINI, IEEE Transactions on Parallel and Distributed Systems 19(10), 1381 (2008), DOI: 10.1109/TPDS.2007.70811. Crossref, ISIGoogle Scholar
    • S. SENGUPTAet al., Scan primitives for gpu computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware pp. 97–106. Google Scholar
    • Y. SHILOACH and U. VISHKIN, Journal of Algorithms 3(1), 57 (1982), DOI: 10.1016/0196-6774(82)90008-6. Crossref, ISIGoogle Scholar
    • V.   VINEET et al. , 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. YOOet al., A scalable distributed parallel breadth-first search algorithm on BlueGene/L, Proceedings of ICS (IEEE Computer Society) p. 25. Google Scholar