loading...
Master-slave Tasking on Heterogeneous Processors
Nice, France April 22-April 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213103International Parallel and Distribute ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Pierre-François Dutot, Laboratoire ID-IMAG
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.
Citation:
Pierre-François Dutot, "Master-slave Tasking on Heterogeneous Processors," ipdps, pp.25b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.