Design and Implementation of GPU-Based Prim's Algorithm

Full Text (PDF, 396KB), PP.55-62

Views: 0 Downloads: 0

Author(s)

Wei Wang 1,* Yongzhong Huang 1 Shaozhong Guo 1

1. Zhengzhou Information Science and Technology Institute, Zhengzhou, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2011.04.08

Received: 7 May 2011 / Revised: 12 Jun. 2011 / Accepted: 1 Jul. 2011 / Published: 8 Aug. 2011

Index Terms

GPU, minimum spanning tree, Prim's algorithm, data parallel primitives, CUDA

Abstract

Minimum spanning tree is a classical problem in graph theory that plays a key role in a broad domain of applications. This paper proposes a minimum spanning tree algorithm using Prim's approach on Nvidia GPU under CUDA architecture. By using new developed GPU-based Min-Reduction data parallel primitive in the key step of the algorithm, higher efficiency is achieved. Experimental results show that we obtain about 2 times speedup on Nvidia GTX260 GPU over the CPU implementation and 3 times speedup over non-primitives GPU implementation.

Cite This Paper

Wei Wang, Yongzhong Huang, Shaozhong Guo, "Design and Implementation of GPU-Based Prim's Algorithm", International Journal of Modern Education and Computer Science(IJMECS), vol.3, no.4, pp.55-62, 2011. DOI:10.5815/ijmecs.2011.04.08

Reference

[1]R. Setia, A. Nedunchezhian, and S. Balachandran, "A new parallel algorithm for minimum spanning tree problem," Proc.International Conference on High Performance Computing (HiPC), pp. 1-5, 2009.
[2]E. Gonina and L. Kalé, "Parallel Prim’s algorithm on dense graphs with a novel extension," Tech. Rep., 2007.
[3]D. A. Bader and G. Cong, "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs," Journal of Parallel and Distributed Computing, v.66 n.11, p.1366-1378, November 2006.
[4]NVIDIA Corporation. CUDA Programming Guide 2.3, http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming _Guide_2.3.pdf, 2009.
[5]A. Munshi, "OpenCL: parallel computing on the GPU and CPU," http://s08.idav.ucdavis.edu/munshi-opencl.pdf, 2008.
[6]R. Vuducy, A.Chandramowlishwarany, J. Choi, M. Guney, and A. Shringarpurez, "On the limits of GPU acceleration," http://www.usenix.org/event/hotpar10/tech/full_papers/Vuduc.pdf, 2010.
[7]J. Siek, L. Lee, and A. Lumsdaine, "The Boost graph library: user guide and reference manual," Addison-Wesley, 2002.
[8]M. Harris, "Optimizing parallel reduction in CUDA, " Nvidia, Tech. Rep., 2007.
[9]G. Karypis, A. Grama, A. Gupta and V. Kumar. Introduction to Parallel Computing. Addison Weslesy, second edition, 2003.
[10]G. E. Blelloch, "Scans as primitive parallel operations," IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989.
[11]V. Vineet, P. Harish, S. Patidar, and P. J. Narayanan, "Fast minimum spanning tree for large graphs on the GPU, " in HPG ’09: Proceedings of the Conference on High Performance Graphics 2009, 2009, pp. 167– 171.
[12]A. Buluc, "Linear algebraic primitives for parallel computing on large graphs," Ph.D. thesis, University of California, Santa Barbara, 2010.
[13]M. Harris, J. Owens, S. Sengupta, Y. Zhang and A. Davidson. CUDPP: CUDA Data Parallel Primitives Library. http://www.gpgpu.org/developer/cudpp/, 2011.
[14]Thrust. Thrust homepage. http://code.google.com/p/thrust/. 2011.
[15]T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT press, 2001.
[16]V. Vineet, P. Harish, and P. J. Narayanan, "Large graph algorithms for massively multithreaded architectures," Tech. Rep., 2009.
[17]J. M. Pedro, T. Robert and G. Antonio. "CUDA solutions for the SSSP problem," Proc of the 9th international conference on computational science, 2009, pp. 904–913.
[18]A. Leist, D. P. Playne and K. A. Hawick. "Exploiting graphical processing units for data-parallel scientific applications".Tech. Rep., December, 2009.
[19]D. Roger, U. Assarsson and N. Holzschuch. "Efficient stream reduction on the GPU". In Workshop on General Purpose Processing on Graphics Processing Units, 2007.
[20]D. A. Bader and K. Madduri, "GTgraph: a synthetic graph generator suite," Tech. Rep., 2006.