Leveraging on-chip networks for data cache migration in chip multiprocessors

ABSTRACT

Recently, chip multiprocessors (CMPs) have arisen as the de facto design for modern high-performance processors, with increasing core counts. An important property of CMPs is that remote, but on-chip, L2 cache accesses are less costly than off-chip accesses; this is in contrast to earlier chip-to-chip or board-to-board multiprocessors, where an access to a remote node is just as costly if not more so than a main memory access. This motivates on-chip cache migration as a means to retain more data on-chip. However, previously proposed techniques do not scale to high core counts: they do not leverage the on-chip caches of all cores nor have a scalable migration mechanism. In this paper we propose ascalable in-network migration technique which uses hints embedded within the router microarchitecture to steer L2 cache evictions towards free/invalid cache slots in any on-chip core cache, rather than evicting it off-chip. We show that our technique can provide an average of a 19% reduction in the number of off-chip memory accesses over the state-of-the-art, beating the performance of a pseudo-optimal migration technique. This can be done with negligible area overhead and a manageable traffic overhead of 13.4%.

REFERENCES

• 1: 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]
• 2: Doug Burger , James R. Goodman , Alain Kägi, Memory bandwidth limitations of future microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.78-89, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 3: H. Cain et al. Precise and Accurate Processor Simulation. In Proc. of the 5th Workshop on Computer Architecture Evaluation Using Commercial Workloads, pp. 13--22, February, 2006.
• 4: 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
• 5: J. Chen et al. Hardware-Modulated Parallelism in Chip Multiprocessors. In DASCMP, November, 2005.
• 6: 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
• 7: Noel Eisley , Li-Shiuan Peh , Li Shang, In-Network Cache Coherence, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.321-332, December 09-13, 2006 [doi>10.1109/MICRO.2006.27]
• 8: J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 9: Lance Hammond , Benedict A. Hubbert , Michael Siu , Manohar K. Prabhu , Michael Chen , Kunle Olukotun, The Stanford Hydra CMP, IEEE Micro, v.20 n.2, p.71-84, March 2000 [doi>10.1109/40.848474]
• 10: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 11: 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]
• 12: Using Switch Directories to Speed Up Cache-to-Cache Transfers in CC-NUMA Multiprocessors, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.721, May 01-05, 2000
• 13: Stefanos Kaxiras , James R. Goodman, The GLOW cache coherence protocol extensions for widely shared data, Proceedings of the 10th international conference on Supercomputing, p.35-43, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237583]
• 14: L. Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm, IEEE Transactions on Computers, v.28 n.9, p.690-691, September 1979 [doi>10.1109/TC.1979.1675439]
• 15: A. Mendelson et al. CMP Implementation in Systems Based on the Intel Core Duo Processor. In Intel Technology Journal, Vol. 10, No. 2, May, 2006.
• 16: H. E. Mizrahi , J. L. Baer , E. D. Lazowska , J. Zahorjan, Introducing memory into the switch elements of multiprocessor interconnection networks, Proceedings of the 16th annual international symposium on Computer architecture, p.158-166, April 1989, Jerusalem, Israel
• 17: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, ACM SIGPLAN Notices, v.31 n.9, p.2-11, Sept. 1996
• 18: S. J. E. Wilton and N. P. Jouppi. An Enhanced Access and Cycle Time Model for on-Chip Caches. DECWestern Research Laboratory, No. 93/5, 1994.
• 19: 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]
• 20: 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
• 21: M. Zhang and K. Asanovic. Victim Migration: Dynamically Adapting between Private and Shared CMP Caches. MIT Technical Report MIT-CSAIL-TR-2005-064, MIT-LCS-TR-1006, October, 2005.
• 22: http://www-128.ibm.com/developerworks/power/library/paexpert1.html
• 23: http://www-flash.stanford.edu/apps/SPLASH/
• 24: http://www.intel.com/multi-core/
• 25: http://www.sun.com/processors/throughput/
• 26: http://www.virtutech.com/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

General Terms:
Design, Theory

Keywords:
CMP, chip-multiprocessor, interconnection network, migration, network-driven computing