Contents V.8, N.1, 2017

  • RESEARCH AND DEVELOPMENT OF JOHNSON’S ALGORITHM PARALLEL SCHEMES IN GPGPU TECHNOLOGY
    S.D.POGORILYY, M.S.SLYNKO, Y.I.RUSTAMOV (pp. 12-21)
  • 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.

    Contact Details

    Telephone:
    Email: twms.aliev@gmail.com
    Website: www.twmsj.az

    Z.Khalilov str., 23, AZ 1148,
    Baku
    AZERBAIJAN