Parallel Batch Dynamic Single Source Shortest Path Algorithm and Its Implementation on GPU based Machine
Journal: The International Arab Journal of Information Technology (Vol.16, No. 2)Publication Date: 2019-03-01
Authors : Dhirendra Singh Nilay Khare;
Page : 217-225
Keywords : Parallel algorithm; graph algorithm; dynamic shortest path algorithm; network algorithm.;
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.
Other Latest Articles
- Formal Architecture and Verification of a Smart Flood Monitoring System-of-Systems
- Data Hiding Based on Contrast Mapping Using DNA Medium
- Rough Set-Based Reduction of Incomplete Medical Datasets by Reducing the Number of Missing Values
- Using the Improved PROMETHEE for Selection of Trustworthy Cloud Database Servers
- Evaluation for Diaphragm’s Deflection for Touch Mode MEMS Pressure Sensors
Last modified: 2019-04-28 18:57:04