Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms

Olivier Beaumont; Pierre Ramet; Jean Roman

inria-00346587, version 1

Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms

Olivier Beaumont () ^1, 2, Pierre Ramet () ^1, 3, Jean Roman () ^3, 4

Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar 3019 (2003) 880--887

Résumé : In this paper, we focus on the scheduling of Laplace task graph on a general platform where both communication links and processing units are heterogeneous. In this context, it is known that deriving optimal algorithm, in the sense of makespan minimization, is NP-Complete, and several inapproximation results have been proved. Nevertheless, we provide an asymtotically optimal algorithm in this general context. Moreover, we expect that this methodolgy can be extended to more general task graphs, especially for nested loops where the inner-most loop is parallel.

1 : Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
2 : CEPAGE (INRIA Bordeaux - Sud-Ouest)
INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
3 : SCALAPPLIX (INRIA Bordeaux - Sud-Ouest)
INRIA – CNRS : UMR5466 – Université Sciences et Technologies - Bordeaux I – Université Victor Segalen - Bordeaux II – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
4 : SCALAPPLIX (INRIA Futurs)
INRIA – CNRS : UMR5466 – Université Sciences et Technologies - Bordeaux I – Université Victor Segalen - Bordeaux II – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

inria-00346587, version 1
http://hal.inria.fr/inria-00346587
oai:hal.inria.fr:inria-00346587
Contributeur : Pierre Ramet <>
Soumis le : Jeudi 11 Décembre 2008, 18:33:27
Dernière modification le : Lundi 15 Décembre 2008, 14:26:37

Voir la fiche détaillée

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="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00346587"><analytic>
<author><persName><forename>Olivier</forename><surname>Beaumont</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">CEPAGE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
</author>
<author><persName><forename>Pierre</forename><surname>Ramet</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">SCALAPPLIX</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5466</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
</author>
<author><persName><forename>Jean</forename><surname>Roman</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">SCALAPPLIX</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5466</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">SCALAPPLIX</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5466</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
</author>
<title type="main" level="a">Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms</title></analytic><monogr><meeting>Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar</meeting><imprint><publisher>Springer Verlag</publisher><pubPlace><settlement>Czestochowa</settlement><country>Pologne</country></pubPlace><biblScope type="publicationDate">2003-00-00</biblScope><biblScope type="vol">3019</biblScope><biblScope type="pp">880--887</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00346587</idno></biblStruct>
</listBibl>
</listBibl>