Graph Analysis Algorithms on GPU

Centrality measure is one of the most typical graph analysis algorithms. Recently, some highly sophisticated works have introduced a collection of centrality measures for real-world graphs. This chapter chooses one of the centrality measure algorithms as an example to indicate how to optimize the graph analysis performance on GPU. Most of these centrality measures account for the various vertex characteristics accustomed to assessing the importance of a vertex in a graph. Betweenness centrality (BC) is widely used to measure a vertex’s significance by using the frequency of a vertex appearing in the shortest path between other vertices. However, the most recent algorithms in BC computation suffer from the problem of high auxiliary memory consumption. To reduce BC computing’s memory consumption, we propose a path-merging-based algorithm called Galliot to calculate the BC values using GPU, which aims to minimize the on-board memory consumption and enable the BC computation of large-scale graphs on GPU. The proposed algorithm requires \(\mathcal {O}(n)\) space and runs in \(\mathcal {O}(mn)\) time on unweighted graphs. We present the theoretical principle for the proposed path merging method. Moreover, we propose a locality-oriented policy to maintain and update the worklist to improve the data locality of GPU. In addition, we conducted extensive experiments on NVIDIA GPUs to show the performance of Galliot. The results show that Galliot can process larger graphs, which have \(11.32\times \) more vertices and \(5.67\times \) more edges than the graphs that recent works can process. Moreover, Galliot can achieve up to \(38.77\times \) speedup over the existing methods.