Skip to Main content Skip to Navigation
Journal articles

Monoparametric Tiling of Polyhedral Programs

Guillaume Iooss 1 Christophe Alias 2 Sanjay Rajopadhye 3 
1 CORSE - Compiler Optimization and Run-time Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 CASH - CASH - Compilation and Analysis, Software and Hardware
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Tiling is a crucial program transformation, adjusting the ops-to-bytes balance of codes to improve locality. Like parallelism, it 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 perform fixed size tiling, or apply parametric tiling in only the final, code generation step. We introduce monoparametric tiling, a restricted parametric tiling transformation. We show that, despite being parametric, it retains the closure properties of the polyhedral model. We first prove that applying monoparametric partitioning (i) to a polyhedron yields a union of polyhedra with modulo conditions, and (ii) to an affine function produces a piecewise-affine function with modulo conditions. We then use these properties to show how to tile an entire polyhedral program. Our monoparametric tiling is general enough to handle tiles with arbitrary tile shapes that can tessellate the iteration space (e.g., hexagonal, trapezoidal, etc). This enables a wide range of polyhedral analyses and transformations to be applied.
Complete list of metadata
Contributor : Guillaume Iooss Connect in order to contact the contributor
Submitted on : Sunday, January 3, 2021 - 7:15:08 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM


Files produced by the author(s)



Guillaume Iooss, Christophe Alias, Sanjay Rajopadhye. Monoparametric Tiling of Polyhedral Programs. International Journal of Parallel Programming, Springer Verlag, 2021, 49, pp.376-409. ⟨10.1007/s10766-021-00694-2⟩. ⟨hal-02493164v2⟩



Record views


Files downloads