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.
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download
Contributor : Christophe Alias <>
Submitted on : Thursday, October 22, 2015 - 5:01:42 PM
Last modification on : Friday, April 20, 2018 - 3:44:27 PM
Long-term archiving on : Thursday, April 27, 2017 - 2:32:10 PM


Files produced by the author(s)


  • HAL Id : hal-01219452, version 1



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⟩



Record views


Files downloads