CFP last date
20 June 2024
Reseach Article

Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview

by Swapnil D. Joshi, Mrs. V. S. Inamdar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 10 - Number 10
Year of Publication: 2010
Authors: Swapnil D. Joshi, Mrs. V. S. Inamdar
10.5120/1520-1992

Swapnil D. Joshi, Mrs. V. S. Inamdar . Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview. International Journal of Computer Applications. 10, 10 ( November 2010), 10-14. DOI=10.5120/1520-1992

@article{ 10.5120/1520-1992,
author = { Swapnil D. Joshi, Mrs. V. S. Inamdar },
title = { Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview },
journal = { International Journal of Computer Applications },
issue_date = { November 2010 },
volume = { 10 },
number = { 10 },
month = { November },
year = { 2010 },
issn = { 0975-8887 },
pages = { 10-14 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume10/number10/1520-1992/ },
doi = { 10.5120/1520-1992 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:58:33.847374+05:30
%A Swapnil D. Joshi
%A Mrs. V. S. Inamdar
%T Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview
%J International Journal of Computer Applications
%@ 0975-8887
%V 10
%N 10
%P 10-14
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The basic operations on the graphs with millions of vertices are common in various applications. To have faster execution of such operations is very essential to reduce overall computation time. Today’s Graphics processing units (GPUs) have high computation power and low price. This device can be treated as an array of Single Instruction Multiple Data (SIMD) processors using CUDA software interface by Nvidia. Massively Multithreaded architecture of a CUDA device makes various threads to run in parallel and hence making optimum use of available computation power of GPU. In case of graph algorithms, vertices of the graphs are processed in parallel by mapping them to various threads on device. By making thousands of threads to run in parallel, computation time required for these algorithms is drastically decreased as compared to their CPU implementation.

References
  1. The Ninth DIMACS implementation challenge on shortest pathshttp://www.dis.uniroma1.it/ challenge9/
  2. NVIDIA. NVIDIA CUDA Programming Guide 2.0
  3. http://www.nvidia.com/object/cudadevelop.html/www.gpgpu.org
  4. S. Nagendran, M. Ashrafulla, J. Bagga, 2008 “Assessment of SIMD programming on graphics card”.
  5. J. Hyvonen, J. Saramaki, and K. Kaski, 2008 Efficient data structures for sparse network representation. Int. J. Comput. Math., 85(8):1219-1233.
  6. N. K. Govindaraju, S. Larsen, J. Gray, and D. Manocha, 2006 Memory model for scientific algorithms on graphics processors. In SC '06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, page 89.
  7. Vibhav Vineet and P. J. Narayanan, 2009 “Large graph algorithms for massively multithreaded architecture”
  8. D. Chakrabarti, Y. Zhan, and C. Faloutsos, 2004 R-MAT: A recursive model for graph mining. In In SIAM International Conference on Data Mining.
  9. D. A. Bader and K. Madduri, 2006 Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA- 2. In ICPP, pages 523-530
  10. Paulius Micikevicius, 2004 General parallel computation on commodity graphics hardware: Case study with the all pairs shortest paths problem. In PDPTA, pages 1359–1365.
  11. P. Harish and P. J. Narayanan, 2007 Accelerating Large Graph Algorithms on the GPU Using CUDA. In HiPC, volume 4873 of Lecture Notes in Computer Science, pages 197-208,
  12. G. J. Katz and J. T. Kider, Jr. , 2008 All pairs shortest-paths for large graphs on the GPU. In GH '08: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pages 47-55.
  13. A. Buluc, J. R. Gilbert, and C. Budak, 2008 Gaussian Elimination Based Algorithms on the GPU. Technical report, November.
  14. D. A. Bader and K. Madduri, 2006 GTgraph: A Synthetic Graph Generator Suite. Technical report.
  15. P. J. Narayanan, 1993 Processor Autonomy on SIMD Architectures. In International Conference on Supercomputing, pages 127-136.
  16. M. Hussein, A. Varshney, and L. Davis, 2007 On Implementing Graph Cuts on CUDA. In First Workshop on General Purpose Processing on Graphics Processing Units.
Index Terms

Computer Science
Information Sciences

Keywords

Parallel computing Graph Algorithms SIMD architecture GPU CUDA