An Efficient Scheduling Algorithm for Distributed Heterogeneous Systems with Task Duplication Allowed

Due to the restriction of data transmission speed and bandwidth between processing units, communication delays are significantly impacting the complete time of applications in distributed heterogeneous systems. Most of the existing methods considering communication delays are approximate. The performance of solutions given by these heuristic methods are depends on the input instance. Another common choice is optimization methods, such as genetic algorithms and branch-and-bound search. However, these algorithms solve general situations with low efficiency. This paper proposes an efficient scheduling algorithm with task duplication allowed, called DHSA. Task duplication allows tasks executing multiple times to trade extra computation for communication delays, which is widely used in parallel system scheduling approximately. To address the complexity explosion caused by allowing all-task duplication, we decompose the scheduling into allocation and ordering stages and optimize them separately with solving optimization model and slack-interval aware ordering approach. Extensive experiments show that DHSA gives more optimal solutions within feasible time comparing to two state-of-the-art methods, particularly for applications with medium to high communication load.