Master-Slave Tasking with Heterogeneous Processors

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 scheduling independent identical tasks on heterogeneous processors where communication times and processing times are different. We assume that communication-computation overlap is possible for every processor, but only allow one send and one receive at a time. We propose an algorithm for chains of processors based on an iterative backward construction of the schedule, which is polynomial in the number of processors and in the number of tasks. The complexity is O(np2) where n is the number of tasks and p the number of processors. We prove this algorithm to be optimal with respect to the makespan. We extend this result to a special kind of tree called spider graphs.
Type de document :
Communication dans un congrès
2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\'2001), 2001, Unknown, CSREA Press, pp.857―863, 2001, 〈10.1109/IPDPS.2003.1213103〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00789462
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:52:00
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. Master-Slave Tasking with Heterogeneous Processors. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\'2001), 2001, Unknown, CSREA Press, pp.857―863, 2001, 〈10.1109/IPDPS.2003.1213103〉. 〈hal-00789462〉

Partager

Métriques

Consultations de la notice

109