Parallel Batch Dynamic Single Source Shortest Path Algorithm and Its Implementation on GPU based Machine

Dhirendra Singh and Nilay Khare

Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, India

Abstract: In this fast changing and uncertain world, to meet the user’s requirements the computer applications based on real world data always try to give responses in the minimum possible time. Single Source Shortest Path (SSSP) calculation is a basic requirement of applications using graphs portraying real world data like social networks and road networks etc. to get useful information from them. Some of these real world data changes very frequently, so recalculation of the shortest path for all nodes of a graph depicting these real world data after small updates of graph structure is an expensive process. To minimize the cost of recalculation shortest path algorithms need to process only the affected part of a graph after any update, and to speed-up any process parallel implementation of algorithm is a frequently used technique. This paper proposes a new parallel batch dynamic SSSP calculation approach and shows its implementation on a CPU- Graphic Processing Unit (GPU) based hybrid machine. The proposed algorithm is defined for positive edge weighted graphs. It accepts multiple edge weight updates simultaneously. It uses parallel modified Bellman Ford algorithm for SSSP recalculation of all affected nodes. Nvidia’s Tesla C2075 GPU is used to run the parallel implementation of the algorithm. The proposed parallel algorithm shows up to a twenty-fold speed increase as compared to best serial algorithm available in literature.

Keywords: Parallel algorithm, graph algorithm, dynamic shortest path algorithm, network algorithm.