¹Department of Computer Science & Technology Jilin University, Changchun, China
²School of Electrical & Information Technology Changchun Institute of Technology, Changchun, China
³Information center of State Food and Drug Administration, Beijing, China

---

Abstract—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.

Index Terms—Task duplication, task scheduling, multi-core processor, scheduling length, DAG, multi-core-cluster systems.

[PDF]

Cite: Xiaozhong Geng, Gaochao Xu, Xiaodong Fu, Yuan Zhang, "A Task Scheduling Algorithm for Multi-Core- Cluster Systems," Journal of Computers vol. 7, no. 11, pp. 2797-2804, 2012.