Design and Implementation of GPU-Based Prim's Algorithm
Автор: Wei Wang, Yongzhong Huang, Shaozhong Guo
Журнал: International Journal of Modern Education and Computer Science (IJMECS) @ijmecs
Статья в выпуске: 4 vol.3, 2011 года.
Бесплатный доступ
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.
GPU, minimum spanning tree, Prim's algorithm, data parallel primitives, CUDA
Короткий адрес: https://sciup.org/15010249
IDR: 15010249
Список литературы Design and Implementation of GPU-Based Prim's Algorithm
- 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.
- E. Gonina and L. Kalé, "Parallel Prim’s algorithm on dense graphs with a novel extension," Tech. Rep., 2007.
- 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.
- 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.
- A. Munshi, "OpenCL: parallel computing on the GPU and CPU," http://s08.idav.ucdavis.edu/munshi-opencl.pdf, 2008.
- 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.
- J. Siek, L. Lee, and A. Lumsdaine, "The Boost graph library: user guide and reference manual," Addison-Wesley, 2002.
- M. Harris, "Optimizing parallel reduction in CUDA, " Nvidia, Tech. Rep., 2007.
- G. Karypis, A. Grama, A. Gupta and V. Kumar. Introduction to Parallel Computing. Addison Weslesy, second edition, 2003.
- G. E. Blelloch, "Scans as primitive parallel operations," IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989.
- 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.
- A. Buluc, "Linear algebraic primitives for parallel computing on large graphs," Ph.D. thesis, University of California, Santa Barbara, 2010.
- M. Harris, J. Owens, S. Sengupta, Y. Zhang and A. Davidson. CUDPP: CUDA Data Parallel Primitives Library. http://www.gpgpu.org/developer/cudpp/, 2011.
- Thrust. Thrust homepage. http://code.google.com/p/thrust/. 2011.
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT press, 2001.
- V. Vineet, P. Harish, and P. J. Narayanan, "Large graph algorithms for massively multithreaded architectures," Tech. Rep., 2009.
- 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.
- A. Leist, D. P. Playne and K. A. Hawick. "Exploiting graphical processing units for data-parallel scientific applications".Tech. Rep., December, 2009.
- D. Roger, U. Assarsson and N. Holzschuch. "Efficient stream reduction on the GPU". In Workshop on General Purpose Processing on Graphics Processing Units, 2007.
- D. A. Bader and K. Madduri, "GTgraph: a synthetic graph generator suite," Tech. Rep., 2006.
