%0 Conference Paper %1 Jiang:2008:AAO:1454115.1454146 %A Jiang, Yunlian %A Shen, Xipeng %A Chen, Jie %A Tripathi, Rahul %B Proceedings of the 17th international conference on Parallel architectures and compilation techniques %C New York, NY, USA %D 2008 %I ACM %K approximation.algorithm multiprocessor scheduling %P 220--229 %R 10.1145/1454115.1454146 %T Analysis and approximation of optimal co-scheduling on chip multiprocessors %X 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. %@ 978-1-60558-282-5

@inproceedings{Jiang:2008:AAO:1454115.1454146, 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.}, acmid = {1454146}, added-at = {2012-09-21T22:21:31.000+0200}, address = {New York, NY, USA}, author = {Jiang, Yunlian and Shen, Xipeng and Chen, Jie and Tripathi, Rahul}, biburl = {https://www.bibsonomy.org/bibtex/29dd9332097315a43e64173318f6a22a9/ytyoun}, booktitle = {Proceedings of the 17th international conference on Parallel architectures and compilation techniques}, doi = {10.1145/1454115.1454146}, interhash = {b8a21b7a2a0941b19a3b5527f51c0ddd}, intrahash = {9dd9332097315a43e64173318f6a22a9}, isbn = {978-1-60558-282-5}, keywords = {approximation.algorithm multiprocessor scheduling}, location = {Toronto, Ontario, Canada}, numpages = {10}, pages = {220--229}, publisher = {ACM}, series = {PACT '08}, timestamp = {2012-09-21T22:21:32.000+0200}, title = {Analysis and approximation of optimal co-scheduling on chip multiprocessors}, year = 2008 }