CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford

by Gaurav Hajela, Manish Pandey
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 95 - Number 15
Year of Publication: 2014
Authors: Gaurav Hajela, Manish Pandey
10.5120/16667-6659

Gaurav Hajela, Manish Pandey . Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford. International Journal of Computer Applications. 95, 15 ( June 2014), 1-6. DOI=10.5120/16667-6659

@article{ 10.5120/16667-6659,
author = { Gaurav Hajela, Manish Pandey },
title = { Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford },
journal = { International Journal of Computer Applications },
issue_date = { June 2014 },
volume = { 95 },
number = { 15 },
month = { June },
year = { 2014 },
issn = { 0975-8887 },
pages = { 1-6 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume95/number15/16667-6659/ },
doi = { 10.5120/16667-6659 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:19:29.363401+05:30
%A Gaurav Hajela
%A Manish Pandey
%T Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford
%J International Journal of Computer Applications
%@ 0975-8887
%V 95
%N 15
%P 1-6
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

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.

References
  1. Michael J. Bannister and David Eppstein , "Randomized Speedup of the Bellman Ford Algorithm" in arXiv:1111. 5414v1 [cs. DS] 23 Nov 2011.
  2. Andrew V. Goldberg, Tomasz Radzik , A Heuristic improvement of the Bellman Ford algorithm. Appl. Math. Lett. Vol. 6, No. 3, pp. 3-6, 1993.
  3. A. S. Nepomniaschaya, An Associative Version of the Bellman-Ford Algorithm for Finding the Shortest Paths in Directed Graphs, V. Malyshkin (Ed. ): PaCT 2001, LNCS 2127, pp. 285–292, 2001.
  4. J. Y. Yen. , An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics 27:526-530, 1970.
  5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Problem 24-1: Yen's improvement to Bellman Ford. Introduction to Algorithms, 2nd edition, pp. 614-615. MIT Press, 2001.
  6. R. Bellman. On a routing problem. Quarterly of Applied Mathematics 16:87-90,1958.
  7. Yefim Dinitz , Rotem Itzhak , Hybrid Bellman-Ford-Dijkstra Algorithm.
  8. Ayd?n Buluc , John R. Gilbert and Ceren Budak , "Solving Path Problems on the GPU" , Journal Parallel Computing Volume 36 Issue 5-6, June,2010 Pages 241-253.
  9. Andrew Davidson , Sean Baxter, Michael Garland , John D. Owens , "Work-Efficient Parallel GPU Methods for Single-Source Shortest Path " in International Parallel and Distributed Processing Symposium, 2014
  10. Owens J. D. , Davis, Houston, M. , Luebke, D. , Green, S. , "GPU Computing", in: Proceedings of the IEEE, Volume: 96 , Issue: 5 , 2008.
  11. A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Addison-Wesley pub. , 2011.
  12. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press, Sep. 2001.
  13. Kumar, S. ; Misra, A. ; Tomar, R. S. ,"A modified parallel approach to Single Source Shortest Path Problem for massively dense graphs using CUDA" in Computer and Communication Technology (ICCCT), 2011 2nd International Conference on , vol. , no. , pp. 635,639, 15-17 Sept. 2011.
  14. Atul Khanna, John Zinky , "The Revised ARPANET Routing Metric", in 1969 ACM.
Index Terms

Computer Science
Information Sciences

Keywords

Shortest path problem OpenCL Graphical processing unit(GPU).

Powered by PhDFocusTM