Paper Info
Title
Master-slave Tasking on Heterogeneous Processors
Abstract
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.
Year
DOI
Venue
2003
10.1109/IPDPS.2003.1213103
IPDPS
Keywords
Field
DocType
processing time,communication time,spider graph,master-slave tasking,heterogeneous processors,heterogeneous processor,independent identical task,special kind,concurrent computing,complexity,high performance computing,parallel algorithm,polynomials,scheduling algorithm,distributed algorithms,tree graphs,makespan,master slave,computational complexity,steady state
Multiprocessor scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Parallel computing,Distributed algorithm,Dynamic priority scheduling,Master/slave,Distributed computing,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
0-7695-1926-1
9
0.58
References 
Authors
5
1
Name
Order
Citations
PageRank
Pierre-françois Dutot116613.95