Accelerating Push-Relabel Algorithm on GPU via Two-Level Parallelism Paradigm and Efficient CSR Designs

The push-relabel algorithm is an efficient algorithm that solves the maximum flow/minimum cut problems of its affinity to parallelization. As the size of graphs grows exponentially, researchers have used Graphics Processing Units (GPUs) to accelerate the computation of the push-relabel algorithm further. However, prior works suffer from a significant imbalanced workload distribution while computing with the GPU, which reduces the utilization of the GPU and increases execution time. Therefore, this paper first identifies the two challenges with the cost model we designed. Based on the observation of the model, we propose a novel two-level parallelism neighbor scanning (TLPNS) with two enhanced compressed sparse representations (CSR) to alleviate the workload imbalance. The enhanced CSR significantly reduces the time spent searching for minimum-height neighbors. Additionally, the two-level parallelism approach of our algorithm can effectively reduce the number of idle threads and improve the utilization of the GPU. In the experiment, the enhanced CSRs can significantly decrease the execution time, while the TLPNS can further achieve up to 23x and 6.9x runtime speedup compared to the state-of-the-art work on enhanced CSRs and real-world graphs in maximum flow and bipartite matching tasks, respectively. Our code is open-sourced for further research on accelerating the push-relabel algorithm.