DocumentCode :
1436203
Title :
On exploiting task duplication in parallel program scheduling
Author :
Ahmad, Ishfaq ; Kwok, Yu-Kwong
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ., Hong Kong
Volume :
9
Issue :
9
fYear :
1998
fDate :
9/1/1998 12:00:00 AM
Firstpage :
872
Lastpage :
892
Abstract :
One of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous algorithms
Keywords :
message passing; multiprocessing systems; processor scheduling; communication overhead; message-passing; multicomputer systems; parallel program scheduling; task duplication; task graphs; Algorithm design and analysis; Bandwidth; Computational efficiency; Concurrent computing; Costs; Delay; Processor scheduling; Scheduling algorithm; Timing; Workstations;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.722221
Filename :
722221
Link To Document :
بازگشت