A comparison of nested loops parallelization algorithms. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

A comparison of nested loops parallelization algorithms.

Résumé

In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different representations of distance vectors as input. We identify the concepts that make them similar or different. We study the optimality of each with respect to the dependence analysis it uses. We propose well-chosen examples that illustrate the power and limitations of the three algorithms. This study permits to identify which algorithm is the most suitable for a given representation of dependences.
Dans ce rapport, nous comparons trois algorithmes de parallélisation automatique de boucles imbriquées (les algorithmes de Kennedy et Allen, de Wolf et Lam et de Darte et Vivien) qui utilisent des représentations différentes des vecteurs de distance. Nous identifions les concepts qui leur sont communs et ceux qui les différencient. Nous étudions l'optimalité de chacun des algorithmes par rapport à l'analyse de dépendance qu'il utilise. Nous illustrons sa puissance et ses limitations par des exemples bien choisis. Cette étude permet finalement d'identifier quel algorithme est le mieux adapté à une analyse de dépendance donnée.
Fichier principal
Vignette du fichier
RR1995-11.pdf (257.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02102085 , version 1

Citer

Alain Darte, Frédéric Vivien. A comparison of nested loops parallelization algorithms.. [Research Report] LIP RR-1995-11, Laboratoire de l'informatique du parallélisme. 1995, 2+18p. ⟨hal-02102085⟩
27 Consultations
348 Téléchargements

Partager

Gmail Facebook X LinkedIn More