A Polynomial-Time Algorithm for Allocating Independent Tasks on Heterogeneous Fork-Graphs

Olivier Beaumont 1 Arnaud Legrand 1 Yves Robert 1
1 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 ofindependent, equal-sized tasks to a heterogeneous processor farm. Themaster processor P 0 can process a task within w 0 time-units; it communicatesa task in d i time-units to the i-th slave P i , 1 i p, which requiresw i time-units to process it. We assume communication-computationoverlap capabilities for each slave (and for the master), but the communicationmedium is exclusive: the master can only communicate with asingle slave at each time-step.
Type de document :
Communication dans un congrès
ISCIS XVII, Seventeenth International Symposium On Computer and Information Sciences, 2002, Unknown, CRC Press, pp.115―119, 2002
Liste complète des métadonnées

https://hal.inria.fr/hal-00789456
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:48
Dernière modification le : mercredi 14 décembre 2016 - 01:06:41

Identifiants

  • HAL Id : hal-00789456, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. A Polynomial-Time Algorithm for Allocating Independent Tasks on Heterogeneous Fork-Graphs. ISCIS XVII, Seventeenth International Symposium On Computer and Information Sciences, 2002, Unknown, CRC Press, pp.115―119, 2002. <hal-00789456>

Partager

Métriques

Consultations de la notice

82