Open AccessResearch and development of Johnson's algorithm parallel schemes in GPGPU technology
Author(s) -
Sergiy Pogorilyy,
M.S. Slynko
Publication year - 2016
Publication title -
problemy programmirovaniâ
Language(s) - English
Resource type - Journals
ISSN - 1727-4907
DOI - 10.15407/pp2016.02-03.105
Subject(s) - cuda , general purpose computing on graphics processing units , computer science , parallel computing , shortest path problem , computation , algorithm , graph , theoretical computer science , graphics , computer graphics (images)
Johnson’s all pairs shortest path algorithm application in an edge weighted, directed graph is considered. Its formalization in terms of Glushkov’s modified systems of algorithmic algebras was made. The expediency of using GPGPU technology to accelerate the algorithm is proved. A number of schemas of parallel algorithm optimized for using in GPGPU were obtained. Suggested approach to the implementation of the schemes obtained using computing architecture NVIDIA CUDA. An experimental study of improved performance by using GPU for computations was made.