On the removal of anti- and output-dependences

Abstract : In this paper we build upon results of Padua and Wolfe, who introduced two graph transformations to break dependence paths including anti- and output-dependences. We first formalize these two transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial dependence paths involving anti- or output-dependences. The problem of finding the minimum number of statements to be transformed is shown to be NP-complete, and we propose two efficient heuristics.
Type de document :
Article dans une revue
International Journal of Parallel Programming, Springer Verlag, 1998, 26 (3), pp.285-312. 〈10.1023/A:1018790129478〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00856847
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 16:04:50
Dernière modification le : mardi 16 janvier 2018 - 15:50:51

Identifiants

Collections

Citation

Pierre-Yves Calland, Alain Darte, Yves Robert, Frédéric Vivien. On the removal of anti- and output-dependences. International Journal of Parallel Programming, Springer Verlag, 1998, 26 (3), pp.285-312. 〈10.1023/A:1018790129478〉. 〈hal-00856847〉

Partager

Métriques

Consultations de la notice

135