Scheduling divisible loads with return messages on heterogeneous master-worker platforms

Abstract : In this paper, we consider the problem of scheduling independent tasks, or divisible loads, onto an heterogeneous star platform, with both heterogeneous computing and communication resources. We consider the case where the workers, after processing the tasks, send back some results to the master processor. This corresponds to a more general framework than the one used in many divisible load papers, where only forward communications are taken into account. To the best of our knowledge, this paper constitutes the first attempt to derive optimality results under this general framework (forward and backward communications, heterogeneous processing and communication resources). We prove that it is possible to derive the optimal solution both for LIFO and FIFO distribution schemes. Nevertheless, the complexity of the general problem remains open: we also prove in the paper that the optimal distribution scheme may be neither LIFO nor FIFO.
Document type :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102504
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 1:54:37 PM
Last modification on : Friday, April 19, 2019 - 1:38:16 AM

File

RR2005-21.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102504, version 1

Collections

Citation

Olivier Beaumont, Loris Marchal, Yves Robert. Scheduling divisible loads with return messages on heterogeneous master-worker platforms. [Research Report] LIP RR-2005-21, Laboratoire de l'informatique du parallélisme. 2005, 2+19p. ⟨hal-02102504⟩

Share

Metrics

Record views

28

Files downloads

30