Messages Scheduling for Data Redistribution between Clusters

Johanne Cohen 1 Emmanuel Jeannot 1 Nicolas Padoy
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 {\em $k$-Preemptive bipartite scheduling (KPBS)} is proven to be \mbox{NP}-Complete. Moreover we prove that approximating KPBS problem within a ratio number smaller that $\frac{4}{3}$ is impossible unless $P=\mbox{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.
Type de document :
Communication dans un congrès
Algorithms, models and tools for parallel computing on heterogeneous network - HeteroPar'03, workshop of SIAM PPAM 2003, Sep 2003, Czestochowa, Poland, 8 p, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099574
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:38:54
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099574, version 1

Collections

Citation

Johanne Cohen, Emmanuel Jeannot, Nicolas Padoy. Messages Scheduling for Data Redistribution between Clusters. Algorithms, models and tools for parallel computing on heterogeneous network - HeteroPar'03, workshop of SIAM PPAM 2003, Sep 2003, Czestochowa, Poland, 8 p, 2003. 〈inria-00099574〉

Partager

Métriques

Consultations de la notice

148