On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1996

On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops

Résumé

We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.
Nous étudions les relations entre représentations des dépendances et extraction maximale du parallélisme dans les nids de boucles. Nous recherchons, pour chaque représentation des dépendances, la plus petite transformation capable d'extraire le maximum de parallélisme. Nous prouvons dans cet article que l'algorithme d'Allen et Kennedy est optimal quand les dépendances sont approximées par des niveaux de dépendance: aucun algorithme, aussi sophistiqué soit-il, ne peut détecter plus de parallélisme que l'algorithme d'Allen et Kennedy, si la seule information disponible sur les dépendances est le niveau de la dépendance. Autrement dit, la distribution de boucles suffit à détecter le maximum de parallélisme dans les graphes de dépendance étiquetés par niveaux.
Fichier principal
Vignette du fichier
RR1996-05.pdf (406.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02101988 , version 1

Citer

Alain Darte, Frédéric Vivien. On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. [Research Report] LIP RR-1996-05, Laboratoire de l'informatique du parallélisme. 1996, 2+34p. ⟨hal-02101988⟩
47 Consultations
376 Téléchargements

Partager

Gmail Facebook X LinkedIn More