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

New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA)

by Pankhari Agarwal, Maitreyee Dutta
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 110 - Number 13
Year of Publication: 2015
Authors: Pankhari Agarwal, Maitreyee Dutta
10.5120/19375-1027

Pankhari Agarwal, Maitreyee Dutta . New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA). International Journal of Computer Applications. 110, 13 ( January 2015), 11-15. DOI=10.5120/19375-1027

@article{ 10.5120/19375-1027,
author = { Pankhari Agarwal, Maitreyee Dutta },
title = { New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA) },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 110 },
number = { 13 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 11-15 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume110/number13/19375-1027/ },
doi = { 10.5120/19375-1027 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:46:15.106914+05:30
%A Pankhari Agarwal
%A Maitreyee Dutta
%T New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA)
%J International Journal of Computer Applications
%@ 0975-8887
%V 110
%N 13
%P 11-15
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Large graphs involving millions of vertices are common in many practical applications and are challenging to process. To process them we present a fundamental single source shortest path (SSSP) algorithm i. e. Bellman Ford algorithm. Bellman Ford algorithm is a well known method of SSSP calculation and which is considered to be an optimization problem in the graph. SSSP problem is a major problem in the graph theory that has various applications in real world that demand execution of these algorithms in large graphs having millions of edges and sequential implementation of these algorithms takes large amount of time. In this paper, we investigates some methods which aim at parallelizing Bellman Ford Algorithm and to implement some extended or enhanced versions of this algorithm over GPU. GPU provides an application programming interface named as CUDA. CUDA is a general purpose parallel programming architecture which was introduced by Nvidia. This algorithm can reduce the execution time up to half of the basic Bellman Ford algorithm.

References
  1. Ashok Jagannathan. Applications of Shortest Path Algorithms to VLSI Chip Layout Problems. Thesis Report. University of Illinois. Chicago. 2000.
  2. Karla Vittori, Alexandre C. B. Delbem and Sérgio L. Pereira. Ant-Based Phylogenetic Reconstruction (ABPR): A new distance algorithm for phylogenetic estimation based on ant colony optimization. Genetics and Molecular Biolog. , 31(4), 2008.
  3. Jiyi Zhang, Wen Luo, Linwang Yuan, Weichang Mei. Shortest path algorithm in GIS network analysis based on Clifford algebra. Transactions of the IRE Professional Group. 18(11, 12).
  4. A. Bustamam, G. Ardaneswari, D. Lestari, "Implementation of CUDA GPU-based parallel computing on Smith-Waterman algorithm to sequence database searches", International Conference on Advanced Computer Science and Information Systems (ICACSIS), IEEE, pp. 137-142, 2013.
  5. Meyer U. , Sanders P. 2003. ? -stepping: a parallelizable shortest path algorithm. J. of Algorithms 49, pp. 114– 152.
  6. Bader D. A. , Madduri K. 2006. Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. ICPP, pp. 523–530.
  7. Bader D. A. , Madduri K. 2006. Parallel algorithms for evaluating centrality indices in real-world networks. ICPP 2006. Proceedings of the 2006 International Conference on Parallel Processing, IEEE Computer Society Press, Los Alamitos , pp. 539–550.
  8. Crauser A. , Mehlhorn K. , Meyer U. , and Sanders P. 1998. A Parallelization of Dijkstra's Shortest Path Algorithm. MFCS'98- LNCS 1450, Lubos Prim et al. (Eds. ), Springer-Verlag Berlin Heidelberg, pp. 722-731.
  9. Jasika N. , Alispahic N. , Elma A. , Ilvana K. , Elma L. and Nosovic N. 2012. Dijkstra's shortest path algorithm serial and parallel execution performance analysis. MIPRO, pp. 1811-1815.
  10. Martín P. J. , Torres R. , and Gavilanes A. 2009. CUDA Solutions for the SSSP Problem. ICCS 2009, Part I, LNCS 5544, G. Allen et al. (Eds. ), Springer-Verlag Berlin Heidelberg , pp. 904-913.
  11. Harish P. and Narayanan P. J. 2007. Accelerating large graph algorithms on the GPU using CUDA, IEEE High Performance Computing, pp. 197-208.
  12. Nvidia CUDA: http://www. nvidia. com/cuda
  13. Srinivas A. , Manish P. , Ramamurthy B and Viktor K. P. 2007. High Performance Computing - HiPC 2007: 14th International Conference, Goa, pp. 199-205.
  14. Frederico L. Cabral, Carla Osthoff, Rafael Nardes, Daniel Ramos1 June 2014. Massive Parallelism With Gpus For Centrality Ranking In Complex Networks in International Journal Of Computer Science & Information Technology (IJCSIT) Vol 6,No3
  15. Gunjan S. , Amrita T. , Dhirendra P. S. , "New Approach for Graph Algorithms on GPU Using CUDA" submitted to journal "IJCA".
  16. Luo L. And Wong M. , Hwu W. 2010An Effective GPU Implementation of Breadth-First Search, DAC'10, ACM, pp. 52-55.
Index Terms

Computer Science
Information Sciences

Keywords

SSSP (Single Source Shortest Path) Problem Graphics Processing Units (GPUs) CUDA (Compute Unified Device Architecture).

Powered by PhDFocusTM