Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs

Alain Darte 1 Frédéric Vivien 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper presents an optimal algorithm for detecting line or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, this algorithm is optimal for the classical approximation by direction sectors. This result generalizes, to the case of several statements. Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations. It can also be viewed as a combination of both Allen and Kennedy's algorithm and Wolf and Lam's algorithm.
Type de document :
Article dans une revue
International Journal of Parallel Programming, Springer Verlag, 1997, 25 (6), pp.447--496. 〈10.1023/A:1025168022993〉
Liste complète des métadonnées

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

Lien texte intégral

Identifiants

Collections

Citation

Alain Darte, Frédéric Vivien. Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. International Journal of Parallel Programming, Springer Verlag, 1997, 25 (6), pp.447--496. 〈10.1023/A:1025168022993〉. 〈hal-00856886〉

Partager

Métriques

Consultations de la notice

121