3379

GPU-Based Fast Minimum Spanning Tree Using Data Parallel Primitives

Wei Wang, Shaozhong Guo, Fan Yang, Jianxun Chen
Zhengzhou Inf. Sci. & Technol. Inst., Zhengzhou, China
2nd International Conference on Information Engineering and Computer Science (ICIECS), 2010

@conference{wang2010gpu,

   title={GPU-Based Fast Minimum Spanning Tree Using Data Parallel Primitives},

   author={Wang, W. and Guo, S. and Yang, F. and Chen, J.},

   booktitle={Information Engineering and Computer Science (ICIECS), 2010 2nd International Conference on},

   pages={1–4},

   issn={2156-7379},

   organization={IEEE}

}

Source Source   

659

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: