Skip to main content

Highly Efficient Compensation-Based Parallelism for Wavefront Loops on GPUs...

by Kaixi Hou, Hao Wang, Wu-chun Feng, Jeffrey S Vetter, Seyong Lee
Publication Type
Conference Paper
Journal Name
IEEE Xplore
Publication Date
Page Numbers
276 to 285
Conference Name
IEEE International Parallel and Distributed Processing Symposium (IPDPS 2018)
Conference Location
Vancouver, Canada
Conference Sponsor
Conference Date

Wavefront loops are widely used in many scientific applications, e.g., partial differential equation (PDE) solvers and sequence alignment tools. However, due to the data dependencies in wavefront loops, it is challenging to fully utilize the abundant compute units of GPUs and to reuse data through their memory hierarchy. Existing solutions can only optimize for these factors to a limited extent. For example, tiling-based methods optimize memory access but may result in load imbalance; while compensation-based methods, which change the original order of computation to expose more parallelism and then compensate for it, suffer from both global synchronization overhead and limited generality. In this paper, we first prove under which circumstances that breaking data dependencies and properly changing the sequence of computation operators in our compensation-based method does not affect the correctness of results. Based on this analysis, we design a highly efficient compensation-based parallelism on GPUs. Our method provides weighted scan-based GPU kernels to optimize the computation and combines with the tiling method to optimize memory access and synchronization. The performance results on the NVIDIA K80 and P100 GPU platforms demonstrate that our method can achieve significant improvements for four types of real-world application kernels over the state-of-the-art research.