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

Cache Friendly Bellman-Ford algorithm using OpenCL

by Lekha Jadhav, Rahul Dubey, Manish Shrivastava
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 139 - Number 13
Year of Publication: 2016
Authors: Lekha Jadhav, Rahul Dubey, Manish Shrivastava
10.5120/ijca2016909305

Lekha Jadhav, Rahul Dubey, Manish Shrivastava . Cache Friendly Bellman-Ford algorithm using OpenCL. International Journal of Computer Applications. 139, 13 ( April 2016), 1-3. DOI=10.5120/ijca2016909305

@article{ 10.5120/ijca2016909305,
author = { Lekha Jadhav, Rahul Dubey, Manish Shrivastava },
title = { Cache Friendly Bellman-Ford algorithm using OpenCL },
journal = { International Journal of Computer Applications },
issue_date = { April 2016 },
volume = { 139 },
number = { 13 },
month = { April },
year = { 2016 },
issn = { 0975-8887 },
pages = { 1-3 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume139/number13/24547-2016909305/ },
doi = { 10.5120/ijca2016909305 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:40:49.089300+05:30
%A Lekha Jadhav
%A Rahul Dubey
%A Manish Shrivastava
%T Cache Friendly Bellman-Ford algorithm using OpenCL
%J International Journal of Computer Applications
%@ 0975-8887
%V 139
%N 13
%P 1-3
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Shortest path algorithms play a vital role in real world applications. In this paper a cache friendly implementation for Bellman Ford algorithm to solve single source shortest path and all pair shortest path algorithm is proposed. The proposed algorithm is compared with sequential algorithm in terms of execution time, cache hit, ALUPacking and ALUBusy. This algorithm is also tuned with execution environment to yield maximum performance. In this paper we have discussed all above factors in terms of framework called OpenCL.

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. A. Munshi, B. R. Gaster, T.G. Mattson, J. Fung, D. Ginsburg, “OpenCL Programming Guide”,Addison-Wesley pub.,2011.
  7. YefimDinitz ,RotemItzhak , Hybrid Bellman-Ford-Dijkstra Algorithm.
  8. AydınBuluc , John R. Gilbert and CerenBudak , “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.
Index Terms

Computer Science
Information Sciences

Keywords

Bellman-Ford OpenCL ALUPacking ALUBusy Cache hit.

Powered by PhDFocusTM