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

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.Le tuilage de boucles (''loop tiling'') est une transformation de code largement utilisée pour améliorer la localité spatiale et temporelle des données, augmenter la granularité des calculs, et générer des algorithmes par blocs, particulièrement utiles pour déporter des portions de code sur des unités de calcul à petite mémoire. En l'absence de mécanisme automatique de cache, les transferts de données et le stockage local doivent être gérés au niveau logiciel, et certaines de ces communications peuvent être évitées en réutilisant des données entre tuiles. Un paramètre important du tuilage est la taille des tuiles qui influe sur la taille de la mémoire locale requise. Mais, pour la plupart des analyses impliquant plusieurs tuiles, ce qui est le cas pour la réutilisation des données entre tuiles, ces tailles de tuiles induisent des contraintes non-linéaires, sauf si ce sont des constantes numériques. Ceci complique ou empêche une analyse paramétrique par des techniques polyédriques.Ce rapport montre que, lorsque les tuiles sont exécutées en séquence le long des axes des tuiles, l'analyse paramétrique (au sens des tailles de tuiles), pour la réutilisation des données entre tuiles, est néanmoins possible, c'est-à-dire qu'on peut déterminer, de façon statique et paramétrique, les ensembles de données entrantes et sortantes pour chaque tuile, avec réutilisation entre tuiles, ainsi que des tailles pour les mémoires locales induites. Lorsque des approximations des transferts sont faites, la situation devient plus complexe, et requiert une analyse attentive pour garantir la correction de la transformation dans le cas où des données peuvent être à la fois lues et écrites. Nous apportons des éléments de base théoriques pour rendre de telles approximations possibles. Combinés avec du tuilage hiérarchique, ces résultats ouvrent des perspectives pour la génération automatique d'algorithmes par blocs, guidée par des modèles de coût paramétriques, où les blocs peuvent être pipelinées ou contenir du parallélisme. Des travaux antérieurs pour FPGA et GPU ont déjà montré l'intérêt et la faisabilité d'une telle automatisation par tuilage, mais de façon non-paramétrique