Determining the maximum possible flow (max-flow) between a source vertex and a sink vertex in a network with given capacities on every edge is a fundamental graph problem found in many domains. The Push-Relabel (PR) algorithm is the leading approach for solving the max-flow problem and has been parallelized for GPUs. However, existing approaches suffer from scalability issues and may perform poorly on large graphs. This paper focuses on improving the efficiency of the PR algorithm on GPUs, presenting several implementation and parallelization improvements compared to the state of the art. Our improvements include fast global relabeling on the GPU, worklists to minimize wasted work and CUDA threads, and a two-level parallelization scheme to improve load balancing. Our approach is, on average,$5.75 x$faster than the fastest prior GPU implementation and$5.08 x$faster than the fastest CPU code.

Graph analytics has become a major workload in recent years. The underlying core algorithms tend to be irregular and data dependent, making them challenging to parallelize. Yet, these algorithms can be implemented and parallelized in many ways for CPUs and even more ways for GPUs. We took 6 key graph algorithms and created hundreds of CUDA, OpenMP, and parallel C++ versions of each of them, most of which have never been described or studied. To determine which parallelization and implementation styles work well and under what circumstances, we evaluated the resulting 1106 programs on 2 GPUs and 2 CPUs using 5 input graphs. Our results show which styles and combinations perform well and which ones should be avoided. We found that choosing the wrong implementation style can yield over a 10× slowdown on average. The worst combinations of styles can cost 6 orders of magnitude in performance.