A List Scheduling Algorithm for DAG-Based Parallel Computing Models

摘要

Task scheduling on multiprocessor system is a well-known problem in area of parallel computing. For this problem, many static scheduling algorithms have been reported. But in most static algorithms, only one attribute of tasks is considered when constructing a ready list, which consists of all ready tasks, and there is no evaluation for different task attributes. In this paper, a list scheduling algorithm for DAG-based parallel computing models is proposed. It is mainly designed for reducing the scheduling length of applications with regular DAG models. Eight task attributes in the DAG model are evaluated, and corresponding rules are presented, which will be used in constructing the ready list. And when scheduling tasks, its start time and communication cost on idle processors are taken into consideration. Experimental results show that the proposed algorithm can achieve a significant performance improvement, which is up to 142%.