The week's pick
Random Articles
Reseach Article
Article:Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview
| 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
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
- 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.
Index Terms
Keywords