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?.
Liste complète des métadonnées

https://hal.inria.fr/hal-00807403
Contributeur : Equipe Roma <>
Soumis le : mercredi 3 avril 2013 - 14:53:44
Dernière modification le : mardi 16 janvier 2018 - 15:42:51

Identifiants

  • HAL Id : hal-00807403, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

193