Comparative study of static scheduling with task duplication for distributed systems

Efficient scheduling of parallel tasks onto processing elements of concurrent computer systems has been an important research issue for decades. The communication overhead often limits the speedup of parallel programs in distributed systems. Duplication Based Scheduling (DBS) has been proposed to reduce the communication overhead by duplicating remote parent tasks on local processing elements. The DBS algorithms need task selection heuristics which decide the order of tasks to be considered for scheduling. This paper explores the speedup obtained by employing task duplication in the scheduling process and also investigates the effect of different task selection heuristics on a DBS algorithm. Our simulation results show that employing task duplication achieves considerable improvement in the application parallel execution time, but employing different task selection heuristics does not affect the speedup significantly.