Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms
Identifieur interne : 004278 ( Main/Merge ); précédent : 004277; suivant : 004279Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms
Auteurs : Pierre-Francois Dutot [France] ; Tchimou N'Takpé [France] ; Frédéric Suter [France] ; Henri Casanova [États-Unis]Source :
- IEEE Transactions on Parallel and Distributed Systems [ 1045-9219 ] ; 2008.
English descriptors
- mix :
Abstract
Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and in practice, i.e., pragmatic heuristics. Due to task parallelism these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are non-guaranteed heuristics. In this paper we develop a scheduling algorithm, MCGAS, which is applicable to multi-cluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multi-cluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed non-guaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.
Url:
DOI: 10.1109/TPDS.2009.11
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 004379
- to stream Hal, to step Curation: 004379
- to stream Hal, to step Checkpoint: 003554
Links to Exploration step
Hal:inria-00347273Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms</title><author><name sortKey="Dutot, Pierre Francois" sort="Dutot, Pierre Francois" uniqKey="Dutot P" first="Pierre-Francois" last="Dutot">Pierre-Francois Dutot</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-24471" status="VALID"><orgName>Laboratoire d'Informatique de Grenoble</orgName><orgName type="acronym">LIG</orgName><desc><address><addrLine>UMR 5217 - Laboratoire LIG - 38041 Grenoble cedex 9 - France Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85</addrLine><country key="FR"></country></address><ref type="url">http://www.liglab.fr/</ref></desc><listRelation><relation active="#struct-3886" type="direct"></relation><relation active="#struct-51016" type="direct"></relation><relation active="#struct-300275" type="direct"></relation><relation name="UMR5217" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-3886" type="direct"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName><orgName type="acronym">Grenoble 2 UPMF</orgName><date type="end">2015-12-31</date><desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://www.upmf-grenoble.fr/</ref></desc></org></tutelle><tutelle active="#struct-51016" type="direct"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName><orgName type="acronym">UJF</orgName><date type="end">2015-12-31</date><desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://www.ujf-grenoble.fr/</ref></desc></org></tutelle><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR5217" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Grenoble</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Pierre-Mendès-France</orgName><orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName><placeName><settlement type="city">Grenoble</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Joseph Fourier</orgName><orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName></affiliation></author><author><name sortKey="N Takpe, Tchimou" sort="N Takpe, Tchimou" uniqKey="N Takpe T" first="Tchimou" last="N'Takpé">Tchimou N'Takpé</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2346" status="OLD"><idno type="RNSR">200718299P</idno><orgName>Algorithms for the Grid</orgName><orgName type="acronym">ALGORILLE</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Suter, Frederic" sort="Suter, Frederic" uniqKey="Suter F" first="Frédéric" last="Suter">Frédéric Suter</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2346" status="OLD"><idno type="RNSR">200718299P</idno><orgName>Algorithms for the Grid</orgName><orgName type="acronym">ALGORILLE</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Casanova, Henri" sort="Casanova, Henri" uniqKey="Casanova H" first="Henri" last="Casanova">Henri Casanova</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-51654" status="VALID"><orgName>Information and Computer Sciences [Hawaii]</orgName><orgName type="acronym">ICS</orgName><desc><address><addrLine>Pacific Ocean Science and Technology (POST) Building, Room 317 1680 East-West Road Honolulu, HI 96822</addrLine><country key="US"></country></address><ref type="url">http://www.ics.hawaii.edu/</ref></desc><listRelation><relation active="#struct-301238" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301238" type="direct"><org type="institution" xml:id="struct-301238" status="VALID"><orgName>University of Hawaii at Manoa</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00347273</idno><idno type="halId">inria-00347273</idno><idno type="halUri">https://hal.inria.fr/inria-00347273</idno><idno type="url">https://hal.inria.fr/inria-00347273</idno><idno type="doi">10.1109/TPDS.2009.11</idno><date when="2008">2008</date><idno type="wicri:Area/Hal/Corpus">004379</idno><idno type="wicri:Area/Hal/Curation">004379</idno><idno type="wicri:Area/Hal/Checkpoint">003554</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003554</idno><idno type="wicri:doubleKey">1045-9219:2008:Dutot P:scheduling:parallel:task</idno><idno type="wicri:Area/Main/Merge">004278</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms</title><author><name sortKey="Dutot, Pierre Francois" sort="Dutot, Pierre Francois" uniqKey="Dutot P" first="Pierre-Francois" last="Dutot">Pierre-Francois Dutot</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-24471" status="VALID"><orgName>Laboratoire d'Informatique de Grenoble</orgName><orgName type="acronym">LIG</orgName><desc><address><addrLine>UMR 5217 - Laboratoire LIG - 38041 Grenoble cedex 9 - France Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85</addrLine><country key="FR"></country></address><ref type="url">http://www.liglab.fr/</ref></desc><listRelation><relation active="#struct-3886" type="direct"></relation><relation active="#struct-51016" type="direct"></relation><relation active="#struct-300275" type="direct"></relation><relation name="UMR5217" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-3886" type="direct"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName><orgName type="acronym">Grenoble 2 UPMF</orgName><date type="end">2015-12-31</date><desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://www.upmf-grenoble.fr/</ref></desc></org></tutelle><tutelle active="#struct-51016" type="direct"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName><orgName type="acronym">UJF</orgName><date type="end">2015-12-31</date><desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://www.ujf-grenoble.fr/</ref></desc></org></tutelle><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR5217" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Grenoble</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Pierre-Mendès-France</orgName><orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName><placeName><settlement type="city">Grenoble</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Joseph Fourier</orgName><orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName></affiliation></author><author><name sortKey="N Takpe, Tchimou" sort="N Takpe, Tchimou" uniqKey="N Takpe T" first="Tchimou" last="N'Takpé">Tchimou N'Takpé</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2346" status="OLD"><idno type="RNSR">200718299P</idno><orgName>Algorithms for the Grid</orgName><orgName type="acronym">ALGORILLE</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Suter, Frederic" sort="Suter, Frederic" uniqKey="Suter F" first="Frédéric" last="Suter">Frédéric Suter</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2346" status="OLD"><idno type="RNSR">200718299P</idno><orgName>Algorithms for the Grid</orgName><orgName type="acronym">ALGORILLE</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Casanova, Henri" sort="Casanova, Henri" uniqKey="Casanova H" first="Henri" last="Casanova">Henri Casanova</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-51654" status="VALID"><orgName>Information and Computer Sciences [Hawaii]</orgName><orgName type="acronym">ICS</orgName><desc><address><addrLine>Pacific Ocean Science and Technology (POST) Building, Room 317 1680 East-West Road Honolulu, HI 96822</addrLine><country key="US"></country></address><ref type="url">http://www.ics.hawaii.edu/</ref></desc><listRelation><relation active="#struct-301238" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301238" type="direct"><org type="institution" xml:id="struct-301238" status="VALID"><orgName>University of Hawaii at Manoa</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author></analytic><idno type="DOI">10.1109/TPDS.2009.11</idno><series><title level="j">IEEE Transactions on Parallel and Distributed Systems</title><idno type="ISSN">1045-9219</idno><imprint><date type="datePub">2008</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>ixed parallelism</term><term>multi-cluster platform M</term><term>multi-cluster platform ixed parallelism</term><term>parallel task graph scheduling</term><term>performance guarantee</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and in practice, i.e., pragmatic heuristics. Due to task parallelism these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are non-guaranteed heuristics. In this paper we develop a scheduling algorithm, MCGAS, which is applicable to multi-cluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multi-cluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed non-guaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004278 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 004278 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Hal:inria-00347273
|texte= Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms
}}
| This area was generated with Dilib version V0.6.33. |  |