Optimization Space Pruning without Regrets

Ulysse Beaugnon 1, 2 Antoine Pouille 1, 2 Marc Pouzet 1, 2 Jacques Pienaar 3 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 : Many computationally-intensive algorithms benefit from the wide parallelism offered by Graphical Processing Units (GPUs). However , the search for a close-to-optimal implementation remains extremely tedious due to the specialization and complexity of GPU architectures. We present a novel approach to automatically discover the best performing code from a given set of possible implementations. It involves a branch and bound algorithm with two distinctive features: (1) an analytic performance model of a lower bound on the execution time, and (2) the ability to estimate such bounds on a partially-specified implementation. The unique features of this performance model allow to aggressively prune the optimization space without eliminating the best performing implementation. While the space considered in this paper focuses on GPUs, the approach is generic enough to be applied to other architectures. We implemented our algorithm in a tool called Telamon and demonstrate its effectiveness on a huge, architecture-specific and input-sensitive optimization space. The information provided by the performance model also helps to identify ways to enrich the search space to consider better candidates, or to highlight architectural bottlenecks.
Type de document :
Communication dans un congrès
CC 2017 - 26th International Conference on Compiler Construction, Feb 2017, Austin, TX, United States. ACM Press, Compiler Construction 2017, pp.34-44, 2017, Proceedings of the International Conference on Compiler Construction. 〈https://conf.researchr.org/home/CC-2017〉. 〈10.1145/3033019.3033023〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01655602
Contributeur : Timothy Bourke <>
Soumis le : mardi 5 décembre 2017 - 19:55:22
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Fichier

Identifiants

Collections

Citation

Ulysse Beaugnon, Antoine Pouille, Marc Pouzet, Jacques Pienaar, Albert Cohen. Optimization Space Pruning without Regrets. CC 2017 - 26th International Conference on Compiler Construction, Feb 2017, Austin, TX, United States. ACM Press, Compiler Construction 2017, pp.34-44, 2017, Proceedings of the International Conference on Compiler Construction. 〈https://conf.researchr.org/home/CC-2017〉. 〈10.1145/3033019.3033023〉. 〈hal-01655602〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

100