6065

Design and Implementation of GPU-Based Prim’s Algorithm

Wei Wang, Yongzhong Huang, Shaozhong Guo
Zhengzhou Information Science and Technology Institute, Zhengzhou, China
International Journal of Modern Education and Computer Science (IJMECS), Vol.3, No.4, 2011

@article{wang2011design,

   title={Design and Implementation of GPU-Based Prim’s Algorithm},

   author={Wang, W. and Huang, Y. and Guo, S.},

   journal={International Journal of Modern Education and Computer Science (IJMECS)},

   volume={3},

   number={4},

   pages={55},

   year={2011}

}

Download Download (PDF)   View View   Source Source   

1106

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: