New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA)
|
10.5120/19375-1027 |
Pankhari Agarwal and Maitreyee Dutta. Article: New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA). International Journal of Computer Applications 110(13):11-15, January 2015. Full text available. BibTeX
@article{key:article,
author = {Pankhari Agarwal and Maitreyee Dutta},
title = {Article: New Approach of Bellman Ford Algorithm on GPU using Compute Unified Design Architecture (CUDA)},
journal = {International Journal of Computer Applications},
year = {2015},
volume = {110},
number = {13},
pages = {11-15},
month = {January},
note = {Full text available}
}
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
- Ashok Jagannathan. Applications of Shortest Path Algorithms to VLSI Chip Layout Problems. Thesis Report. University of Illinois. Chicago. 2000.
- 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.
- 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).
- 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.
- Meyer U. , Sanders P. 2003. ? -stepping: a parallelizable shortest path algorithm. J. of Algorithms 49, pp. 114– 152.
- 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.
- 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.
- 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.
- 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.
- 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.
- Harish P. and Narayanan P. J. 2007. Accelerating large graph algorithms on the GPU using CUDA, IEEE High Performance Computing, pp. 197-208.
- Nvidia CUDA: http://www. nvidia. com/cuda
- Srinivas A. , Manish P. , Ramamurthy B and Viktor K. P. 2007. High Performance Computing - HiPC 2007: 14th International Conference, Goa, pp. 199-205.
- 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
- Gunjan S. , Amrita T. , Dhirendra P. S. , "New Approach for Graph Algorithms on GPU Using CUDA" submitted to journal "IJCA".
- Luo L. And Wong M. , Hwu W. 2010An Effective GPU Implementation of Breadth-First Search, DAC'10, ACM, pp. 52-55.