Design and Implementation of GPU-Based Prim’s Algorithm

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 the authors obtain about 2 times speed-up on Nvidia GTX260 GPU over the CPU implementation and 3 times speed-up over non-primitives GPU implementation.

Resource Details

Provided by:
mecs-press
Topic:
Hardware
Format:
PDF