Towards practical page coloring-based multicore cache management

ABSTRACT

Modern multi-core processors present new resource management challenges due to the subtle interactions of simultaneously executing processes sharing on-chip resources (particularly the L2 cache). Recent research demonstrates that the operating system may use the page coloring mechanism to control cache partitioning, and consequently to achieve fair and efficient cache utilization. However, page coloring places additional constraints on memory space allocation, which may conflict with application memory needs. Further, adaptive adjustments of cache partitioning policies in a multi-programmed execution environment may incur substantial overhead for page recoloring (or copying). This paper proposes a hot-page coloring approach enforcing coloring on only a small set of frequently accessed (or hot) pages for each process. The cost of identifying hot pages online is reduced by leveraging the knowledge of spatial locality during a page table scan of access bits. Our results demonstrate that hot page identification and selective coloring can significantly alleviate the coloring-induced adverse effects in practice. However, we also reach the somewhat negative conclusion that without additional hardware support, adaptive page coloring is only beneficial when recoloring is performed infrequently (meaning long scheduling time quanta in multi-programmed executions).

REFERENCES

• 1: Amazon. Amazon elastic compute cloud. http://aws.amazon.com/ec2/.
• 2: AMD64-manual. AMD-64 architecture programmer's manual, 2008.
• 3: Edouard Bugnion , Jennifer M. Anderson , Todd C. Mowry , Mendel Rosenblum , Monica S. Lam, Compiler-directed page coloring for multiprocessors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.244-255, October 01-04, 1996, Cambridge, Massachusetts, United States
• 4: Derek Chiou , Prabhat Jain , Larry Rudolph , Srinivas Devadas, Application-specific memory management for embedded systems using software-controlled caches, Proceedings of the 37th conference on Design automation, p.416-419, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337523]
• 5: Sangyeun Cho , Lei Jin, Managing Distributed, Shared L2 Caches through OS-Level Page Allocation, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.455-468, December 09-13, 2006 [doi>10.1109/MICRO.2006.31]
• 6: 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]
• 7: GoGrid. http://www.gogrid.com.
• 8: 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]
• 9: IA32-manual. IA-32 Intel architecture software developer's manual, 2008. http://www.intel.com&/products/processor/manuals/.
• 10: Intel. TLBs, paging-structure caches, and their invalidation, 2008. http://www.intel.com/design/processor/applnots/317080.pdf.
• 11: Ravi Iyer , Li Zhao , Fei Guo , Ramesh Illikkal , Srihari Makineni , Don Newell , Yan Solihin , Lisa Hsu , Steve Reinhardt, QoS policies and architecture for cache/memory in CMP platforms, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 12: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• 13: 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]
• 14: D. Lee , J. Choi , J. H. Kim , S. H. Noh , S. L. Min , Y. Cho , C. S. Kim, LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies, IEEE Transactions on Computers, v.50 n.12, p.1352-1361, December 2001 [doi>10.1109/TC.2001.970573]
• 15: J. Lin, Q. Lu, X. Ding, Z. Zhang, X. Zhang, and P. Sadayappan. Gaining insights into multicore cache partitioning: Bridging the gap between simulation and real systems. In Int'l Symp. on High-Performance Computer Architecture (HPCA), pages 367--378, Salt Lake, UT, February 2008.
• 16: Pin Lu , Kai Shen, Virtual machine memory access tracing with hypervisor exclusive cache, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-15, June 17-22, 2007, Santa Clara, CA
• 17: David A. Patterson, Latency lags bandwith, Communications of the ACM, v.47 n.10, p.71-75, October 2004 [doi>10.1145/1022594.1022596]
• 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: A. Raghuraman. Miss-ratio curve directed memory management for high performance and low energy. Master's thesis, Dept. of Computer Science, UIUC, 2003.
• 21: T. H. Romer, D. Lee, B. N. Bershad, and J. B. Chen. Dynamic page mapping policies for cache conflict resolution on standard hardware. In First USENIX Symp. on Operating Systems Design and Implementation (OSDI), pages 255--266, Monterey, CA, November 1994.
• 22: Timothy Sherwood , Brad Calder , Joel Emer, Reducing cache misses using hardware and software page placement, Proceedings of the 13th international conference on Supercomputing, p.155-164, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305189]
• 23: Livio Soares , David Tam , Michael Stumm, Reducing the harmful effects of last-level cache polluters with an OS-level, software-only pollute buffer, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.258-269, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771796]
• 24: L. B. Sokolinsky. LFU-K: An effective buffer management replacement algorithm. In 9th International Conference on Database Systems for Advanced Applications, pages 670--681, 2004.
• 25: 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]
• 26: G. E. Suh, L. Rudolph, and Srini Devadas. Dynamic cache partitioning for simultaneous multithreading systems. In Int'l Conf. on Parallel and Distributed Computing and Systems, pages 116--127, Anaheim, CA, August 2001.
• 27: D. Tam, R. Azimi, L. Soares, and M. Stumm. Managing shared L2 caches on multicore systems in software. In Workshop on the Interaction between Operating Systems and Computer Architecture, San Diego, CA, June 2007.
• 28: George Taylor , Peter Davies , Michael Farmwald, The TLB slice—a low-cost high-speed address translation mechanism, Proceedings of the 17th annual international symposium on Computer Architecture, p.355-363, May 28-31, 1990, Seattle, Washington, United States
• 29: 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]
• 30: 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
• 31: Li Zhao , Ravi Iyer , Ramesh Illikkal , Jaideep Moses , Srihari Makineni , Don Newell, CacheScouts: Fine-Grain Monitoring of Shared Caches in CMP Platforms, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.339-352, September 15-19, 2007 [doi>10.1109/PACT.2007.19]
• 32: Pin Zhou , Vivek Pandey , Jagadeesan Sundaresan , Anand Raghuraman , Yuanyuan Zhou , Sanjeev Kumar, Dynamic tracking of page miss ratio curve for memory management, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Measurement, Performance

Keywords:
cache partitioning, multi-core, page coloring, resource management