Parallel batch dynamic single source shortest path algorithm and its implementation on gpu based machine
Joint Authors
Source
The International Arab Journal of Information Technology
Issue
Vol. 16, Issue 2 (31 Mar. 2019), pp.217-225, 9 p.
Publisher
Publication Date
2019-03-31
Country of Publication
Jordan
No. of Pages
9
Main Subjects
Information Technology and Computer Science
Abstract EN
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.
American Psychological Association (APA)
Singh, Dhirendra& Khare, Nilay. 2019. Parallel batch dynamic single source shortest path algorithm and its implementation on gpu based machine. The International Arab Journal of Information Technology،Vol. 16, no. 2, pp.217-225.
https://search.emarefa.net/detail/BIM-894961
Modern Language Association (MLA)
Singh, Dhirendra& Khare, Nilay. Parallel batch dynamic single source shortest path algorithm and its implementation on gpu based machine. The International Arab Journal of Information Technology Vol. 16, no. 2 (Mar. 2019), pp.217-225.
https://search.emarefa.net/detail/BIM-894961
American Medical Association (AMA)
Singh, Dhirendra& Khare, Nilay. Parallel batch dynamic single source shortest path algorithm and its implementation on gpu based machine. The International Arab Journal of Information Technology. 2019. Vol. 16, no. 2, pp.217-225.
https://search.emarefa.net/detail/BIM-894961
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 224-225
Record ID
BIM-894961