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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL

by Umesh Nayak, Rajeev Pandey, Uday Chourasia
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 179 - Number 40
Year of Publication: 2018
Authors: Umesh Nayak, Rajeev Pandey, Uday Chourasia
10.5120/ijca2018916948

Umesh Nayak, Rajeev Pandey, Uday Chourasia . A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL. International Journal of Computer Applications. 179, 40 ( May 2018), 34-38. DOI=10.5120/ijca2018916948

@article{ 10.5120/ijca2018916948,
author = { Umesh Nayak, Rajeev Pandey, Uday Chourasia },
title = { A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL },
journal = { International Journal of Computer Applications },
issue_date = { May 2018 },
volume = { 179 },
number = { 40 },
month = { May },
year = { 2018 },
issn = { 0975-8887 },
pages = { 34-38 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume179/number40/29349-2018916948/ },
doi = { 10.5120/ijca2018916948 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:58:00.280343+05:30
%A Umesh Nayak
%A Rajeev Pandey
%A Uday Chourasia
%T A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL
%J International Journal of Computer Applications
%@ 0975-8887
%V 179
%N 40
%P 34-38
%D 2018
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Finding shortest path for various applications is important in various domains. But to provide result for complex graphs in real time is a challenging task. So in this paper four shortest path algorithms namely Dijkstra’s algorithm, Floyd Warshall, Bellman Ford and Jhonsons algorithm are studied and analyzed to detect parallelism in them and the parallelized version of all three is implemented using parallel computing framework OpenCL. It is found that Bellman Ford and Floyd Warshall contains fine grained parallelism while Jhonsons has less parallelism.

References
  1. Andrew Davidson, Sean Baxter, Michael Garland, John D. Owens, “Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths” in 2014 IEEE 28th International Parallel & Distributed Processing Symposium.
  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.
Index Terms

Computer Science
Information Sciences

Keywords

Bellman-Ford Dijkstra Floyd Warshall

Powered by PhDFocusTM