On the Removal of Anti and Output Dependences

Pierre-Yves Calland 1 Alain Darte 1 Yves Robert 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 : In this paper we build upon results of Padua and Wolfe~\cite{PaduaWo86}, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial cycles involving anti or output dependences. The problem of finding the mininum number of statements to be transformed is shown to be NP-complete in the strong sense, and we propose two efficient heuristics.
Type de document :
Rapport
[Research Report] RR-2800, INRIA. 1996
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00073890
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:00:09
Dernière modification le : mardi 16 janvier 2018 - 15:43:11
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:01:05

Fichiers

Identifiants

  • HAL Id : inria-00073890, version 1

Collections

Citation

Pierre-Yves Calland, Alain Darte, Yves Robert, Frédéric Vivien. On the Removal of Anti and Output Dependences. [Research Report] RR-2800, INRIA. 1996. 〈inria-00073890〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

145