Name
Abstract | ||
|---|---|---|
Computing a minimum spanning tree (MST) of a graph is a fundamental problem in Graph Theory and arises as a subproblem in many applications. In this paper, we propose a parallel MST algorithm and implement it on a GPU (Graphics Processing Unit). One of the steps of previous parallel MST algorithms is a heavy use of parallel list ranking. Besides the fact that list ranking is present in several parallel libraries, it is very time-consuming. Using a different graph decomposition, called strut, we devised a new parallel MST algorithm that does not make use of the list ranking procedure. Based on the BSP/CGM model we proved that our algorithm is correct and it finds the MST after O(log p) iterations (communication and computation rounds). To show that our algorithm has a good performance onreal parallel machines, we have implemented it on GPU. The way that we have designed the parallel algorithm allowed us to exploit the computing power of the GPU. The efficiency of the algorithm was confirmed by our experimental results. The tests performed show that, for randomly constructed graphs, with vertex numbers varying from 10,000 to 30,000 and density between 0.02 and 0.2, the algorithm constructs an MST in a maximum of six iterations. When the graph is not very sparse, our implementation achieved a speedup of more than 50, for some instances as high 296, over a minimum spanning tree sequential algorithm previously proposed in the literature. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/SBAC-PADW.2017.20 | 2017 International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW) |
Keywords | Field | DocType |
minimum spanning tree,parallel algorithm,GPU | List ranking,Distributed minimum spanning tree,Prim's algorithm,Computer science,Parallel algorithm,Parallel computing,Spanning tree,Sequential algorithm,Kruskal's algorithm,Minimum spanning tree | Conference |
ISBN | Citations | PageRank |
978-1-5386-4820-9 | 2 | 0.38 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jucele Franca de Alencar Vasconcellos | 1 | 2 | 0.38 |
| Edson Norberto Cáceres | 2 | 29 | 7.30 |
| Henrique Mongelli | 3 | 20 | 4.21 |
| S. W. Song | 4 | 129 | 29.78 |