Loop parallelization algorithms : from parallelism extraction to code generation. - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1997

Loop parallelization algorithms : from parallelism extraction to code generation.

Résumé

In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and their ability to incorporate various optimizing criteria such as maximal parallelism detection, detection of permutable loops , minimization of synchronizations, easiness of code generation, etc. We complete the discussion by presenting new results related to code generation and loop fusion for a particular class of multi-dimensional schedules, called shifted linear schedules. We demonstrate that algorithms based on such schedules, while generally considered as too complex, can indeed lead to simple codes.
Dans ce rapport, nous présentons divers algorithmes de parallélisation, en prenant en compte la représentation des dépendances qu'ils utilisent, les transformations de boucle qu'ils génèrent, les techniques de génération de code dont ils ont besoin, et enfin, leur capacité à incorporer divers critères d'optimisation tels que la détection du parallélisme maximal, la détection de boucles permutables, la minimisation des synchronisations, la simplicité de la génération de code, etc... Nous complétons notre discussion par la présentation de nouveaux résultats liés à la génération de code et à la fusion de boucles pour une classe particulière d'ordonnancements multi-dimensionnels appelés ordonnancements linéaires décalés. Nous montrons que des algorithmes qui se fondent sur de tels ordonnancements, souvent considérés comme trop complexes, peuvent néanmoins générer des codes simples.
Fichier principal
Vignette du fichier
RR1997-17.pdf (373.8 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02101883 , version 1

Citer

Pierre Boulet, Alain Darte, Georges-Andre Silber, Frédéric Vivien. Loop parallelization algorithms : from parallelism extraction to code generation.. [Research Report] LIP RR-1997-17, Laboratoire de l'informatique du parallélisme. 1997, 2+30p. ⟨hal-02101883⟩
36 Consultations
798 Téléchargements

Partager

More