On the Removal of Anti and Output Dependences

Pierre-Yves Calland; Alain Darte; Yves Robert; Frédéric Vivien

inria-00073890, version 1

On the Removal of Anti and Output Dependences

Pierre-Yves Calland ¹, Alain Darte ()^a^, 1, Yves Robert^b^, 1, Frédéric Vivien ¹

N° RR-2800 (1996)

Résumé : 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.

a – CNRS
b – Ecole Normale Supérieure de Lyon - ENS Lyon
1 : REMAP (INRIA Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
INRIA – École Normale Supérieure - Lyon – CNRS : UMR5668 – LIP

inria-00073890, version 1
http://hal.inria.fr/inria-00073890
oai:hal.inria.fr:inria-00073890
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mercredi 24 Mai 2006, 14:00:09
Dernière modification le : Jeudi 2 Octobre 2008, 16:28:38

Voir la fiche détaillée

Documents associés

PS :

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00073890"><monogr>
<author><persName><forename>Pierre-Yves</forename><surname>Calland</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="team">REMAP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">LIP</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Darte</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="team">REMAP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">LIP</orgName>
</affiliation>
</author>
<author><persName><forename>Yves</forename><surname>Robert</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="team">REMAP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">LIP</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Vivien</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="team">REMAP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">LIP</orgName>
</affiliation>
</author>
<title type="main" level="m">On the Removal of Anti and Output Dependences</title><title type="main" level="m">On the Removal of Anti and Output Dependences</title><imprint><biblScope type="publicationDate">1996-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00073890</idno><idno type="HALFile">http://hal.inria.fr/inria-00073890/PDF/RR-2800.pdf</idno></biblStruct>
</listBibl>
</listBibl>