Architectural support for operating system-driven CMP cache management

ABSTRACT

The role of the operating system (OS) in managing shared resources such as CPU time, memory, peripherals, and even energy is well motivated and understood [23]. Unfortunately, one key resource—lower-level shared cache in chip multi-processors—is commonly managed purely in hardware by rudimentary replacement policies such as least-recentlyused (LRU). The rigid nature of the hardware cache management policy poses a serious problem since there is no single best cache management policy across all sharing scenarios. For example, the cache management policy for a scenario where applications from a single organization are running under "best effort" performance expectation is likely to be different from the policy for a scenario where applications from competing business entities (say, at a third party data center) are running under a minimum service level expectation. When it comes to managing shared caches, there is an inherent tension between flexibility and performance. On one hand, managing the shared cache in the OS offers immense policy flexibility since it may be implemented in software. Unfortunately, it is prohibitively expensive in terms of performance for the OS to be involved in managing temporally fine-grain events such as cache allocation. On the other hand, sophisticated hardware-only cache management techniques to achieve fair sharing or throughput maximization have been proposed. But they offer no policy flexibility.This paper addresses this problem by designing architectural support for OS to efficiently manage shared caches with a wide variety of policies. Our scheme consists of a hardware cache quota management mechanism, an OS interface and a set of OS level quota orchestration policies. The hardware mechanism guarantees that OS-specified quotas are enforced in shared caches, thus eliminating the need for (and the performance penalty of) temporally fine-grained OS intervention. The OS retains policy flexibility since it can tune the quotas during regularly scheduled OS interventions. We demonstrate that our scheme can support a wide range of policies including policies that provide (a) passive performance differentiation, (b) reactive fairness by miss-rate equalization and (c) reactive performance differentiation.

REFERENCES

• 1: Paul Barford , Mark Crovella, Generating Representative Web Workloads for Network and Server Performance Evaluation, Boston University, Boston, MA, 1997
• 2: M. J. Buco , R. N. Chang , L. Z. Luan , C. Ward , J. L. Wolf , P. S. Yu, Utility computing SLA management based upon business objectives, IBM Systems Journal, v.43 n.1, p.159-178, January 2004
• 3: D. R. Cheriton , A. Gupta , P. D. Boyle , H. A. Goosen, The VMP multiprocessor: initial experience, refinements, and performance evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.410-421, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 4: D. Chiou, P. Jain, S. Devadas, and L. Rudolph. Dynamic Cache Partitioning via Columnization. In Proceedings of Design Automation Conference, Los Angeles, june 2000.
• 5: Joseph R. Eykholt, Steve R. Kleiman, Steve Barton, Roger Faulkner, Anil Shivalingiah, Mark Smith, Dan Stein, Jim Voll, Mary Weeks, and Dock Williams. Beyond Multiprocessing: Multithreading the SunOS Kernel. In Proceedings of theSummer 1992 USENIX Technical Conference and Exhibition, pages 11--18, San Antontio, TX, USA, 1992.
• 6: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 7: Ravi Iyer, CQoS: a framework for enabling QoS in shared caches of CMP platforms, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006246]
• 8: B. Jacob , T. Mudge, Software-Managed Address Translation, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.156, February 01-05, 1997
• 9: 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]
• 10: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 11: Chun Liu , Anand Sivasubramaniam , Mahmut Kandemir, Organizing the Last Line of Defense before Hitting the Memory Wall for CMPs, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.176, February 14-18, 2004 [doi>10.1109/HPCA.2004.10017]
• 12: Philip Machanick , Pierre Salverda , Lance Pompe, Hardware-software trade-offs in a direct Rambus implementation of the RAMpage memory hierarchy, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.105-114, October 02-07, 1998, San Jose, California, United States
• 13: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 14: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 15: Jim Mauro. The Solaris Process Model: Managing Thread Execution and Wait Times in the System Clock Handler, 2000.
• 16: Kunle Olukotun , Lance Hammond, The future of microprocessors, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095418]
• 17: M. P. Papazoglou , D. Georgakopoulos, Introduction, Communications of the ACM, v.46 n.10, October 2003 [doi>10.1145/944217.944233]
• 18: Moinuddin K. Qureshi , David Thompson , Yale N. Patt, The V-Way Cache: Demand Based Associativity via Global Replacement, Proceedings of the 32nd annual international symposium on Computer Architecture, p.544-555, June 04-08, 2005
• 19: Nauman Rafique, Won-Taek Lim, and Mithuna Thottethodi. Architectural Support for Operating System-Driven CMP Cache Management. Technical Report TR ECE 06-11, Purdue University, 2006.
• 20: Parthasarathy Ranganathan , Norman Jouppi, Enterprise IT Trends and Implications for Architecture Research, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.253-256, February 12-16, 2005 [doi>10.1109/HPCA.2005.14]
• 21: Alex Settle, Dan Connors, Enric Gibert, and Antonio Gonzalez. A Dynamically Reconfigurable Cache for Multithreaded Processors. Journal of Embedded Computing: Special Issue on Single-Chip Multi-core Architectures, December 2005.
• 22: P. Shivakumar and Norm P. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power and Area Model. Technical Report, 2001.
• 23: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 24: 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
• 25: G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004 [doi>10.1023/B:SUPE.0000014800.27383.8f]
• 26: sun.com. Solaris Containers-Resource Management and Solaris Zones. In System Administration Guide.
• 27: Thomas Y. Yeh , Glenn Reinman, Fast and fair: data-stream quality of service, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086328]
• 28: Li Zhang , Danilo Ardagna, SLA based profit optimization in autonomic computing systems, Proceedings of the 2nd international conference on Service oriented computing, November 15-19, 2004, New York, NY, USA [doi>10.1145/1035167.1035193]
• 29: Zhichun Zhu , Zhao Zhang, A Performance Comparison of DRAM Memory System Optimizations for SMT Processors, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.213-224, February 12-16, 2005 [doi>10.1109/HPCA.2005.2]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Algorithms, Design, Performance

Keywords:
CMP, OS, QoS, SLAs, cache, fairness, interface, quotas