A study on optimally co-scheduling jobs of different lengths on chip multiprocessors

ABSTRACT

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.

REFERENCES

• 1: Gnu linear programming kit. Available at http://www.gnu.org/software/glpk/glpk.html.
• 2: Stanford parallel applications for shared memory (splash) benchmark. Available at http://www-flash.stanford.edu/SPLASH/.
• 3: 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
• 4: 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]
• 5: Peter J. Denning, Thrashing: its causes and prevention, Proceedings of the December 9-11, 1968, fall joint computer conference, part I, December 09-11, 1968, San Francisco, California [doi>10.1145/1476589.1476705]
• 6: 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.
• 7: 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.
• 8: Ali 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.
• 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: T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, 2001.
• 11: 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]
• 12: 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]
• 13: Yunlian Jiang , Xipeng Shen , Jie Chen , Rahul Tripathi, Analysis and approximation of optimal co-scheduling on chip multiprocessors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454146]
• 14: 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]
• 15: 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]
• 16: 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
• 17: 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.
• 18: Moinuddin K. Qureshi , Yale N. Patt, Utility-Based Cache Partitioning: A Low-Overhead, High-Performance, Runtime Mechanism to Partition Shared Caches, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.423-432, December 09-13, 2006 [doi>10.1109/MICRO.2006.49]
• 19: 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]
• 20: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 21: 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]
• 22: 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
• 23: 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
• 24: 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
• 25: G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy [doi>10.1145/377792.377797]
• 26: G. Edward Suh , Srinivas Devadas , Larry Rudolph, A New Memory Monitoring Scheme for Memory-Aware Scheduling and Partitioning, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.117, February 02-06, 2002
• 27: 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
• 28: 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

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:
a*-search, cache contention, cmp scheduling, co-scheduling, perfect matching