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

Zhengyu He, Bo Hong
School of Electrical and Computer Engineering, Georgia Institute of Technology
IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2010


   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},






Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: