| Accelerating large graph algorithms on the GPU using CUDA (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Graph algorithms are fundamental to many disciplines and application areas. Large graphs involving millions of vertices are common in scientific and engineering applications. Practical-time implementations using high-end computing resources have been reported but are accessible only to a few. Graphics Processing Units (GPUs) are fast emerging as inexpensive parallel processors due to their high computation power and low price. The G80 line of Nvidia GPUs provides the CUDA programming model that treats the GPU as a SIMD processor array. We present a few fundamental algorithms using this programming model on large graphs. We report results on breadth first search, single source shortest path, and all-pairs shortest path. Our implementation is able to compute single source shortest paths on a graph with 10 million vertices in about 1.5 seconds using the Nvidia 8800GTX GPU costing $600. The GPU can then be used as an inexpensive co-processor to accelerate parts of the applications. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||