Splitting Polyhedra to Generate More Efficient Code: Efficient Code Generation in the Polyhedral Model is Harder Than We Thought

Harenome Razanajato 1, 2 Vincent Loechner 1, 2 Cédric Bastoul 1, 2
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : Code generation in the polyhedral model takes as input a union of Z-polyhedra and produces code scanning all of them. Modern code generation tools are heavily relying on polyhedral operations to perform this task. However, these operations are typically provided by general-purpose poly- hedral libraries that are not specifically designed to address the code generation problem. In particular, (unions of) poly- hedra may be represented in various mathematically equiv- alent ways which may have different properties with respect to code generation. In this paper, we investigate this prob- lem and try to find the best representation of polyhedra to generate efficient code. We present two contributions. First we demonstrate that this problem has been largely under-estimated, showing sig- nificant control overhead deviations when using different representations of the same polyhedra. Second, we propose an improvement to the main algorithm of the state-of-the-art code generation tool CLooG. It generates code with fewer tests in the inner loops, and aims to reduce control overhead and to simplify vectorization for the compiler, at the cost of a larger code size. It is based on a smart splitting of the union of polyhedra while recursing on the dimensions. We implemented our algorithm in CLooG/PolyLib, and com- pared the performance and size of the generated code to the CLooG/isl version.
Type de document :
Communication dans un congrès
IMPACT 2017, 7th International Workshop on Polyhedral Compilation Techniques, Jan 2017, Stockholm, Sweden. 2017, 〈http://impact.gforge.inria.fr/impact2017/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01505764
Contributeur : Vincent Loechner <>
Soumis le : vendredi 14 avril 2017 - 15:22:36
Dernière modification le : jeudi 15 juin 2017 - 09:09:26
Document(s) archivé(s) le : samedi 15 juillet 2017 - 15:44:37

Fichier

impact-17-splitting-polyhedra-...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01505764, version 1

Collections

Citation

Harenome Razanajato, Vincent Loechner, Cédric Bastoul. Splitting Polyhedra to Generate More Efficient Code: Efficient Code Generation in the Polyhedral Model is Harder Than We Thought. IMPACT 2017, 7th International Workshop on Polyhedral Compilation Techniques, Jan 2017, Stockholm, Sweden. 2017, 〈http://impact.gforge.inria.fr/impact2017/〉. 〈hal-01505764〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

36