Geodesic
Parallel implementation of minimum spanning tree algorithm on CPU and GPU
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 3, pp. 5-19 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Solution of the finding a minimum spanning tree problem is common in various areas of research: recognition of different objects, computer vision, analysis and construction of networks (eg, telephone, electrical, computer, travel, etc.), chemistry and biology, and many others. Processing large graphs is a quite time-consuming task for the central processor (CPU), and in high demand at the present moment. The usage of Graphics processing units (GPUs) as a mean to solve general-purpose problems grows every day, because GPUs have more computing power than CPUs. This article describes the methods of compression and conversion of graphs in standard formats to increase the efficiency of their processing. The search algorithm of minimum spanning trees has been used for researching the proposed approaches. The possibility of a hybrid implementation of this algorithm has been investigated. The highest results were obtained on the large R-MAT and SSCA2 graphs.
Keywords: MST, parallel graph processing, CUDA, large graphs.
Mots-clés : Boruvka algorithm 
@article{VYURV_2016_5_3_a0,
     author = {A. S. Kolganov},
     title = {Parallel implementation of minimum spanning tree algorithm on {CPU} and {GPU}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {5--19},
     year = {2016},
     volume = {5},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a0/}
}
TY  - JOUR
AU  - A. S. Kolganov
TI  - Parallel implementation of minimum spanning tree algorithm on CPU and GPU
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2016
SP  - 5
EP  - 19
VL  - 5
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a0/
LA  - ru
ID  - VYURV_2016_5_3_a0
ER  - 
%0 Journal Article
%A A. S. Kolganov
%T Parallel implementation of minimum spanning tree algorithm on CPU and GPU
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2016
%P 5-19
%V 5
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a0/
%G ru
%F VYURV_2016_5_3_a0
A. S. Kolganov. Parallel implementation of minimum spanning tree algorithm on CPU and GPU. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 3, pp. 5-19. http://geodesic.mathdoc.fr/item/VYURV_2016_5_3_a0/

[1] Chazelle B.A., “Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity”, Journal of the ACM, 47:6 (2000), 1028–1047 | DOI

[2] S. Pettie, “An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem”, Foundations of Computer Science, 2002, 155–163 | DOI

[3] W. Wei, G. Shaozhong, Y. Fan, C. Jianxun, “Minimum Spanning Tree Using Data Parallel Primitives”, Information Engineering and Computer Science (ICIECS), 2nd International Conference (TBD Wuhan, China), 2010, 1–4 | DOI

[4] A.S. Arefin, C. Riveros, R. Berretta, P. Moscato, “kNN-MST-Agglomerative: A Fast and Scalable Graph-Based Data Clustering Approach on GPU”, Computer Science Education (ICCSE), 7th International Conference (The University of Melbourne, Australia), 2012, 585–590 | DOI

[5] V. Vineet, P. Harish, S. Patidar, P.J. Narayanan, “Fast Minimum Spanning Tree for Large Graphs on the GPU”, HPG ’09 Proceedings of the Conference on High Performance Graphics (New Orleans, LA, USA), 2009, 167–171 | DOI

[6] N.E. Gibbs, W.G. Poole, P.K. Stockmeyer, “A Comparison of Several Bandwidth and Profile Reduction Algorithms”, ACM Transactions on Mathematical Software, 2:4 (1976), 322–330 | DOI

[7] J.R. Gilbert, C. Moler, R. Schreiber, “Sparse Matrices in MATLAB: Design and Implementation”, SIAM Journal on Matrix Analysis and Applications, 13:1 (1992), 333–356 | DOI

[8] D. Chakrabarti, Y. Zhan, C. Faloutsos, “R-MAT: A Recursive Model for Graph Mining”, In Proceedings of 4th International Conference on Data Mining (Brighton, UK), 2004, 442–446 | DOI

[9] D.A. Bader, K. Madduri, “Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors”, Technical Report, 2005

[10] O. Borůvka, “O Jistém Problému Minimálním”, Práce Moravské Přírodovědecké Společnosti III, 1926, no. 3, 37–58

[11] Opisanie algoritmov dlya struktury Union-Find, (data obrascheniya: 30.11.2015) https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

[12] Opisanie standarta OpenMP, (data obrascheniya: 30.11.2015) http://www.openmp.org/mp-documents/openmp-4.5.pdf

[13] Compute Unified Device Architecture, (data obrascheniya: 30.11.2015) http://www.nvidia.ru/object/cuda-parallel-computing-ru.html

[14] Unified Memory in CUDA 6, (data obrascheniya: 30.11.2015) http://devblogs.nvidia.com/parallelforall/unified-memory-in-cuda-6/

[15] S. Nobari, T. Cao, P. Karras, S. Bressan, “Scalable Parallel Minimum Spanning Forest Computation”, PPoPP’12 Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (New York, NY, USA), 2012, 205–214 | DOI

[16] W. Wei, G. Shaozhong, Y. Fan, C. Jianxun, “Design and Implementation of GPU-Based Prim’s Algorithm”, Information Engineering and Computer Science (ICIECS), 2010 2nd International Conference (TBD Wuhan, China), 2010, 1–4