Analysis and Approximation of Optimal Co-Scheduling on Chip Multiprocessors
Yunlian Jiang, Xipeng Shen, Jie Chen, and Rahul Tripathi
ABSTRACT
Cache sharing among processors is important for Chip Multiprocessors
to reduce inter-thread latency, but also brings cache contention,
degrading program performance considerably. Recent studies have
shown that job co-scheduling can effectively alleviate the
contention, but it remains an open question how to efficiently find
optimal co-schedules. Solving the question is critical for
determining the potential of a co-scheduling system. This paper
presents a theoretical analysis of the complexity of co-scheduling,
proving its NP-completeness. Furthermore, for a special case when
there are two sharers per chip, we propose an algorithm that finds
the optimal co-schedules in polynomial time. For more complex cases,
we design and evaluate a sequence of approximation algorithms, among
which, the hierarchical matching algorithm produces near-optimal
schedules and shows good scalability. This study facilitates the
evaluation of co-scheduling systems, as well as offers some
techniques directly usable in proactive job co-scheduling.
Download the paper in
pdf format.
Copyright notice