Reactive NUCA: near-optimal block placement and replication in distributed caches

ABSTRACT

Increases in on-chip communication delay and the large working sets of server and scientific workloads complicate the design of the on-chip last-level cache for multicore processors. The large working sets favor a shared cache design that maximizes the aggregate cache capacity and minimizes off-chip memory requests. At the same time, the growing on-chip communication delay favors core-private caches that replicate data to minimize delays on global wires. Recent hybrid proposals offer lower average latency than conventional designs, but they address the placement requirements of only a subset of the data accessed by the application, require complex lookup and coherence mechanisms that increase latency, or fail to scale to high core counts.

In this work, we observe that the cache access patterns of a range of server and scientific workloads can be classified into distinct classes, where each class is amenable to different block placement policies. Based on this observation, we propose Reactive NUCA (R-NUCA), a distributed cache design which reacts to the class of each cache access and places blocks at the appropriate location in the cache. R-NUCA cooperates with the operating system to support intelligent placement, migration, and replication without the overhead of an explicit coherence mechanism for the on-chip last-level cache. In a range of server, scientific, and multiprogrammed workloads, R-NUCA matches the performance of the best cache design for each workload, improving performance by 14% on average over competing designs and by 32% at best, while achieving performance within 5% of an ideal cache design.

REFERENCES

• 1: M. Azimi, N. Cherukuri, D. N. Jayasimha, A. Kumar, P. Kundu, S. Park, I. Schoinas, and A. S. Vaidya. Integration challenges and trade-offs for tera-scale architectures. Intel Technology Journal, 11(3):173-184, Aug. 2007.
• 2: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 3: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 4: Bradford M. Beckmann , Michael R. Marty , David A. Wood, ASR: Adaptive Selective Replication for CMP Caches, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.443-454, December 09-13, 2006 [doi>10.1109/MICRO.2006.10]
• 5: Bradford M. Beckmann , David A. Wood, Managing Wire Delay in Large Chip-Multiprocessor Caches, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.319-330, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.21]
• 6: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 7: Jichuan Chang , Gurindar S. Sohi, Cooperative Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 8: G. Chen, H. Chen, M. Haurylau, N. Nelson, P. M. Fauchet, E. G. Friedman, and D. H. Albonesi. Electrical and optical on-chip interconnects in scaled microprocessors. In Proceedings of the 2005 IEEE International Symposium on Circuits and Systems, May 2005.
• 9: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Distance Associativity for High-Performance Energy-Efficient Non-Uniform Cache Architectures, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.55, December 03-05, 2003
• 10: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Optimizing Replication, Communication, and Capacity Allocation in CMPs, Proceedings of the 32nd annual international symposium on Computer Architecture, p.357-368, June 04-08, 2005
• 11: 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]
• 12: Yuan Chou , Lawrence Spracklen , Santosh G. Abraham, Store Memory-Level Parallelism Optimizations for Commercial Applications, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.183-196, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.31]
• 13: W. J. Dally and C. L. Seitz. The torus routing chip. Distributed Computing, 1(4):187--196, Dec. 1986.
• 14: John D. Davis , James Laudon , Kunle Olukotun, Maximizing CMP Throughput with Mediocre Cores, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.51-62, September 17-21, 2005 [doi>10.1109/PACT.2005.42]
• 15: Haakon Dybdahl , Per Stenstrom, An Adaptive Shared/Private NUCA Cache Partitioning Scheme for Chip Multiprocessors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.2-12, February 10-14, 2007 [doi>10.1109/HPCA.2007.346180]
• 16: Babak Falsafi , David A. Wood, Reactive NUMA: a design for unifying S-COMA and CC-NUMA, Proceedings of the 24th annual international symposium on Computer architecture, p.229-240, June 01-04, 1997, Denver, Colorado, United States
• 17: C. Fensch and M. Cintra. An OS-based alternative to full hardware coherence on tiled CMPs. In Proceedings of the 14th International Symposium on High-Performance Computer Architecture, Feb. 2008.
• 18: K. Gharachorloo, A. Gupta, and J. Hennessy. Two techniques to enhance the performance of memory consistency models. In Proceedings of the 1991 International Conference on Parallel Processing (Vol. I Architecture), Aug. 1991.
• 19: Zvika Guz , Idit Keidar , Avinoam Kolodny , Uri C. Weiser, Utilizing shared data in chip multiprocessors with the Nahalal architecture, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378535]
• 20: N. Hardavellas, I. Pandis, R. Johnson, N. Mancheril, A. Ailamaki, and B. Falsafi. Database servers on chip multiprocessors: limitations and opportunities. In Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research, Jan. 2007.
• 21: 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]
• 22: Lei Jin , Hyunjin Lee , Sangyeun Cho, A flexible data to L2 cache mapping approach for future multicore processors, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178613]
• 23: Mahmut Kandemir , Feihui Li , Mary Jane Irwin , Seung Woo Son, A novel migration-based NUCA design for chip multiprocessors, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
• 24: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: 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]
• 26: 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]
• 27: Milo M. K. Martin , Mark D. Hill , David A. Wood, Token coherence: decoupling performance and correctness, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 28: Michael R. Marty , Mark D. Hill, Virtual hierarchies to support server consolidation, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 29: Javier Merino , Valentín Puente , Pablo Prieto , José Ángel Gregorio, SP-NUCA: a cost effective dynamic non-uniform cache architecture, ACM SIGARCH Computer Architecture News, v.36 n.2, p.64-71, May 2008 [doi>10.1145/1399972.1399973]
• 30: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 31: R. Ricci, S. Barrus, D. Gebhardt, and R. Balasubramonian. Leveraging bloom filters for smart search within NUCA caches. In Proceedings of the 2006 Workshop on Complexity-Effective Design, Jun. 2006.
• 32: Larry Seiler , Doug Carmean , Eric Sprangle , Tom Forsyth , Michael Abrash , Pradeep Dubey , Stephen Junkins , Adam Lake , Jeremy Sugerman , Robert Cavin , Roger Espasa , Ed Grochowski , Toni Juan , Pat Hanrahan, Larrabee: a many-core x86 architecture for visual computing, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 33: Semiconductor Industry Association. The International Technology Roadmap for Semiconductors (ITRS). http://www.itrs.net/, 2007 Edition.
• 34: 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]
• 35: Stephen Somogyi , Thomas F. Wenisch , Nikolaos Hardavellas , Jangwoo Kim , Anastassia Ailamaki , Babak Falsafi, Memory coherence activity prediction in commercial workloads, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.37-45, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054949]
• 36: D. Tam, R. Azimi, L. Soares, and M. Stumm. Managing shared L2 caches on multicore systems in software. In Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture, Jun. 2007.
• 37: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th annual Design Automation Conference, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 38: Thomas F. Wenisch , Anastasia Ailamaki , Babak Falsafi , Andreas Moshovos, Mechanisms for store-wait-free multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 39: Thomas F. Wenisch , Roland E. Wunderlich , Michael Ferdman , Anastassia Ailamaki , Babak Falsafi , James C. Hoe, SimFlex: Statistical Sampling of Computer System Simulation, IEEE Micro, v.26 n.4, p.18-31, July 2006 [doi>10.1109/MM.2006.79]
• 40: 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]
• 41: M. Zhang and K. Asanovic. Victim migration: Dynamically adapting between private and shared CMP caches. Technical Report MIT-CSAIL-TR-2005-064, MIT, Oct. 2005.
• 42: Michael Zhang , Krste Asanovic, Victim Replication: Maximizing Capacity while Hiding Wire Delay in Tiled Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.336-345, June 04-08, 2005
• 43: Zheng Zhang , Josep Torrellas, Reducing Remote Conflict Misses: NUMA with Remote Cache versus COMA, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.272, February 01-05, 1997
• 44: Li Zhao , Ravi Iyer , Mike Upton , Don Newell, Towards hybrid last level caches for chip-multiprocessors, ACM SIGARCH Computer Architecture News, v.36 n.2, May 2008 [doi>10.1145/1399972.1399982]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Interleaved memories**; Shared memory

General Terms:
Design, Experimentation, Performance

Keywords:
block migration, block placement, block replication, cache, cache coherence, cache indexing, cache lookup, cache management, chip multiprocessor, cmp, coherence, data migration, data placement, data replication, interleaving, last-level cache, lookup, migration, multi-core, multicore, non-uniform cache access, nuca, placement, private cache, r-nuca, reactive nuca, replication, rotational interleaving, shared cache