Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 metadata
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Wednesday, April 3, 2013 - 2:53:44 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:37 AM


  • HAL Id : hal-00807403, version 1



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⟩



Record views