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, ENS Paris - École normale supérieure - Paris, 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.
Type de document :
Communication dans un congrès
PACT'16 - ACM/IEEE Conference on Parallel Architectures and Compilation Techniques, Sep 2016, Haifa, Israel. pp.87 - 97, 2016, 〈10.1145/2967938.2967950〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01425750
Contributeur : Albert Cohen <>
Soumis le : dimanche 29 janvier 2017 - 17:32:10
Dernière modification le : samedi 21 octobre 2017 - 20:10:13
Document(s) archivé(s) le : dimanche 30 avril 2017 - 12:15:19

Fichier

paper.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

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, 2016, 〈10.1145/2967938.2967950〉. 〈hal-01425750〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

33