Sharing-aware OS scheduling algorithms for multi-socket multi-core servers

ABSTRACT

Major chip manufacturers have all introduced multi-core microprocessors. Multi-socket systems built from these processors are routinely used for running various server applications. Typically each processor in such a system shares a cache at either the L2 or L3 level. Depending on the application that is run on the system, inter-socket cache-to-cache transfers can impact overall performance. This paper presents a new operating system (OS) scheduling optimization to reduce the impact of such inter-socket cache-to-cache transfers.

By observing the pattern of cache-to-cache transfers between every pair of threads for each scheduling quantum and applying four different algorithms, we come up with a new schedule of threads for the next quantum. This new schedule potentially cuts down the inter-socket cache-to-cache transfers for the next scheduling quantum. We studied the impact of these algorithms on 18 real-world benchmarks. For the benchmarks we studied, inter-socket cache-to-cache transfers were cut down by as much as 99.3% on some benchmarks and, on average, between -5.5% and 24% depending on the scheduling algorithm employed.

REFERENCES

• 1: R. Thekkath , S. J. Eggers, Impact of sharing-based thread placement on multithreaded architectures, Proceedings of the 21st annual international symposium on Computer architecture, p.176-186, April 18-21, 1994, Chicago, Illinois, United States
• 2: David Tam , Reza Azimi , Michael Stumm, Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
• 3: www.top500.org
• 4: S. Sridharan et al. Thread migration to improve synchronization performance. In Workshop on Operating System Interference in High Performance Applications, 2006.
• 5: J. Nakajima et al. Enhancements for Hyper-Threading technology in the operating system -- seeking the optimal micro-architectural scheduling. In Intl. Parallel and Distributed Processing Symp. 2005.
• 6: 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
• 7: A. El-Moursy et al. Compatible phase co-scheduling on a CMP of multi-threaded processors. In Intl. Parallel and Distributed Processing Symp. 2006.

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: Threads; Multiprocessing/multiprogramming/multitasking

General Terms:
Algorithms, Management, Performance

Keywords:
cache-to-cache transfers, scheduling algorithms