Skip to Main content Skip to Navigation
Conference papers

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.
Keywords : algorithmes inaproximability algorithm redistribution np-complete np-complet inapproximation
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/inria-00099574
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:38:54 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

Identifiers

  • HAL Id : inria-00099574, version 1

Collections

INRIA | CNRS | LORIA | UNIV-LORRAINE

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. ⟨inria-00099574⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

179

 

Contact                    Legal Notice                    Personal Data