@inproceedings{1f46a624432b41b3af596e01d59a6729,
title = "Highly efficient compensation-based parallelism for wavefront loops on GPUs",
abstract = "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.",
keywords = "GPU, Locality, Parallelism, Prefix Sum, Scan, Synchronization, Wavefront",
author = "Kaixi Hou and Hao Wang and Feng, {Wu Chun} and Vetter, {Jeffrey S.} and Seyong Lee",
note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 ; Conference date: 21-05-2018 Through 25-05-2018",
year = "2018",
month = aug,
day = "3",
doi = "10.1109/IPDPS.2018.00037",
language = "English",
isbn = "9781538643686",
series = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "276--285",
booktitle = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",
}