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

Olivier Beaumont 1, 2 Arnaud Legrand 3, 4 Yves Robert 3, 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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?.
Complete list of metadatas

https://hal.inria.fr/hal-00807403
Contributor : Equipe Roma <>
Submitted on : Wednesday, April 3, 2013 - 2:53:44 PM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Identifiers

  • HAL Id : hal-00807403, version 1

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs. [Research Report] 2002-7, 2002. ⟨hal-00807403⟩

Share

Metrics

Record views

254