A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs

Abstract : In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous processor farm. The master processor and the p slaves have different computation and communication capabilities. We assume communication-computation overlap for each slave (and for the master), but the communication medium is exclusive: the master can only communicate with a single slave at each time-step. We give a polynomial-time algorithm to solve the following scheduling problem: given a time-bound T, what is the maximal number of tasks that can be processed by the master and the p slaves within T time-units?.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101974
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:09 AM
Last modification on : Wednesday, November 20, 2019 - 2:50:26 AM

File

RR2002-07.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101974, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs. [Research Report] LIP RR-2002-07, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02101974⟩

Share

Metrics

Record views

7

Files downloads

14