Task-duplication And Insertion Based Scheduling Algorithm For Heterogeneous Computing Environments

Optimal scheduling of parallel tasks with precedence relationships in heterogeneous environments plays a significant role in the area of parallel and distributed computation. This problem is NP-hard problem and can't get deterministic solution at polynomial time unless P= NP. In recent twenty years, researchers have tried to solve this NP-hard problem with higher quality and lower complexity.Task duplication-based(TDB) scheme is a well-known strategy, and the insertion strategy can also be considered based on the TDB scheme. We redesigned several key steps for the TDB process including the parameter calculation, task duplication, task merging and task insertion, and propose a Task-Duplication and Insertion based Clustering and Merging Algorithm(TDICMA). There exists a phenomenon of chain reaction during the process of the task duplication, i.e. a duplication that has been evaluated to be ineffective may become effective again after other duplication has been exerted. Traditional TDB algorithm has not considered this chain reaction, while TDICMA utilizes this chain reaction to get better performance.In addition, a system for comparing distributed tasks scheduling algorithms is developed, which can automatically generate representative test cases. Through this system, we analyze the effects of DAG parameters in detail by comparing with typical algorithms published in the literature. The experiments with DCPD, HEFT and TANH show that TDICMA has improved the results of previous researches in the aspect of the quality of the schedules at the same time without increasing the computational complexity.