A Task Scheduling Algorithm for Multi-Core-Cluster Systems

The quantity of cores on one chip increases rapidly with the development of multi-core technology, which has led to more complex structure of cluster system and greatly increasing number of tasks. In order to schedule tasks in multi-core-cluster systems efficiently, a task schedule model based on the directed acyclic graph(DAG) is built, and then a algorithm based on task duplication is proposed. The algorithm is composed of two steps of operations, in which the processes are assigned to processor nodes in the first step and the threads in processes are assigned to core nodes in the second step respectively. The time complexity of this algorithm is less than similar algorithms. For the algorithm, minimization scheduling length is the primary objective, and keeping load balancing between processing nodes is secondary objectives. It can be seen through comparison with correlative work that the algorithm has advantages in scheduling length; furthermore, while the ratio of total communication cost and total computation cost in the task schedule model becomes larger, the advantage of this algorithm is more obvious.