InforLorV4, Main, Exploration, bibRecordById, Pascal:04-0280482

Messages Scheduling for Data Redistribution between Clusters

Identifieur interne : 006B71 ( Main/Exploration ); précédent : 006B70; suivant : 006B72

Messages Scheduling for Data Redistribution between Clusters

Auteurs : Johanne Cohen [France] ; Emmanuel Jeannot [France] ; Nicolas Padoy [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:C4FA7996F58BD4FBBFF37EEACFAE0111E3AFDB7A

Descripteurs français

Pascal (Inist)
- Algorithme approximation, Borne inférieure, Complétude, Machine parallèle, Mémoire répartie, Méthode heuristique, Ordonnancement, Préemption, Réseau fédérateur, Système réparti.

English descriptors

KwdEn :
- Approximation algorithm, Backbone, Completeness, Distributed memory, Distributed system, Heuristic method, Lower bound, Parallel machines, Preemption, Scheduling.

Abstract

Abstract: In this paper we study the general problem of parallel data redistribution over a network. Given a set of communications between two parallel machines interconnected by a backbone, we wish to minimize the total time required for the completion of all communications assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k-Preemptive bipartite scheduling (KPBS) is proven to be NP-Complete. Moreover we prove that approximating KPBS problem within a ratio number smaller that $\frac{4}{3}$ is impossible unless P=NP. In spite of this negative result, we study a lower bound on the cost of KPBS problem in terms of its parameters, and we propose an approximation algorithm with ratio 2 and fast heuristics.

Url:

https://api.istex.fr/ark:/67375/HCB-85Z2C83B-S/fulltext.pdf

DOI: 10.1007/978-3-540-24669-5_116

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Messages Scheduling for Data Redistribution between Clusters</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
</author>
<author><name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name>
</author>
<author><name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:C4FA7996F58BD4FBBFF37EEACFAE0111E3AFDB7A</idno>
<date when="2004" year="2004">2004</date>
<idno type="doi">10.1007/978-3-540-24669-5_116</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-85Z2C83B-S/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002E75</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002E75</idno>
<idno type="wicri:Area/Istex/Curation">002E37</idno>
<idno type="wicri:Area/Istex/Checkpoint">001780</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001780</idno>
<idno type="wicri:doubleKey">0302-9743:2004:Cohen J:messages:scheduling:for</idno>
<idno type="wicri:Area/Main/Merge">006E75</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:04-0280482</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000676</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000365</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000592</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000592</idno>
<idno type="wicri:doubleKey">0302-9743:2004:Cohen J:messages:scheduling:for</idno>
<idno type="wicri:Area/Main/Merge">007027</idno>
<idno type="wicri:Area/Main/Curation">006B71</idno>
<idno type="wicri:Area/Main/Exploration">006B71</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Messages Scheduling for Data Redistribution between Clusters</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CNRS LORIA, Vandœuvre les Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
<settlement type="city" wicri:auto="agglo">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA, Université H. Poincaré, Vandœuvre les Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
<settlement type="city" wicri:auto="agglo">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>École Normale Supérieure de Lyon</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Backbone</term>
<term>Completeness</term>
<term>Distributed memory</term>
<term>Distributed system</term>
<term>Heuristic method</term>
<term>Lower bound</term>
<term>Parallel machines</term>
<term>Preemption</term>
<term>Scheduling</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme approximation</term>
<term>Borne inférieure</term>
<term>Complétude</term>
<term>Machine parallèle</term>
<term>Mémoire répartie</term>
<term>Méthode heuristique</term>
<term>Ordonnancement</term>
<term>Préemption</term>
<term>Réseau fédérateur</term>
<term>Système réparti</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: In this paper we study the general problem of parallel data redistribution over a network. Given a set of communications between two parallel machines interconnected by a backbone, we wish to minimize the total time required for the completion of all communications assuming that communications can be preempted and that preemption comes with an extra cost. Our problem, called k-Preemptive bipartite scheduling (KPBS) is proven to be NP-Complete. Moreover we prove that approximating KPBS problem within a ratio number smaller that $\frac{4}{3}$ is impossible unless P=NP. In spite of this negative result, we study a lower bound on the cost of KPBS problem in terms of its parameters, and we propose an approximation algorithm with ratio 2 and fast heuristics.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Nancy</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
</region>
<name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name>
<name sortKey="Jeannot, Emmanuel" sort="Jeannot, Emmanuel" uniqKey="Jeannot E" first="Emmanuel" last="Jeannot">Emmanuel Jeannot</name>
<name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name>
<name sortKey="Padoy, Nicolas" sort="Padoy, Nicolas" uniqKey="Padoy N" first="Nicolas" last="Padoy">Nicolas Padoy</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006B71 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006B71 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:C4FA7996F58BD4FBBFF37EEACFAE0111E3AFDB7A
   |texte=   Messages Scheduling for Data Redistribution between Clusters
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Messages Scheduling for Data Redistribution between Clusters

Messages Scheduling for Data Redistribution between Clusters

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.