CQoS: a framework for enabling QoS in shared caches of CMP platforms

ABSTRACT

Cache hierarchies have been traditionally designed for usage by a single application, thread or core. As multi-threaded (MT) and multi-core (CMP) platform architectures emerge and their workloads range from single-threaded and multithreaded applications to complex virtual machines (VMs), a shared cache resource will be consumed by these different entities generating heterogeneous memory access streams exhibiting different locality properties and varying memory sensitivity. As a result, conventional cache management approaches that treat all memory accesses equally are bound to result in inefficient space utilization and poor performance even for applications with good locality properties. To address this problem, this paper presents a new cache management framework (CQoS) that (1) recognizes the heterogeneity in memory access streams, (2) introduces the notion of QoS to handle the varying degrees of locality and latency sensitivity and (3) assigns and enforces priorities to streams based on latency sensitivity, locality degree and application performance needs. To achieve this, we propose CQoS options for priority classification, priority assignment and priority enforcement. We briefly describe CQoS priority classification and assignment options -- ranging from user-driven and developer-driven to compiler-detected and flow-based approaches. Our focus in this paper is on CQoS mechanisms for priority enforcement -- these include (1) selective cache allocation, (2) static/dynamic set partitioning and (3) heterogeneous cache regions. We discuss the architectural design and implementation complexity of these CQoS options. To evaluate the performance trade-offs for these options, we have modeled these CQoS options in a cache simulator and evaluated their performance in CMP platforms running network-intensive server workloads. Our simulation results show the effectiveness of our proposed options and make the case for CQoS in future multi-threaded/multi-core platforms since it improves shared cache efficiency and increases overall system performance as a result.

REFERENCES

• 1: Hazim Abdel-Shafi , Jonathan Hall , Sarita V. Adve , Vikram S. Adve, An Evaluation of Fine-Grain Producer-Initiated Communication in Cache-Coherent Multiprocessors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.204, February 01-05, 1997
• 2: K. Beyls, "Faster Computing through Software-Controlled Cache Replacement," http://escher.elis.ugent.be/publ/Edocs/DOC/P102_118.pdf
• 3: François Bodin , André Seznec, Skewed Associativity Improves Program Performance and Enhances Predictability, IEEE Transactions on Computers, v.46 n.5, p.530-544, May 1997 [doi>10.1109/12.589219]
• 4: D. Clark et. al., "An analysis of TCP Processing overhead", IEEE Communications, June 1989.
• 5: Tal Garfinkel , Ben Pfaff , Jim Chow , Mendel Rosenblum , Dan Boneh, Terra: a virtual machine-based platform for trusted computing, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: R. Iyer, "CASPER: Cache Architecture, Simulation and Performance Exploration using Re-streams," Intel's Design and Test Technology Conference (DTTC), 2001.
• 7: R. Iyer, "On Modeling and Analyzing Cache Hierarchies using CASPER," MASCOTS-11, 2003.
• 8: P. Jain, et al., "Software Assisted Cache Replacement and Prefetching Pollution Control," http://www.csail.mit.edu/research/abstracts/abstracts03/architecture/24jain.pdf
• 9: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 10: S.T. King, George W. Dunlap, Peter M. Chen, "Operating System Support for Virtual Machines", Proceedings of the 2003 Annual USENIX Technical Conference, June 2003.
• 11: David A. Koufaty , Xiangfeng Chen , David K. Poulsen , Josep Torrellas, Data Forwarding in Scalable Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1250-1264, December 1996 [doi>10.1109/71.553274]
• 12: David J. Lilja , Pen-Chung Yew, Combining hardware and software cache coherence strategies, Proceedings of the 5th international conference on Supercomputing, p.274-283, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109093]
• 13: Srihari Makineni , Ravi Iyer, Architectural Characterization of TCP/IP Packet Processing on the Pentium® M Microprocessor, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.152, February 14-18, 2004 [doi>10.1109/HPCA.2004.10024]
• 14: S. Makineni and R. Iyer, "Performance Characterization of TCP/IP Packet Processing in Commercial Workloads," IEEE WWC-6, 2003.
• 15: D. Marr et al., "Hyper-Threading Technology Architecture and Microarchitecture" Intel Technology Journal, 2002. http://www.intel.com/technology/itj/2002/volume06issue01/
• 16: M. Martin, et al., "Token Coherence: A New Framework for Shared-Memory Multiprocessors," IEEE Micro Special Issue, Nov-Dec 2003.
• 17: N. Megido, "Adaptive Replacement Cache," IBM T.J. Watson Research Center, http://www.almaden.ibm.com/cs/people/dmodha/arc-fast.pdf
• 18: D. Minturn, et al., "Exploiting Architectural Techniques for Improving TCP/IP Processing Performance," submitted to a conference.
• 19: B. A. Nayfeh , K. Olukotun , J. P. Singh, The impact of shared-cache clustering in small-scale shared-memory multiprocessors, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.74, February 03-07, 1996
• 20: J. B. Postel, "Transmission Control Protocol", RFC 793, Information Sciences Institute, Sept. 1981.
• 21: David K. Poulsen , Pen-Chung Yew, Integrating fine-grained message passing in cache coherent shared memory multiprocessors, Journal of Parallel and Distributed Computing, v.33 n.2, p.172-188, March 15, 1996 [doi>10.1006/jpdc.1996.0036]
• 22: Parthasarathy Ranganathan , Vijay S. Pai , Hazim Abdel-Shafi , Sarita V. Adve, The interaction of software prefetching with ILP processors in shared-memory systems, Proceedings of the 24th annual international symposium on Computer architecture, p.144-156, June 01-04, 1997, Denver, Colorado, United States
• 23: André Seznec, Decoupled Sectored Caches, IEEE Transactions on Computers, v.46 n.2, p.210-215, February 1997 [doi>10.1109/12.565601]
• 24: SimpleScalar LLC, http://www.simplescalar.com
• 25: Yan Solihin , Jaejin Lee , Josep Torrellas, Using a user-level memory thread for correlation prefetching, Proceedings of the 29th annual international symposium on Computer architecture, p.171, May 25-29, 2002, Anchorage, Alaska
• 26: "SPECweb99 Design Document," available at http://www.specbench.org/osg/web99/docs/whitepaper.html
• 27: P. Stenstrom, "A Survey of Cache Coherence Protocols," IEEE Computer, 1990.
• 28: E. Suh, L. Rudolph and S. Devadas, "Dynamic Partitioning of Shared Cache Memory," Journal of Supercomputing, July 2002.
• 29: "The TTCP Benchmark", http://ftp.arl.mil/~mike/ttcp.html
• 30: Dean M. Tullsen , Susan J. Eggers, Limitations of cache prefetching on a bus-based multiprocessor, Proceedings of the 20th annual international symposium on Computer architecture, p.278-288, May 16-19, 1993, San Diego, California, United States
• 31: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 32: VMware Inc., "VMware is Virtual Infrastructure", http://www.vmware.com/vinfrastructure/
• 33: Carl A. Waldspurger, Memory resource management in VMware ESX server, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060307]
• 34: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]
• 35: L. Zhao, et al., "Efficient Cache Structures and Policies for Server Network Acceleration," submitted to a conference.

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, QoS, cache, partitioning, performance, sharing