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.
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
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〉
