Data-reuse Optimizations for Pipelined Tiling with Parametric Tile Sizes

Optimisation de réutilisation des données pour le tuilage pipeliné avec tailles de tuiles paramétriques

Alexandre Isoard (1)

1 COMPSYS - Compilation and embedded computing systems

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 platforms with small memories. When hardware caches are not available, data transfers and local storage must be software-managed, and some useless external communications can be avoided by exploiting data reuse between tiles. An important parameter of loop 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 extended abstract 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. Combined with hierarchical tiling, this result opens new perspectives for the automatic generation, guided by parametric cost models, of blocking algorithms, 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.

Mots clés: pipelining; polyhedral analysis; accelerators; code generation; code transformation; compilers; cost models; fpga; data-reuse; gpu; optimization; parallel programming; parametric tiling

Domaines: Informatique

Alexandre Isoard. Data-reuse Optimizations for Pipelined Tiling with Parametric Tile Sizes. 23rd International Conference on Parallel Architectures and Compilation Techniques (PACT'14), Aug 2014, Edmonton, Canada. ⟨hal-01111393⟩