RESEARCH AND DEVELOPMENT OF JOHNSON’S ALGORITHM
PARALLEL SCHEMES IN GPGPU TECHNOLOGYS.D.POGORILYY, M.S.SLYNKO, Y.I.RUSTAMOV
Abstract.The use of Johnson’s algorithm for finding the shortest path for all pairs of weighted
directed graph nodes is proposed. Its formalization in terms of Glushkov’s modified systems
of algorithmic algebras is realized. The expediency of GPGPU technology using to accelerate
the algorithm is proved. A number of schemas of parallel algorithm optimized for using in
GPGPU are obtained. Approach to the implementation of the schemes obtained with the use
of computing architecture NVIDIA CUDA is proposed. An experimental study of improved
performance by using GPU for computations is realized.
Keywords:NVIDIA CUDA, GPGPU, SSSP, APSP, Thrust, SAA Scheme, Johnson’s Algorithm.