International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 3, No. 4, 8 Aug. 2011
Cover page and Table of Contents: PDF (size: 396KB)
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
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.