Mono-parametric Tiling is a Polyhedral Transformation

Guillaume Iooss 1, 2, 3 Sanjay Rajopadhye 3 Christophe Alias 4, 1 Yun Zou 3
2 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Tiling is a crucial program transformation with many benefits: it improves locality, exposes parallelism, allows for adjusting the ops-to-bytes balance of codes, and can be applied at multiple levels. Allowing tile sizes to be symbolic parameters at compile time has many benefits, including efficient autotuning, and run-time adaptability to system variations. For polyhedral programs, parametric tiling in its full generality is known to be non-linear, breaking the mathematical closure properties of the polyhedral model. Most compilation tools therefore either avoid it by only performing fixed size tiling, or apply it in only the final, code generation step. Both strategies have limitations. We first introduce mono-parametric partitioning, a restricted parametric, tiling-like transformation which can be used to express a tiling. We show that, despite being parametric, it is a polyhedral transformation. We first prove that applying mono-parametric partitioning (i) to a polyhedron yields a union of polyhedra, and (ii) to an affine function produces a piecewise-affine function. We then use these properties to show how to partition an entire polyhedral program, including one with reductions. Next, we generalize this transformation to tiles with arbitrary tile shapes that can tesselate the iteration space (e.g., hexagonal, trapezoidal, etc). We show how mono-parametric tiling can be applied at multiple levels, and enables a wide range of polyhedral analysis and transformations to be applied.
Type de document :
Rapport
[Research Report] RR-8802, INRIA Grenoble - Rhône-Alpes; CNRS. 2015, pp.40
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01219452
Contributeur : Christophe Alias <>
Soumis le : jeudi 22 octobre 2015 - 17:01:42
Dernière modification le : mardi 16 janvier 2018 - 15:35:13
Document(s) archivé(s) le : jeudi 27 avril 2017 - 14:32:10

Fichier

RR-8802.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01219452, version 1

Collections

Citation

Guillaume Iooss, Sanjay Rajopadhye, Christophe Alias, Yun Zou. Mono-parametric Tiling is a Polyhedral Transformation. [Research Report] RR-8802, INRIA Grenoble - Rhône-Alpes; CNRS. 2015, pp.40. 〈hal-01219452〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

308