Reduction Drawing: Language Constructs and Polyhedral Compilation for Reductions on GPUs

Chandan Reddy 1 Michael Kruse 1 Albert Cohen 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : Reductions are common in scientific and data-crunching codes, and a typical source of bottlenecks on massively parallel architectures such as GPUs. Reductions are memory-bound, and achieving peak performance involves sophisticated optimizations. There exist libraries such as CUB and Thrust providing highly tuned implementations of reductions on GPUs. However, library APIs are not flexible enough to express user-defined reductions on arbitrary data types and array indexing schemes. Languages such as OpenACC provide declarative syntax to express reductions. Such approaches support a limited range of reduction operators and do not facilitate the application of complex program transformations in presence of reductions. We present language constructs that let a programmer express arbitrary reductions on user-defined data types matching the performance of tuned library implementations. We also extend a polyhedral compilation flow to process these user-defined reductions, enabling optimizations such as the fusion of multiple reductions, combining reductions with other loop transformations, and optimizing data transfers and storage in the presence of reductions. We implemented these language constructs and compilation methods in the PPCG framework and conducted experiments on multiple GPU targets. For single reductions the generated code performs on par with highly tuned libraries, and for multiple reductions it significantly outperforms both libraries and OpenACC on all platforms.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [32 references]  Display  Hide  Download
Contributor : Albert Cohen <>
Submitted on : Sunday, January 29, 2017 - 5:32:10 PM
Last modification on : Thursday, February 7, 2019 - 3:49:40 PM
Document(s) archivé(s) le : Sunday, April 30, 2017 - 12:15:19 PM


Publisher files allowed on an open archive




Chandan Reddy, Michael Kruse, Albert Cohen. Reduction Drawing: Language Constructs and Polyhedral Compilation for Reductions on GPUs. PACT'16 - ACM/IEEE Conference on Parallel Architectures and Compilation Techniques, Sep 2016, Haifa, Israel. pp.87 - 97, ⟨10.1145/2967938.2967950⟩. ⟨hal-01425750⟩



Record views


Files downloads