A comparison of nested loops parallelization algorithms.

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