The Master-Slave Paradigm with Heterogeneous Processors

Olivier Beaumont 1, 2 Arnaud Legrand 3 Yves Robert 3
2 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We revisit the master-slave tasking paradigm in the context of heterogeneous processors. We assume that communications are handled by a bus and, therefore, at most one communication can take place at a given time step. We present a polynomial algorithm that gives the optimal solution when a single communication is needed before the execution of the tasks on the slave processors. When communications are required both before and after the processing of the tasks, we show that the problem is strongly NP-complete. In this case, we present a guaranteed approximation algorithm. Finally, we present asymptotically optimal algorithms when communications are required before the processing of each task, or both before and after the processing of each task.
Type de document :
Article dans une revue
IEEE Trans. Parallel Distributed Systems, IEEE Computer Society, 2003, 14, pp.897―908. 〈10.1109/TPDS.2003.1233712〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00789429
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:50:22
Dernière modification le : vendredi 11 septembre 2015 - 01:06:00

Identifiants

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. The Master-Slave Paradigm with Heterogeneous Processors. IEEE Trans. Parallel Distributed Systems, IEEE Computer Society, 2003, 14, pp.897―908. 〈10.1109/TPDS.2003.1233712〉. 〈hal-00789429〉

Partager

Métriques

Consultations de la notice

273