Analysis and approximation of optimal co-scheduling on chip multiprocessors

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.

REFERENCES

• 1: James R. Bulpin , Ian A. Pratt, Hyper-threading aware process scheduling heuristics, Proceedings of the annual conference on USENIX Annual Technical Conference, p.27-27, April 10-15, 2005, Anaheim, CA
• 2: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 3: William Cook , Andre Rohe, Computing Minimum-Weight Perfect Matchings, INFORMS Journal on Computing, v.11 n.2, p.138-148, February 1999 [doi>10.1287/ijoc.11.2.138]
• 4: P. Denning. Thrashing: Its causes and prevention. In Proceedings of the AFIPS 1968 Fall Joint Computer Conference, volume 33, pages 915--922, 1968.
• 5: M. DeVuyst, R. Kumar, and D. M. Tullsen. Exploiting unbalanced thread scheduling for energy and performance on a cmp of smt processors. In Proceedings of International Parallel and Distribute Processing Symposium (IPDPS), 2006.
• 6: J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B, 69B:125--130, 1965.
• 7: A. El-Moursy, R. Garg, D. H. Albonesi, and S. Dwarkadas. Compatible phase co-scheduling on a cmp of multi-threaded processors. In Proceedings of International Parallel and Distribute Processing Symposium (IPDPS), 2006.
• 8: Alexandra Fedorova , Margo Seltzer , Christoper Small , Daniel Nussbaum, Performance of multithreaded chip multiprocessors and implications for operating system design, Proceedings of the annual conference on USENIX Annual Technical Conference, p.26-26, April 10-15, 2005, Anaheim, CA
• 9: Alexandra Fedorova , Margo Seltzer , Michael D. Smith, Improving Performance Isolation on Chip Multiprocessors via an Operating System Scheduler, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.25-38, September 15-19, 2007 [doi>10.1109/PACT.2007.40]
• 10: Harold N. Gabow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991 [doi>10.1145/115234.115366]
• 11: M. Garey and D. Johnson. Computers and Intractability. Feeman, San Francisco, CA, 1979.
• 12: Lisa R. Hsu , Steven K. Reinhardt , Ravishankar Iyer , Srihari Makineni, Communist, utilitarian, and capitalist cache policies on CMPs: caches as a shared resource, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152161]
• 13: Jaehyuk Huh , Changkyu Kim , Hazim Shafi , Lixin Zhang , Doug Burger , Stephen W. Keckler, A NUCA substrate for flexible CMP cache sharing, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088154]
• 14: Y. Jiang and X. Shen. Exploration of the influence of program inputs on cmp co-scheduling. In European Conference on Parallel Computing (Euro-Par), August 2008.
• 15: R. Karp. Reducibility among combinatiorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.
• 16: Seongbeom Kim , Dhruba Chandra , Yan Solihin, Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, September 29-October 03, 2004 [doi>10.1109/PACT.2004.15]
• 17: Rakesh Kumar , Dean M. Tullsen , Norman P. Jouppi, Core architecture optimization for heterogeneous chip multiprocessors, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152162]
• 18: J. McCalpin. Memory bandwidth and machine balance in current high performance computers. IEEE TCCA Newsletter, 1995. http://www.cs.virginia.edu/stream.
• 19: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 20: Jun Nakajima , Venkatesh Pallipadi, Enhancements for hyper-threading technology in the operating system: seeking the optimal scheduling, Proceedings of the 2nd conference on Industrial Experiences with Systems Software, p.3-3, December 08, 2002, Boston, MA
• 21: S. Parekh, S. Eggers, H. Levy, and J. Lo. Thread-sensitive scheduling for smt processors. Technical Report 2000-04-02, University of Washington, June 2000.
• 22: Nauman Rafique , Won-Taek Lim , Mithuna Thottethodi, Architectural support for operating system-driven CMP cache management, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152160]
• 23: Alex Settle , Joshua Kihm , Andrew Janiszewski , Dan Connors, Architectural Support for Enhanced SMT Job Scheduling, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.63-73, September 29-October 03, 2004 [doi>10.1109/PACT.2004.7]
• 24: X. Shen and J. Shaw. Scalable implementation of efficient locality approximation. In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing, 2008.
• 25: Xipeng Shen , Jonathan Shaw , Brian Meeker , Chen Ding, Locality approximation using time, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 26: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 27: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 28: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 29: Allan Snavely , Dean M. Tullsen , Geoff Voelker, Symbiotic jobscheduling with priorities for a simultaneous multithreading processor, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 30: Harold S. Stone , John Turek , Joel L. Wolf, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, v.41 n.9, p.1054-1068, September 1992 [doi>10.1109/12.165388]
• 31: G. Suh, S. Devadas, and L. Rudolph. A new memory monitoring scheme for memory-aware scheduling and partitioning. In Proceedings of the International Conference on Parallel Architecture and Compilation Techniques, 2002.
• 32: Nathan Tuck , Dean M. Tullsen, Initial Observations of the Simultaneous Multithreading Pentium 4 Processor, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.26, September 27-October 01, 2003
• 33: Xiao Zhang , Sandhya Dwarkadas , Girts Folkmanis , Kai Shen, Processor hardware counter statistics as a first-class system resource, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA
• 34: Yutao Zhong , Wentao Chang, Sampling-based program locality approximation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375648]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Algorithms, Experimentation, Performance

Keywords:
CMP scheduling, cache contention, co-scheduling, perfect matching