A Study on Optimally Co-scheduling Jobs of Different Lengths on Chip Multiprocessors
Kai Tian, Yunlian Jiang, Xipeng Shen
Cache sharing in Chip Multiprocessors brings cache contention among
corunning processes, which often causes considerable degradation of
program performance and system fairness. Recent studies have seen
the effectiveness of job co-scheduling in alleviating the
contention. But finding optimal schedules is challenging. Previous
explorations tackle the problem under highly constrained settings.
In this work, we show that relaxing those constraints, particularly
the assumptions on job lengths and reschedulings, increases the
complexity of the problem significantly. Subsequently, we propose a
series of algorithms to compute or approximate the optimal schedules
in the more general setting.
Specifically, we propose an A*-based approach to accelerating the
search for optimal schedules by as much as several orders of
magnitude. For large problems, we design and evaluate two
approximation algorithms, A*-cluster and local-matching algorithms,
to effectively approximate the optimal schedules with good accuracy
and high scalability. This study contributes better understanding to
the optimal co-scheduling problem, facilitates the evaluation of
co-scheduling systems, and offers insights and techniques for the
development of practical co-scheduling algorithms.
Download the paper in pdf