Total views : 697

Modified Dijkstra’s Algorithm for Dense Graphs on GPU using CUDA

Affiliations

  • Department of Computer Science and Engineering, Maulana Ajad National Institute of Technology, Bhopal - 462003, Madhya Pradesh, India

Abstract


The objective of this research is to propose and implement a fast parallel Single source shortest path (SSSP) algorithm on Graphics Processing Unit (GPU) based highly parallel and cost effective platform for dense and complete graphs. The proposed algorithm is a variant of Dijkstra’s algorithm for SSSP calculation for complete and dense graphs. In place of relaxing all the edges of a selected node as in Dijkstra’s algorithm, it relaxes one-one selected edge of different nodes of the graph simultaneously at any iteration. This paper shows parallel implementation of both Dijkstra’s algorithm and our modified Dijkstra’s algorithm on a GPU-based machine. We evaluate these implementations on NVIDIA Tesla C2075 GPU- based machines. Parallel implementation of proposed modified Dijkstra’s algorithm gives a two to three times speed increase over a parallel Dijkstra’s algorithm on a GPU-based machine for complete and dense graphs. The proposed algorithm has minimized the number of edges relaxed by one parallel thread at any iteration of parallel Dijkstra’s algorithm.

Keywords

CUDA, Graph Algorithm, GPU Computing, Parallel Dijkstra’s Algorithm, Parallel Single Source Shortest Path Algorithm.

Full Text:

 |  (PDF views: 613)

References


  • Zhang D, Rubinstein BIP, Gemmell J. Principled Graph Matching Algorithms for Integrating Multiple Data Sources. IEEE Transactions on Knowledge and Data Engineering. 2015; 27(100):2784–96.
  • Dadaneh BZ, Markid HY, Zakerolhosseini A. Graph coloring using Intelligent Water Drops algorithm. Proceeding of 23rd Iranian Conference on Electrical Engineering. 2015.
  • Cheraghi A. Searching for an Unknown Edge in the Graph and its Tight Complexity Bounds. Indian Journal of Science and Technology. 2016; 9(13). Doi:10.17485/ijst/2016/v9i13/71360.
  • Albert S, Raj A, Victor SP. Algorithms to Find Geodetic Numbers and Edge Geodetic Numbers in Graphs. Indian Journal of Science and Technology. 2015; 8(13). Doi: 10.17485/ijst/2015/v8i13/53160.
  • Leung AKH, Kwok YK. An Efficient and Practical Greedy Algorithm for Server-Peer Selection in Wireless Peer-to-Peer File Sharing Networks. LNCS Springer-Verlag Berlin Heidelberg. 2005; 3794:1016–25.
  • Davoust A, Esfandiari B. Collaborative Building, Sharing and Handling of Graphs of Documents Using P2P File-Sharing. LNCS Springer-Verlag Berlin Heidelberg. 2009; 5872:888–97.
  • Papagelis M. Sampling Online Social Networks. IEEE Transaction on Knowledge and Data Engineering. 2013; 25(3):662–76.
  • Das S. Anonimos: An LP-Based Approach for Anonymizing Weighted Social Network Graphs. IEEE Transaction on Knowledge and Data Engineering. 2012; 24(4):590–604.
  • Takigawa I, Mamitsuka H. Probabilistic path ranking based on adjacent pair wise coexpression for metabolic transcripts analysis. Bioinformatics. 2008; 24(2):250–7.
  • Brown JA. Examination of Graphs in Multiple Agent Genetic Networks for Iterated Prisoner’s Dilemma. Proceedings of the Conference on Computational Intelligence in Games. 2013.
  • Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik. 1959; 1(1):269–71.
  • Bellman RE. On a routing problem. Quarterly of Applied Mathematics. 1958; 16:87–90.
  • Ford LR, Fulkerson DR. Flows in Network. Princeton University Press. 1962.
  • Sanci S, Isler V. A Parallel Algorithm for UAV Flight Route Planning on GPU. International Journal of Parallel Programming. 2011; 39(6):809–37.
  • Sintorn E, Assarsson U. Fast Parallel GPU- Sorting Using a Hybrid Algorithm. Journal of Parallel and Distributed Computing. 2008; 68(10):1381–8.
  • Jang H, Park A, Jung K. Neural Network Implementation Using CUDA and Open MP. Proceedings of the Digital Image Computing: Techniques and Applications. 2008.
  • Habibpour L, Yousefi S, Lighvan MZ, Aghdasi HS. 1D Chaos-based Image Encryption Acceleration by using GPU. Indian Journal of Science and Technology. 2016; 9(6). Doi:10.17485/ijst/2016/v9i6/72651.
  • Khemiri R, Sayadi FE, Atri M. MatLab-GPU-based 2D-DWT Acceleration for JPEG2000 with Single and Double-Precision. Indian Journal of Science and Technology. 2016; 9(12). Doi:10.17485/ijst/2016/v9i12/80526.
  • Zha X, Sahni S. GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU. IEEE Transaction on Computers. 2013; 62(6):1156–69.
  • Faujdar N, Ghrera SP. Performance Evaluation of Parallel Count Sort using GPU Computing with CUDA. Indian Journal of Science and Technology. 2016; 9(15). Doi:10.17485/ijst/2016/v9i15/80080.
  • Ha S, Matej S, Ispiryan M, Mueller K. GPU-Accelerated Forward and Back-Projections With Spatially Varying Kernels for 3D DIRECT TOF PET Reconstruction. IEEE Transaction on Nuclear Science. 2013; 60(1):166–73.
  • Crauser A, Mehlhom K, Meyer U, Sanders P. A parallelization of dijkstra’s shortest path algorithm. LNCS Springer-Verlag Berlin Heidelberg. 1998; 1450:722–31.
  • Brodal G, Traff J, Zarolingis CD. A parallel priority data structure with applications. Proceedings of the 11th International Parallel Processing Symposium. 1997.
  • Narayanan PJ. Single source shortest path problem on Processor arrays. Proceedings of the Fourth Symposium on the Frontiers of Massively Parallel Computing. 1992.
  • Papaefthymiou M, Rodrigue J. Implementing parallel shortest-paths algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1994; 59–68.
  • Tang Y, Zhang Y, Chen HA. Parallel shortest path algorithm based on graph-partitioning and iterative correcting. Proceedings of the International Conference on High Performance Computing and Communications. 2008.
  • Meyer U, Sanders P. Δ-stepping: A parallelizable shortest path algorithm. Journal of Algorithms. 2003; 49(1):114–52.
  • Crobak JR, Berry JW, Madduri K, Bader DA. Advanced shortest paths algorithms on a massively-multithreaded architecture. Proceedings of the Parallel and Distributed Processing Symposium. 2007.
  • Thorup M. Undirected single-source shortest paths with positive integer weights in liner time. Journal of the ACM. 1999; 46(3):362–94.
  • Fetterer A, Shekhar S. A performance analysis of hierarchical shortest path algorithms. Proceedings of the International Conference on Tools with Artificial Intelligence. 1997.
  • Harish P, Narayanan PJ. Accelerating large graph algorithms on the GPU using CUDA. LNCS Springer Berlin Heidelberg. 2007; 4873:197–208.
  • Kumar S, Misra A, Tomar RS. A Modified Parallel Approach to Single Source Shortest Path Problem for Massively Dense Graphs Using CUDA. Proceedings of the International Conference on Computer and Communication Technology. 2011.
  • Martin PJ, Torres R, Gavilanes A. CUDA Solutions for the SSSP Problem. LNCS Springer-Verlag Berlin Heidelberg. 2009; 5544:904–13.
  • Dashora S, Khare N. Implementation of Graph Algorithms over GPU: A Comparative Analysis. Proceeding of IEEE Students Conference on Electrical, Electronics and Computer Science. 2012.
  • Singh DP, Khare N. Parallel Implementation of the Single Source Shortest Path Algorithm on CPU–GPU Based Hybrid System. International Journal of Computer Science and Information Security. 2013; 11(9):74–80.
  • Ortega-Arranz H, Torres Y, Llanos DR, Gonzalez-Escribano A. A New GPU-based Approach to the Shortest Path Problem. Proceedings of International Conference on High Performance Computing and Simulation (HPCS). 2013.
  • Davidson A, Baxter S, Garland M, Owens JD. Work-efficient Parallel GPU Methods for Single-Source Shortest path. Proceedings of 28th IEEE International Parallel and Distributed Processing Symposium. 2014.
  • Ortega-Arranz H, Torres Y, Llanos DR, Gonzalez-Escribano A. Comprehensive Evaluation of a New GPU-based Approach to the Shortest Path Problem. International Journal of Parallel Programming. 2015; 43:918–38.
  • Singh DP, Khare N, Rasool A. Efficient Parallel Implementation of Single Source Shortest Path Algorithm on GPU Using CUDA. International Journal of Applied Engineering Research. 2016; 11(4):2560–7.
  • Katz GJ, Kider JT. All-Pairs Shortest-Paths for Large Graphs on the GPU. Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. 2007.
  • Matsumoto K, Nakasato N, Sedukhin SG. Blocked All-Pairs Shortest Paths Algorithm for Hybrid CPU-GPU System. Proceedings of the 13th IEEE International Conference on High Performance Computing and Communications. 2011.
  • Tran QN. Designing Efficient Many-Core Parallel Algorithms for All-Pairs Shortest-Paths Using CUDA. Proceedings of the Seventh International Conference on Information Technology: New Generations, 2010.
  • Buluc A, Gilbert JR, Budak C. Solving Path Problems on the GPU. Journal of Parallel Computing. 2010; 36(6):241–53.
  • Nickolls J, Buck I, Garland M, Skadron K. Scalable Parallel Programming with CUDA. ACM Queue. 2008; 6(2):40–53.
  • NVIDIA Corporation, CUDA C programming guide (2013). Available from: http://docs.nvidia.com/cuda/cuda-c-programming-guide/#axzz48cRjH1nP. Accessed date: 14 may 2016.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.