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

New Approach for Graph Algorithms on GPU using CUDA

by Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 72 - Number 18
Year of Publication: 2013
Authors: Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh
10.5120/12645-9386

Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh . New Approach for Graph Algorithms on GPU using CUDA. International Journal of Computer Applications. 72, 18 ( June 2013), 38-42. DOI=10.5120/12645-9386

@article{ 10.5120/12645-9386,
author = { Gunjan Singla, Amrita Tiwari, Dhirendra Pratap Singh },
title = { New Approach for Graph Algorithms on GPU using CUDA },
journal = { International Journal of Computer Applications },
issue_date = { June 2013 },
volume = { 72 },
number = { 18 },
month = { June },
year = { 2013 },
issn = { 0975-8887 },
pages = { 38-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume72/number18/12645-9386/ },
doi = { 10.5120/12645-9386 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:38:17.753483+05:30
%A Gunjan Singla
%A Amrita Tiwari
%A Dhirendra Pratap Singh
%T New Approach for Graph Algorithms on GPU using CUDA
%J International Journal of Computer Applications
%@ 0975-8887
%V 72
%N 18
%P 38-42
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Large Graph algorithms like Breadth-First Search (BFS), Depth-First Search(DFS), shortest path algorithms etc. used frequently in various engineering and real world applications that demand execution of these algorithms in large graphs having millions of edges and sequential implementation of these algorithms takes large amount of time. Today's Graphics Processing Units (GPUs) provide a platform to implement such applications with high computation power and massively multithreaded architecture at low price. In this paper, we present parallel implementations of two basic graph algorithms breadth-first search and Dijkstra's single source shortest path algorithm by using a new approach called edge based kernel execution on GPU. The performance analysis of parallel implementation over the serial execution gives a good speed-up.

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. Dijkstra E. W. 1959. A note on two problems in connexion with graphs. Num. Math. 1, pp. 269–271
  5. Quinn M. J. and Deo N. 1984. Parallel graph algorithms. ACM Comput. Surv. , 16(3), pp. 319-348.
  6. Reghbati A. E. and Corneil D. G. 1978. Parallel computations in graph theory. SIAM Journal of Computing, 2(2): pp. 230-237.
  7. Meyer U. , Sanders P. 2003. ? -stepping: a parallelizable shortest path algorithm. J. of Algorithms 49, pp. 114–152.
  8. 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.
  9. 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
  10. 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.
  11. 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.
  12. 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.
  13. Luo L. And Wong M. , Hwu W. 2010An Effective GPU Implementation of Breadth-First Search, DAC'10, ACM, pp. 52-55.
  14. Harish P. and Narayanan P. J. 2007. Accelerating large graph algorithms on the GPU using CUDA, IEEE High Performance Computing, pp. 197-208.
  15. Nvidia, CUDA programming guide version 3, at developer. download. nvidia. com/compute/cuda/1_1/NVIDIA_CUDA_Programming_Guide. pdf (2010).
  16. Nvidia CUDA: http://www. nvidia. com/cuda/.
Index Terms

Computer Science
Information Sciences

Keywords

SSSP (Single Source Shortest Path) problem Dijkstra's algorithm BFS (Breadth -First Search) CUDA (Compute Unified Device Architecture) model GPU(Graphic Processing Unit)

Powered by PhDFocusTM