Skip to Main content Skip to Navigation
Conference papers

Master-slave Tasking on Heterogeneous Processors

Pierre-François Dutot 1
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Abstract : In this paper, we consider the problem of scheduling independent identical tasks on heterogeneous processors where communication times and processing times are differ- ent. 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 proces- sors and in the number of tasks. The complexity is O(np2 ) where n is the number of tasks and p the number of proces- sors. 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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00001081
Contributor : Pierre-François Dutot <>
Submitted on : Wednesday, February 1, 2006 - 6:27:59 PM
Last modification on : Tuesday, February 9, 2021 - 3:22:08 PM
Long-term archiving on: : Saturday, April 3, 2010 - 10:03:21 PM

Identifiers

  • HAL Id : inria-00001081, version 1

Collections

INRIA | IMAG | CNRS | UGA

Citation

Pierre-François Dutot. Master-slave Tasking on Heterogeneous Processors. International Parallel and Distributed Processing Symposium, Apr 2003, Nice, France. ⟨inria-00001081⟩

Share

Metrics

Record views

329

Files downloads

263