Date Added: May 2009
Cache sharing in Chip Multiprocessors brings cache contention among co-running 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 paper, the authors show that relaxing those constraints, particularly the assumptions on job lengths and reschedulings, increases the complexity of the problem significantly. Subsequently, they propose a series of algorithms to compute or approximate the optimal schedules in the more general setting.