Highly efficient compensation-based parallelism for wavefront loops on GPUs

Kaixi Hou, Hao Wang, Wu Chun Feng, Jeffrey S. Vetter, Seyong Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages276-285
Number of pages10
ISBN (Print)9781538643686
DOIs
StatePublished - Aug 3 2018
Event32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 - Vancouver, Canada
Duration: May 21 2018May 25 2018

Publication series

NameProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

Conference

Conference32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018
Country/TerritoryCanada
CityVancouver
Period05/21/1805/25/18

Keywords

  • GPU
  • Locality
  • Parallelism
  • Prefix Sum
  • Scan
  • Synchronization
  • Wavefront

Fingerprint

Dive into the research topics of 'Highly efficient compensation-based parallelism for wavefront loops on GPUs'. Together they form a unique fingerprint.

Cite this