Optimal Co-Scheduling to Minimize Makespan on Chip Multiprocessors

Abstract. On-chip resource sharing among sibling cores causes resource con-tention on Chip Multiprocessors (CMP), considerably degrading program per-formance and system fairness. Job co-scheduling attempts to alleviate the prob-lem by assigning jobs to cores intelligently. Despite many heuristics-based em-pirical explorations, studies on optimal co-scheduling and its inherent complex-ity start only recently, and all have concentrated on the minimization of total performance degradations. There is another important criterion for scheduling, makespan, which determines the finish time of a job set. Its importance for job co-scheduling on CMP is increasingly recognized, especially with the rise of CMP-based compute cloud, data centers, and server farms. However, optimal co-scheduling for makespan minimization still remains unexplored. This work compares makespan minimization problem with previously studied cost minimization (or degradation minimization) problem, revealing these con-nections as well as significant differences. It uncovers the computational com-plexity of the makespan minimization problem, and proposes a series of algo-rithms to either compute or approximate the optimal schedules. It proves that the problem is NP-complete in a general setting, but for a special case (dual-core without job migrations), the problem is solvable in O(n2.5 · log n) time (n is the number of jobs). In addition, this paper presents a series of algorithms to compute or approximate the optimal schedules in the general setting. Experiments on both real and synthetic problems verify the optimality of the optimal co-scheduling algorithms, and demonstrate the reasonable accuracy and scalability of the ap-proximation algorithms. The findings may advance the current understanding of optimal co-scheduling, facilitate the evaluation of real co-scheduling systems, and provide insights for the development of practical co-scheduling algorithms.