Directed Acyclic Graph (DAG) scheduling in a heterogeneous environment is aimed at assigning the on-the-fly jobs to a cluster of heterogeneous computing executors in order to minimize the makespan while meeting all requirements of scheduling. The problem gets more attention than ever since the rapid development of heterogeneous cloud computing. A little reduction of makespan of DAG scheduling could both bring huge profits to the service providers and increase the level of service of users. Although DAG scheduling plays an important role in cloud computing industries, existing solutions still have huge room for improvement, especially in making use of topological dependencies between jobs. In this paper, we propose a task-duplication based learning algorithm, called textit{Lachesis}, for the distributed DAG scheduling problem. In our approach, it first perceives the topological dependencies between jobs using a specially designed graph convolutional network (GCN) to select the most likely task to be executed. Then the task is assigned to a specific executor with the consideration of duplicating all its precedent tasks according to a sophisticated heuristic method. We have conducted extensive experiments over standard workload data to evaluate our solution. The experimental results suggest that the proposed algorithm can achieve at most 26.7% reduction of makespan and 35.2% improvement of speedup ratio over seven strong baseline algorithms, including state-of-the-art heuristics methods and a variety of deep reinforcement learning based algorithms.
Download