Master-slave Tasking on Heterogeneous Processors

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.