DOI: 10.5176/978-981-08-7656-2 A-29
Authors: Sadegh H. Nobari Stéphane Bressan, Chedy Raïssi
Abstract: We propose a fast data parallel minimum spanning tree algorithm designed for general purpose computation graphical processing units (GPU). Our algorithm is a data parallel version of Boru˙ vka’s minimum spanning tree algorithm. Its gist is a synchronization on the central processing unit after each of the parallel iterations computing the components and their outgoing edge minimum weight. Our implementation uses both BrookGPU and CUDA from NVIDIA as programming environments and the performance of our algorithm was evaluated in comparison with the state-of-theart algorithms on different types of datasets. The experimental results show that our algorithm outperforms other
algorithms substantially in terms of execution time with up to tenfold speedup.
Updating...