A scalable task duplication based scheduling algorithm for heterogeneous systems

Optimal scheduling of tasks represented by a directed acyclic graph (DAG) onto a set of homogeneous processors, is a strong NP-hard problem. In this paper we introduce a scalable scheduling scheme called STDS for heterogeneous systems. This implies that tasks could potentially have different run times on different processors. The complexity of STDS is O(v²) where v is the number of nodes in the task graph. Schedule length is primarily reduced by selected task duplication. Current task duplication based scheduling schemes are mostly done for homogeneous systems. Comparing the performance of STDS with BIL, another scheduling scheme for heterogeneous systems, it is observed that STDS obtained speed-ups of 6 to 40 generating shorter schedules when sufficient duplication can be carried out