On the complexity of loop fusion - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1998

On the complexity of loop fusion

Résumé

Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this report is to study, from a theoretical point of view, several variants of the loop fusion problem -- identifying polynomially solvable cases and NP-complete cases -- and to make the link between these problems and some scheduling problems that arise from completely different areas. We study, among others, the fusion of loops of different types, and the fusion of loops when combined with loop shifting.
La fusion de boucles est une transformation de programme qui combine plusieurs boucles en une seule. Elle est utilisée dans les compilateurs-paralléliseurs, principalement pour augmenter la granularité des boucles et pour améliorer la réutilisation des données. Le but de ce rapport est d'étudier d'un point de vue théorique plusieurs variantes du problème de fusion de boucles -- en identifiant les cas solubles en temps polynomial et les cas NP-complets -- et d'établir le lien entre ces problèmes et quelques problèmes d'ordonnancement provenant de domaines complètement différents. Nous étudions notamment le problème de la fusion de boucles typées ainsi que le problème de la fusion de boucles avec décalage.
Fichier principal
Vignette du fichier
RR1998-50.pdf (262.33 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101854 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101854 , version 1

Citer

Alain Darte. On the complexity of loop fusion. [Research Report] LIP RR-1998-50, Laboratoire de l'informatique du parallélisme. 1998, 2+17p. ⟨hal-02101854⟩
32 Consultations
96 Téléchargements

Partager

More