Message Scheduling for Parallel Data Redistribution between Clusters
Identifieur interne : 003162 ( Hal/Corpus ); précédent : 003161; suivant : 003163Message Scheduling for Parallel Data Redistribution between Clusters
Auteurs : Johanne Cohen ; Emmanuel Jeannot ; Nicolas Padoy ; Frédéric WagnerSource :
- IEEE Transactions on Parallel and Distributed Systems [ 1045-9219 ] ; 2006.
English descriptors
- mix :
Abstract
We study the problem of redistributing data between clusters interconnected by a backbone. We suppose that at most k communications can be performed at the same time (the value of k depending on the characteristics of the platform). Given a set of messages, we aim at minimizing the total communication time assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k{\hbox{-}}Preemptive Bipartite Scheduling (KPBS) is proven to be NP-hard. We study its lower bound. We propose two {\frac{8}{3}}{\hbox{-}}{\rm{approximation}} algorithms with low complexity and fast heuristics. Simulation results show that both algorithms perform very well compared to the optimal solution and to the heuristics. Experimental results, based on an MPI implementation of these algorithms, show that both algorithms outperform a brute-force TCP-based solution, where no scheduling of the messages is performed.
Url:
DOI: 10.1109/TPDS.2006.141
Links to Exploration step
Hal:inria-00097208Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Message Scheduling for Parallel Data Redistribution between Clusters</title><author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name><affiliation><hal:affiliation 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><tutelles><tutelle name="UMR7503" 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><tutelle active="#struct-300009" type="direct"><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="direct"><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="direct"><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="direct"><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></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name><affiliation><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></affiliation></author><author><name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-82335" status="VALID"><orgName>Institut für Informatik</orgName><orgName type="acronym">LRR-TUM</orgName><desc><address><addrLine>Institut für Informatik Lehreinheit für Rechnertechnik und Rechnerorganisation / Parallelrechnerarchitektur - Technische Universität München (LRR-TUM) TU München Boltzmannstr. 3 D-85748 Garching bei München Germany</addrLine><country key="DE"></country></address><ref type="url">http://www.lrr.in.tum.de</ref></desc><listRelation><relation active="#struct-301140" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301140" type="direct"><org type="institution" xml:id="struct-301140" status="VALID"><orgName>Technische Universität München [München]</orgName><orgName type="acronym">TUM</orgName><desc><address><addrLine>Arcisstraße 21, 80333 München</addrLine><country key="DE"></country></address><ref type="url">http://www.tum.de/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Wagner, Frederic" sort="Wagner, Frederic" uniqKey="Wagner F" first="Frédéric" last="Wagner">Frédéric Wagner</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-100376" status="VALID"><orgName>Laboratoire Informatique d'Avignon</orgName><orgName type="acronym">LIA</orgName><desc><address><addrLine>339 Chemin des Meinajaries Agroparc BP 1228 84911 Avignon cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://lia.univ-avignon.fr/</ref></desc><listRelation><relation active="#struct-195507" type="direct"></relation><relation active="#struct-302221" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-195507" type="direct"><org type="institution" xml:id="struct-195507" status="VALID"><orgName>Université d'Avignon et des Pays de Vaucluse</orgName><orgName type="acronym">UAPV</orgName><desc><address><addrLine>74 rue Louis Pasteur - 84 029 Avignon cedex 1</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-avignon.fr/</ref></desc></org></tutelle><tutelle active="#struct-302221" type="direct"><org type="institution" xml:id="struct-302221" status="VALID"><orgName>Centre d'Enseignement et de Recherche en Informatique - CERI</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00097208</idno><idno type="halId">inria-00097208</idno><idno type="halUri">https://hal.inria.fr/inria-00097208</idno><idno type="url">https://hal.inria.fr/inria-00097208</idno><idno type="doi">10.1109/TPDS.2006.141</idno><date when="2006">2006</date><idno type="wicri:Area/Hal/Corpus">003162</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Message Scheduling for Parallel Data Redistribution between Clusters</title><author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name><affiliation><hal:affiliation 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><tutelles><tutelle name="UMR7503" 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><tutelle active="#struct-300009" type="direct"><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="direct"><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="direct"><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="direct"><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></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name><affiliation><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></affiliation></author><author><name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-82335" status="VALID"><orgName>Institut für Informatik</orgName><orgName type="acronym">LRR-TUM</orgName><desc><address><addrLine>Institut für Informatik Lehreinheit für Rechnertechnik und Rechnerorganisation / Parallelrechnerarchitektur - Technische Universität München (LRR-TUM) TU München Boltzmannstr. 3 D-85748 Garching bei München Germany</addrLine><country key="DE"></country></address><ref type="url">http://www.lrr.in.tum.de</ref></desc><listRelation><relation active="#struct-301140" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301140" type="direct"><org type="institution" xml:id="struct-301140" status="VALID"><orgName>Technische Universität München [München]</orgName><orgName type="acronym">TUM</orgName><desc><address><addrLine>Arcisstraße 21, 80333 München</addrLine><country key="DE"></country></address><ref type="url">http://www.tum.de/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Wagner, Frederic" sort="Wagner, Frederic" uniqKey="Wagner F" first="Frédéric" last="Wagner">Frédéric Wagner</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-100376" status="VALID"><orgName>Laboratoire Informatique d'Avignon</orgName><orgName type="acronym">LIA</orgName><desc><address><addrLine>339 Chemin des Meinajaries Agroparc BP 1228 84911 Avignon cedex 9</addrLine><country key="FR"></country></address><ref type="url">http://lia.univ-avignon.fr/</ref></desc><listRelation><relation active="#struct-195507" type="direct"></relation><relation active="#struct-302221" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-195507" type="direct"><org type="institution" xml:id="struct-195507" status="VALID"><orgName>Université d'Avignon et des Pays de Vaucluse</orgName><orgName type="acronym">UAPV</orgName><desc><address><addrLine>74 rue Louis Pasteur - 84 029 Avignon cedex 1</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-avignon.fr/</ref></desc></org></tutelle><tutelle active="#struct-302221" type="direct"><org type="institution" xml:id="struct-302221" status="VALID"><orgName>Centre d'Enseignement et de Recherche en Informatique - CERI</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic><idno type="DOI">10.1109/TPDS.2006.141</idno><series><title level="j">IEEE Transactions on Parallel and Distributed Systems</title><idno type="ISSN">1045-9219</idno><imprint><date type="datePub">2006</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Message scheduling</term><term>approximation algorithm</term><term>code coupling</term><term>data redistribution</term><term>grid computing</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study the problem of redistributing data between clusters interconnected by a backbone. We suppose that at most k communications can be performed at the same time (the value of k depending on the characteristics of the platform). Given a set of messages, we aim at minimizing the total communication time assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k{\hbox{-}}Preemptive Bipartite Scheduling (KPBS) is proven to be NP-hard. We study its lower bound. We propose two {\frac{8}{3}}{\hbox{-}}{\rm{approximation}} algorithms with low complexity and fast heuristics. Simulation results show that both algorithms perform very well compared to the optimal solution and to the heuristics. Experimental results, based on an MPI implementation of these algorithms, show that both algorithms outperform a brute-force TCP-based solution, where no scheduling of the messages is performed.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Message Scheduling for Parallel Data Redistribution between Clusters</title><author role="aut"><persName><forename type="first">Johanne</forename><surname>Cohen</surname></persName><email>Johanne.Cohen@loria.fr</email><idno type="idhal">johanne-cohen</idno><idno type="halauthor">92180</idno><affiliation ref="#struct-160"></affiliation></author><author role="aut"><persName><forename type="first">Emmanuel</forename><surname>Jeannot</surname></persName><email></email><idno type="halauthor">59340</idno><affiliation ref="#struct-2346"></affiliation></author><author role="aut"><persName><forename type="first">Nicolas</forename><surname>Padoy</surname></persName><email></email><idno type="halauthor">99705</idno><affiliation ref="#struct-82335"></affiliation></author><author role="aut"><persName><forename type="first">Frédéric</forename><surname>Wagner</surname></persName><email></email><idno type="halauthor">59341</idno><affiliation ref="#struct-100376"></affiliation></author><editor role="depositor"><persName><forename>Emmanuel</forename><surname>Jeannot</surname></persName><email>emmanuel.jeannot@inria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-09-21 11:13:50</date><date type="whenWritten">2006</date><date type="whenModified">2016-05-18 08:58:05</date><date type="whenReleased">2006-09-21 11:13:50</date><date type="whenProduced">2006</date></edition><respStmt><resp>contributor</resp><name key="103195"><persName><forename>Emmanuel</forename><surname>Jeannot</surname></persName><email>emmanuel.jeannot@inria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">inria-00097208</idno><idno type="halUri">https://hal.inria.fr/inria-00097208</idno><idno type="halBibtex">cohen:inria-00097208</idno><idno type="halRefHtml">IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2006, 17 (10), pp.1163-1175. <10.1109/TPDS.2006.141></idno><idno type="halRef">IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2006, 17 (10), pp.1163-1175. <10.1109/TPDS.2006.141></idno></publicationStmt><seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="UNIV-AVIGNON">Université d'Avignon</idno><idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="LORIA-NSS" p="LORIA">Réseaux, systèmes et services</idno><idno type="stamp" n="INRIA2">INRIA 2</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno></seriesStmt><notesStmt><note type="audience" n="2">International</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Message Scheduling for Parallel Data Redistribution between Clusters</title><author role="aut"><persName><forename type="first">Johanne</forename><surname>Cohen</surname></persName><email>Johanne.Cohen@loria.fr</email><idno type="idHal">johanne-cohen</idno><idno type="halAuthorId">92180</idno><affiliation ref="#struct-160"></affiliation></author><author role="aut"><persName><forename type="first">Emmanuel</forename><surname>Jeannot</surname></persName><idno type="halAuthorId">59340</idno><affiliation ref="#struct-2346"></affiliation></author><author role="aut"><persName><forename type="first">Nicolas</forename><surname>Padoy</surname></persName><idno type="halAuthorId">99705</idno><affiliation ref="#struct-82335"></affiliation></author><author role="aut"><persName><forename type="first">Frédéric</forename><surname>Wagner</surname></persName><idno type="halAuthorId">59341</idno><affiliation ref="#struct-100376"></affiliation></author></analytic><monogr><idno type="halJournalId" status="VALID">5389</idno><idno type="issn">1045-9219</idno><title level="j">IEEE Transactions on Parallel and Distributed Systems</title><imprint><publisher>Institute of Electrical and Electronics Engineers</publisher><biblScope unit="volume">17</biblScope><biblScope unit="issue">10</biblScope><biblScope unit="pp">1163-1175</biblScope><date type="datePub">2006</date></imprint></monogr><idno type="doi">10.1109/TPDS.2006.141</idno></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">Message scheduling</term><term xml:lang="en">data redistribution</term><term xml:lang="en">grid computing</term><term xml:lang="en">approximation algorithm</term><term xml:lang="en">code coupling</term></keywords><classCode scheme="halDomain" n="info.info-dc">Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]</classCode><classCode scheme="halTypology" n="ART">Journal articles</classCode></textClass><abstract xml:lang="en">We study the problem of redistributing data between clusters interconnected by a backbone. We suppose that at most k communications can be performed at the same time (the value of k depending on the characteristics of the platform). Given a set of messages, we aim at minimizing the total communication time assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k{\hbox{-}}Preemptive Bipartite Scheduling (KPBS) is proven to be NP-hard. We study its lower bound. We propose two {\frac{8}{3}}{\hbox{-}}{\rm{approximation}} algorithms with low complexity and fast heuristics. Simulation results show that both algorithms perform very well compared to the optimal solution and to the heuristics. Experimental results, based on an MPI implementation of these algorithms, show that both algorithms outperform a brute-force TCP-based solution, where no scheduling of the messages is performed.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003162 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 003162 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:inria-00097208
|texte= Message Scheduling for Parallel Data Redistribution between Clusters
}}
| This area was generated with Dilib version V0.6.33. |  |