The Master-Slave Paradigm with Heterogeneous Processors

Olivier Beaumont 1, 2 Arnaud Legrand 1 Yves Robert 1, 2
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 revisit the master-slave tasking paradigm in the context of heterogeneous processors. We assume that communications take place in exclusive mode. 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 task processing, we show that the problem is at least as difficult as a problem whose complexity is open. 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072467
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:02:16 AM
Last modification on : Friday, May 17, 2019 - 8:46:23 AM

Identifiers

  • HAL Id : inria-00072467, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. The Master-Slave Paradigm with Heterogeneous Processors. [Research Report] RR-4156, LIP RR-2001-13, INRIA, LIP. 2001. ⟨inria-00072467⟩

Share

Metrics

Record views

263

Files downloads

624