DyDupSA - Dynamic Task Duplication Based Scheduling Algorithm for Multiprocessor System

Scheduling of tasks of a Directed Acyclic Graph (DAG) onto a set of processors is a NP-hard problem. In this paper we present a scheduling algorithm named as DyDupSA (Dynamic Task Duplication based Scheduling Algorithm) to schedule tasks onto a heterogeneous system to minimize the length of schedule, maximize resource utilization and increase the speed up ratio. The existing task duplication based scheduling algorithms proposed for heterogeneous system didn't focus on the above features. The performance of the proposed algorithm is compared with existing scheduling algorithms for heterogeneous processors.