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

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {5},
     number = {3},
     year = {2016},
     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
PB  - mathdoc
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
%I mathdoc
%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/