HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

Contributor : Pierre-François Dutot Connect in order to contact the contributor
Submitted on : Wednesday, February 1, 2006 - 6:27:59 PM
Last modification on : Friday, February 4, 2022 - 3:11:20 AM
Long-term archiving on: : Saturday, April 3, 2010 - 10:03:21 PM


  • HAL Id : inria-00001081, version 1



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



Record views


Files downloads