On the Optimality of Allen and Kennedy's Algorithm for Parallelism Extraction in Nested Loops

Alain Darte 1, * Frédéric Vivien 1
* Auteur correspondant
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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.
Type de document :
Article dans une revue
Journal of Parallel Algorithms and Applications, Taylor & Francis, 1997, 12 (1-3), pp.83-112. 〈10.1080/01495739708941417〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00856887
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 16:19:09
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Identifiants

Collections

Citation

Alain Darte, Frédéric Vivien. On the Optimality of Allen and Kennedy's Algorithm for Parallelism Extraction in Nested Loops. Journal of Parallel Algorithms and Applications, Taylor & Francis, 1997, 12 (1-3), pp.83-112. 〈10.1080/01495739708941417〉. 〈hal-00856887〉

Partager

Métriques

Consultations de la notice

135