Graph Traversal Algorithms on GPU

Traversal algorithm is the basic algorithm for graph processing. This section uses the graph coloring algorithm as an example to illustrate the challenges of implementing a graph traversal algorithm on accelerators like GPUs. There are great challenges in performing graph coloring on a GPU in general. First, the long-tail problem exists in the recursion algorithm because the conflict (i.e., different threads assign the adjacent nodes to the same color) becomes more likely to occur as the number of iterations increases. Second, it is hard to parallelize the sequential spread algorithm because the color allocation depends on the adjoining iteration. Third, the atomic operation is widely used on the GPU to maintain the color list, which can greatly reduce the efficiency of GPU threads. In this chapter, we propose a two-stage high-performance graph coloring algorithm, called Feluca, aiming to address the above challenges. Feluca combines the recursion-based method with the sequential spread-based method. In the first stage, Feluca uses a recursive routine to color a majority of the vertices in the graph. Then, it switches to the sequential spread method to color the remaining vertices in order to avoid the conflicts of the recursive algorithm. Moreover, the following techniques are proposed to further improve the graph coloring performance. (i) A new method is proposed to eliminate the cycles in the graph; (ii) a top-down scheme is developed to avoid the atomic operation originally required for color selection; and (iii) a novel color-centric coloring paradigm is designed to improve the degree of parallelism for the sequential spread part. All these newly developed techniques, together with further GPU-specific optimizations such as coalesced memory access, comprise an efficient parallel graph coloring solution in Feluca. We have conducted extensive experiments on NVIDIA GPU. The results show that Feluca can achieve 1.19–8.39 \(\times \) speedup over the state-of-the-art algorithms.