Accelerating Large Graph Algorithms on the GPU Using CUDA
Center for Visual Information Technology, International Institute of Information Technology Hyderabad, INDIA
High Performance Computing, HiPC 2007 In High Performance Computing HiPC 2007, Vol. 4873 (2007), pp. 197-208-208.
@article{harish2007accelerating,
title={Accelerating large graph algorithms on the GPU using CUDA},
author={Harish, P. and Narayanan, P.},
journal={High Performance Computing–HiPC 2007},
pages={197–208},
year={2007},
publisher={Springer}
}
Large graphs involving millions of vertices are common in many practical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. Graphics Processing Units (GPUs) of today have high computation power and low price. They have a restrictive programming model and are tricky to use. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA programming model. We present a few fundamental algorithms â including breadth first search, single source shortest path, and all-pairs shortest path â using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1.5 seconds using the Nvidia 8800GTX GPU costing $600. In some cases optimal sequential algorithm is not the fastest on the GPU architecture. GPUs have great potential as high-performance co-processors.
October 28, 2010 by hgpu
