## Dynamically tuned push-relabel algorithm for the maximum flow problem on CPU-GPU-Hybrid platforms

School of Electrical and Computer Engineering, Georgia Institute of Technology

IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2010

@conference{he2010dynamically,

title={Dynamically tuned push-relabel algorithm for the maximum flow problem on CPU-GPU-Hybrid platforms},

author={He, Z. and Hong, B.},

booktitle={Parallel & Distributed Processing (IPDPS), 2010 IEEE International Symposium on},

pages={1–10},

issn={1530-2075},

year={2010},

organization={IEEE}

}

The maximum flow problem is a fundamental graph theory problem with many important applications. Max-flow algorithms based on the push-relabel method are known to have better complexity bound and faster practical execution speed than others. However, existing push-relabel algorithms are designed for uniprocessors or parallel processors that support locking primitives, thus making it very difficult to apply the push-relabel technique to CUDA-based GPUs. In this paper, we present a first generic parallel push-relabel algorithm for CUDA devices. We model the parallelization efficiency of the algorithm, which reveals that, for a given input graph, the level of parallelism varies during the execution of the algorithm. To maximize the execution efficiency, we develop a dynamically tuned algorithm that utilizes both CPU and GPU by adaptively switching between the two computing units during run time. We show that algorithm finds the maximum flow with O(|V|^2|E|) operations (summed over both the CPU and the GPU). Extensive experimental results show that the new algorithm is up to 2 times faster than the push-relabel algorithm by Goldberg et al.

March 6, 2011 by hgpu