Exploiting Parallelism in Iterative Irregular Maxflow Computations on GPU Accelerators
Dept. of Comput. Sci., Univ. of Manitoba, Winnipeg, MB, Canada
12th IEEE International Conference on High Performance Computing and Communications (HPCC), 2010
@conference{solomon2010exploiting,
title={Exploiting Parallelism in Iterative Irregular Maxflow Computations on GPU Accelerators},
author={Solomon, S. and Thulasiraman, P. and Thulasiram, R.K.},
booktitle={2010 12th IEEE International Conference on High Performance Computing and Communications},
pages={297–304},
year={2010},
organization={IEEE}
}
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.
March 27, 2011 by hgpu
