Exploiting Parallelism in Iterative Irregular Maxflow Computations on GPU Accelerators

The Graphics Processing Unit (GPU) is an asymmetric, heterogeneous multi-core architecture that can be used for high performance parallel computing applications. However, a significant level of interest has been focused on algorithms for solving regular problems, as these applications typically map well to the GPU. Irregular applications, which rely on pointer or graph-based data structures, have not been as extensively studied and are significantly more difficult to implement or map in an efficient fashion on the GPU. In this paper, we consider a graph-based maximum flow algorithm that has applications in network optimization problems. In the literature, the push-relabel maximum flow algorithm has been considered on the GPU. We believe that Malhotra, Pramodh Kumar and Maheshwari´s algorithm is better suited for the GPU due to the synchronous, iterative nature of the algorithm. As a result, we choose this algorithm for our study. We show that the performance of the GPU algorithm far exceeds that of a sequential CPU algorithm.