Exact and Approximated Data-Reuse Optimizations for Tiling with Parametric Sizes

Alain Darte 1 Alexandre Isoard 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Loop tiling is a loop transformation widely used to improve spatial and temporal data locality, to increase computation granularity, and to enable blocking algorithms, which are particularly useful when offloading kernels on computing units with smaller memories. When caches are not available or used, data transfers and local storage must be software-managed, and some useless remote communications can be avoided by exploiting data reuse between tiles. An important parameter of tiling is the sizes of the tiles, which impact the size of the required local memory. However, for most analyses involving several tiles, which is the case for inter-tile data reuse, the tile sizes induce non-linear constraints, unless they are numerical constants. This complicates or prevents a parametric analysis with polyhedral optimization techniques. This paper shows that, when tiles are executed in sequence along tile axes, the parametric (with respect to tile sizes) analysis for inter-tile data reuse is nevertheless possible, i.e., one can determine, at compile-time and in a parametric fashion, the copy-in and copy-out data sets for all tiles, with inter-tile reuse, as well as sizes for the induced local memories. When approximations of transfers are performed, the situation is much more complex, and involves a careful analysis to guarantee correctness when data are both read and written. We provide the mathematical foundations to make such approximations possible. Combined with hierarchical tiling, this result opens perspectives for the automatic generation of blocking algorithms, guided by parametric cost models, where blocks can be pipelined and/or can contain parallelism. Previous work on FPGAs and GPUs already showed the interest and feasibility of such automation with tiling, but in a non-parametric fashion.
Document type :
Reports
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-01103460
Contributor : Alain Darte <>
Submitted on : Wednesday, January 14, 2015 - 5:24:19 PM
Last modification on : Wednesday, November 20, 2019 - 3:01:56 AM
Long-term archiving on: Friday, September 11, 2015 - 6:47:46 AM

File

RR-8671.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01103460, version 1

Collections

Citation

Alain Darte, Alexandre Isoard. Exact and Approximated Data-Reuse Optimizations for Tiling with Parametric Sizes. [Research Report] RR-8671, LIP - ENS Lyon; CNRS; Inria; UCBL. 2015, pp.28. ⟨hal-01103460⟩

Share

Metrics

Record views

248

Files downloads

398