Parallel implementation of the search algorithm for minimum spanning trees using central and graphic processors

Author

A.S. Kolganov

Annotation

The solution of the problem to search a minimum spanning trees is widespread in various fields of researches: recognition of different objects, computer vision,  analysis and creation of networks (for example, telephone, electrical, computer, road, etc.), chemistry and biology and many others. There are at least three well-known algorithms that solve this problem: Boruvka's, Kruskal's and Prim's.  Large graph processing is a time-consuming task for Central processor unit (CPU) and is popular at present. The graphic accelerators (GPU) having greater computational power, than CPU, become more and more widespread for solution of  general purpose tasks.  But this problem, as well as many graph processing tasks, badly lays down on GPU architecture. In this article hybrid implementation of the algorithm will be considered.  

Key words

MST, CUDA, NVidia, Graphs, Boruvka.

Language

Russian

Reference

A.S. Kolganov. Parallel implementation of the search algorithm for minimum spanning trees using central and graphic processors // Proceedings of the international scientific conference "Parallel Computational Technologies (PCT'2016)", Chelyabinsk: Publishing center SUSU, 2016, P. 530-543