An Improved Task Duplication based Clustering Algorithm for DAG Task Scheduling in Heterogenous and Distributed Systems
Fan Wei, Jie Zhu, Kexin Ding · 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · 2022
Task scheduling in heterogenous and distributed systems for the directed acyclic graph (DAG) based applications has been widely studied. In DAG task scheduling problems, a set of distributed tasks with dependencies are dispatched to appropriate computing instances. The objective is to obtain the feasible schedule with the minimal schedule length, i.e., makespan. In this paper, we propose a task duplication based clustering framework for the problem under study. We employ the task duplication scheme in the framework which allows task clusters contain duplicated tasks in order to reduce the communication cost. A selection matrix is introduced to record the candidate tasks to generate clusters. Multiple feasible task clustering solutions are obtained based on the selection matrix and among which the best one with the minimal makespan is output. Experimental results indicate that the proposal outperforms compared algorithms on both effectiveness and robustness.