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
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8671, LIP - ENS Lyon; CNRS; Inria; UCBL. 2015, pp.28
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01103460
Contributeur : Alain Darte <>
Soumis le : mercredi 14 janvier 2015 - 17:24:19
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 06:47:46

Fichier

RR-8671.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

282