Research and development of Johnson's algorithm parallel schemes in GPGPU technology

S.D. Pogorilyy, M.S. Slynko

Abstract


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.

Problems in programming 2016; 2-3: 105-112


Keywords


NVidia CUDA; GPGPU; SSSP; APSP; Thrust; SAA scheme; Johnson’s algorithm

References


Pogorilyy S.D. & Bilous R.V. (2010) Genetic algorithm for solving routing problem in networks. In 7-th international scientific programming conference UKRPROG'2010. Kyiv. p.p. 171-177.

Cormen T. H. et al. (2013) Introduction to algorithms, 3rd Ed. Cambridge: MIT Press.

NVidia (2015). CUDA C Programming Guide [Online] September 2015. Available from: http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf [Accessed: 22-nd Dec 2015].

Boreskov A.V. & Kharlamov A.A (2010) CUDA technology fundamentals. Moscow: DMC Press.

Pogorilyy S.D., Vitel D. Yu. & Vereschinsky O.A. (2012) Modern video adapter architectures. GPGPU technology. Part 1. Data registration, storage and processing. 14 (4).

Anisimov A.V., Pogorilyy S.D. & Vitel D.Yu. (2013) About the Issue of Algorithms formalized Design for Parallel Computer Architectures. Applied and Computational Mathematics. 12 (2). p.p. 140-151 .

Tianyi, D. H. & Abdelrahman, T. S. (2011). Reducing Branch Divergence in GPU Programs. Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units. New York, NY, USA.

Crauser, A. et al (1998). A parallelization of Dijkstra’s shortest path algorithm. Mathematical Foundations of Computer Science, P. 722–731.

Pogorilyy S.D., Maryanovsky V.A., Boyko Yu.V. & Vereshinsky O.A. (2009) Research of Danzig algorithm parallel schemes for computing systems with shared memory. Mathematical Machines and Systems. 4.

Bell, N. & Hoberock, J. (2011). Thrust: A Productivity-Oriented Library for CUDA [Online] 2011. Available from: https://thrust.googlecode.com/files/Thrust%20-%20A%20Productivity-Oriented%20Library%20for%20CUDA.pdf [Accessed: 22-nd Dec 2015].




DOI: https://doi.org/10.15407/pp2016.02-03.105

Refbacks

  • There are currently no refbacks.