Abstract :
Maximum flow is one of the fundamental problems in graph theory with several applications such as bipartite matchings, image segmentation, disjoint paths, network connectivity, etc. Goldberg Tarjan’s Push Relabel (PR) Algorithm is a well-known algorithm that calculates the maximum s-t flow on a directed weighted graph. PR algorithm has been effectively parallelized on the GPUs. For many of the maximum flow algorit hm’s error-tolerant applications, it is sufficient to compute the approximate maximum flow value. In this work, we propose four techniques for improving the push-relabel algorithm’s performance on the GPUs keeping its error-tolerant applications in mind. The first technique removes the vertices that are irrelevant from the maximum flow computation point of view from the flow network. The second technique reduces the thread divergence by removing the edges from the high outdegree nodes followed by the nodes’ renumbering. The third technique prunes the excess cycles detected during the execution of the algorithm. The fourth technique tries to reuse the min-heights computed in the particular cycle by the algorithm for its subsequent cycles. We also add the knobs for those techniques that add the inaccuracy in the maximum flow computation. Our experimental results show 1.18×, 1.23×, 2.30×, and 1.66× speedups, respectively, for each of the above four techniques on a suite of real-world and synthetic graphs.