Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford
Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, India
International Journal of Computer Applications, Volume 95, No. 15, 2014
@article{hajela2014parallel,
author={Gaurav Hajela and Manish Pandey},
title={Article: Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford},
journal={International Journal of Computer Applications},
year={2014},
volume={95},
number={15},
pages={1-6},
month={June},
note={Published by Foundation of Computer Science, New York, USA}
}
In this paper, different parallel implementations of Bellman-Ford algorithm on GPU using OpenCL are presented. These variants include Bellman-Ford for solving single source shortest path (SSSP) having two variants and Bellman-Ford for all pair shortest path (APSP) problems. Also, a comparative analysis of their performances on CPU and GPU is discussed in this paper.Write-write consistency in Bellman-Ford is overcome using synchronization mechanism available in OpenCL and by explicit synchronization by modifying the algorithm.An average speed up of 13.8x for parallel bellman ford for SSSP and an average speed up of 18.5x for bellman ford for APSP is achieved by proposed algorithm.
July 12, 2014 by hgpu
