Research of Redundant Elimination of Task Scheduling for Homogeneous Parallel Systems

The scheduling of multiple tasks for parallel and distributed computing systems is one of the NP-complete problems. Most of the duplication-based scheduling heuristics try to duplicate the ancestor nodes of a given join node, it would inevitably induce redundant duplications. This paper proposes a novel method basing on the CPFD or SD scheduling algorithm to Eliminate the Redundant Duplications(ERD), it records the sources of the used data and the tendency of the results of every node in the scheduling. And after that, these recorded are applied to eliminate the redundant duplications in a bottom-up fashion. The result of algorithm analysis shows that the proposed algorithm can effectively reduce the number of duplications produced by the existing duplication-based task scheduling heuristics, and the number of the processors as well.