Performance Improvement in Large Graph Algorithms on GPU using CUDA: an Overview
|
10.5120/1520-1992 |
Swapnil D Joshi and Mrs. V S Inamdar. Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview. International Journal of Computer Applications 10(10):10–14, November 2010. Published By Foundation of Computer Science. BibTeX
@article{key:article,
author = {Swapnil D. Joshi and Mrs. V. S. Inamdar},
title = {Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview},
journal = {International Journal of Computer Applications},
year = {2010},
volume = {10},
number = {10},
pages = {10--14},
month = {November},
note = {Published By Foundation of Computer Science}
}
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.
We studied different parallel algorithms for Breadth first search, all pairs shortest path that are carried out on GPU using CUDA and make their comparative study with respect to execution time, data structure used, input data etc. In the paper, we presented overview of various parallel methods carried out on GPU using its multithreaded architecture for BFS, APSP by various authors.
Reference
- The Ninth DIMACS implementation challenge on shortest pathshttp://www.dis.uniroma1.it/ challenge9/
- NVIDIA. NVIDIA CUDA Programming Guide 2.0
- http://www.nvidia.com/object/cudadevelop.html/www.gpgpu.org
- S. Nagendran, M. Ashrafulla, J. Bagga, 2008 “Assessment of SIMD programming on graphics card”.
- J. Hyvonen, J. Saramaki, and K. Kaski, 2008 Efficient data structures for sparse network representation. Int. J. Comput. Math., 85(8):1219-1233.
- 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.
- Vibhav Vineet and P. J. Narayanan, 2009 “Large graph algorithms for massively multithreaded architecture”
- D. Chakrabarti, Y. Zhan, and C. Faloutsos, 2004 R-MAT: A recursive model for graph mining. In In SIAM International Conference on Data Mining.
- 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
- Paulius Micikevicius, 2004 General parallel computation on commodity graphics hardware: Case study with the all pairs shortest paths problem. In PDPTA, pages 1359–1365.
- 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,
- 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.
- A. Buluc, J. R. Gilbert, and C. Budak, 2008 Gaussian Elimination Based Algorithms on the GPU. Technical report, November.
- D. A. Bader and K. Madduri, 2006 GTgraph: A Synthetic Graph Generator Suite. Technical report.
- P. J. Narayanan, 1993 Processor Autonomy on SIMD Architectures. In International Conference on Supercomputing, pages 127-136.
- 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.