Large Graph Algorithms for Massively Multithreaded Architectures
The Graphics Processing Units (GPUs) provide high computation power at a low cost and is an important compute accelerator with a massively multithreaded architecture. In this paper, we present fast implementations of common graph operations like breadth first search, st connectivity, single source shortest path, all pairs shortest path, minimum spanning tree, and maximum flow for undirected graphs on the GPU using the CUDA programming model. Our implementations exhibit high performance, especially on large graphs. We use two data parallel programming methodologies for these algorithms. One is an iterative, mask based approach that processes valid data elements like vertices and edges using independent threads for each. The other is a divide and conquer approach that reduces the problem into smaller problems that are handled later using the same approach. Parallel algorithms for such problems have been reported in the literature before, especially on supercomputers. The massively multithreaded model of the GPU makes it possible to adopt the data parallel approach even to irregular algorithms like graph algorithms, using O(V or O(E) simultaneous threads. The algorithms and the underlying techniques presented in this paper are likely to be applicable to many irregular algorithms. We show the impact of our implementations on random, scalefree, and real life graphs of up to millions of vertices on highend and low end GPUs. The availability and spread of GPUs to desktops and laptops make them ideal candidates to accelerate graph operations over the CPU only implementations. Practical implementations of basic operations go a long way in realizing their potential.