A New Guaranteed Heuristic for the Software Pipelining Problem

Pierre-Yves Calland; Alain Darte; Yves Robert

inria-00073933, version 1

A New Guaranteed Heuristic for the Software Pipelining Problem

Pierre-Yves Calland ¹, Alain Darte ()^a^, 1, Yves Robert^b^, 1

N° RR-2759 (1995)

Résumé : We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing its deep link with the circuit retiming problem. Also, in the single resource class case, our new heuristic is guaranteed, with a better bound than that of~\cite{GasperoniSc94}. Finally, we point out that, in its simplest form, our algorithm has a lower complexity.

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-00073933, version 1
http://hal.inria.fr/inria-00073933
oai:hal.inria.fr:inria-00073933
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mercredi 24 Mai 2006, 14:07:06
Dernière modification le : Jeudi 2 Octobre 2008, 15:50:53

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-00073933"><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>
<title type="main" level="m">A New Guaranteed Heuristic for the Software Pipelining Problem</title><title type="main" level="m">A New Guaranteed Heuristic for the Software Pipelining Problem</title><imprint><biblScope type="publicationDate">1995-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00073933</idno><idno type="HALFile">http://hal.inria.fr/inria-00073933/PDF/RR-2759.pdf</idno></biblStruct>
</listBibl>
</listBibl>