Interconnect design considerations for large NUCA caches

ABSTRACT

The ever increasing sizes of on-chip caches and the growing domination of wire delay necessitate significant changes to cache hierarchy design methodologies. Many recent proposals advocate splitting the cache into a large number of banks and employing a network-on-chip (NoC) to allow fast access to nearby banks (referred to as Non-Uniform Cache Architectures--NUCA). Most studies on NUCA organizations have assumed a generic NoC and focused on logical policies for cache block placement, movement, and search. Since wire/router delay and power are major limiting factors in modern processors, this work focuses on interconnect design and its influence on NUCA performance and power. We extend the widely-used CACTI cache modeling tool to take network design parameters into account. With these overheads appropriately accounted for, the optimal cache organization is typically very different from that assumed in prior NUCA studies. To alleviate the interconnect delay bottleneck, we propose novel cache access optimizations that introduce heterogeneity within the inter-bank network. The careful consideration of interconnect choices for a large cache results in a 51% performance improvement over a baseline generic NoC and the introduction of heterogeneity within the network yields an additional 11-15% performance improvement.

REFERENCES

• 1: H. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, 1990.
• 2: Rajeev Balasubramonian , Naveen Muralimanohar , Karthik Ramani , Venkatanand Venkatachalapathy, Microarchitectural Wire Management for Performance and Power in Partitioned Architectures, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.28-39, February 12-16, 2005 [doi>10.1109/HPCA.2005.21]
• 3: K. Banerjee and A. Mehrotra. A Power-optimal Repeater Insertion Methodology for Global Interconnects in Nanometer Designs. IEEE Transactions on Electron Devices, 49(11):2001--2007, November 2002.
• 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, TLC: Transmission Line Caches, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.43, December 03-05, 2003
• 6: 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]
• 7: D. Burger and T. Austin. The Simplescalar Toolset, Version 2.0. Technical Report TR-97-1342, University of Wisconsin-Madison, June 1997.
• 8: 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
• 9: R. Chang, N. Talwalkar, C. Yue, and S. Wong. Near Speed-of-Light Signaling Over On-Chip Electrical Interconnects. IEEE Journal of Solid-State Circuits, 38(5):834--838, May 2003.
• 10: Liqun Cheng , Naveen Muralimanohar , Karthik Ramani , Rajeev Balasubramonian , John B. Carter, Interconnect-Aware Coherence Protocols for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.339-351, June 17-21, 2006
• 11: 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
• 12: 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
• 13: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 14: William J. Dally , John W. Poulton, Digital systems engineering, Cambridge University Press, New York, NY, 1998
• 15: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 16: R. Ho, K. Mai, and M. Horowitz. The Future of Wires. Proceedings of the IEEE, Vol.89, No.4, April 2001.
• 17: M. Hrishikesh, D. Burger, S. Keckler, P. Shivakumar, N.P. Jouppi, and K.I. Farkas. The Optimal Logic Depth Per Pipeline Stage is 6 to 8 FO4 Inverter Delays.
• 18: 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]
• 19: R. E. Kessler , R. Jooss , A. Lebeck , M. D. Hill, Inexpensive implementations of set-associativity, Proceedings of the 16th annual international symposium on Computer architecture, p.131-139, April 1989, Jerusalem, Israel
• 20: 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
• 21: Rakesh Kumar , Victor Zyuban , Dean M. Tullsen, Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.408-419, June 04-08, 2005
• 22: Feihui Li , Chrysostomos Nicopoulos , Thomas Richardson , Yuan Xie , Vijaykrishnan Narayanan , Mahmut Kandemir, Design and Management of 3D Chip Multiprocessors Using Network-in-Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.130-141, June 17-21, 2006
• 23: Gian Luca Loi , Banit Agrawal , Navin Srivastava , Sheng-Chih Lin , Timothy Sherwood , Kaustav Banerjee, A thermally-aware performance analysis of vertically integrated (3-D) processor-memory hierarchy, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147160]
• 24: Nir Magen , Avinoam Kolodny , Uri Weiser , Nachum Shamir, Interconnect-power dissipation in a microprocessor, Proceedings of the 2004 international workshop on System level interconnect prediction, February 14-15, 2004, Paris, France [doi>10.1145/966747.966750]
• 25: Doug Matzke, Will Physical Scalability Sabotage Performance Gains?, Computer, v.30 n.9, p.37-39, September 1997 [doi>10.1109/2.612245]
• 26: Cameron McNairy , Rohit Bhatia, Montecito: A Dual-Core, Dual-Thread Itanium Processor, IEEE Micro, v.25 n.2, p.10-20, March 2005 [doi>10.1109/MM.2005.34]
• 27: Shubhendu S. Mukherjee , Peter Bannon , Steven Lang , Aaron Spink , David Webb, The Alpha 21364 Network Architecture, IEEE Micro, v.22 n.1, p.26-35, January 2002 [doi>10.1109/40.988687]
• 28: Robert Mullins , Andrew West , Simon Moore, Low-Latency Virtual-Channel Routers for On-Chip Networks, Proceedings of the 31st annual international symposium on Computer architecture, p.188, June 19-23, 2004, München, Germany
• 29: Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001
• 30: Li-Shiuan Peh , William J. Dally, A Delay Model for Router Microarchitectures, IEEE Micro, v.21 n.1, p.26-34, January 2001 [doi>10.1109/40.903059]
• 31: Semiconductor Industry Association. International Technology Roadmap for Semiconductors 2005. http://www.itrs.net/Links/2005ITRS/Home2005.htm.
• 32: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 33: P. Shivakumar and N.P. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. Technical Report TN-2001/2, Compaq Western Research Laboratory, August 2001.
• 34: Evan Speight , Hazim Shafi , Lixin Zhang , Ram Rajamony, Adaptive Mechanisms and Policies for Managing Cache Hierarchies in Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.346-356, June 04-08, 2005
• 35: Hang-Sheng Wang , Li-Shiuan Peh , Sharad Malik, A Power Model for Routers: Modeling Alpha 21364 and InfiniBand Routers, IEEE Micro, v.23 n.1, p.26-35, January 2003 [doi>10.1109/MM.2003.1179895]
• 36: Hang-Sheng Wang , Xinping Zhu , Li-Shiuan Peh , Sharad Malik, Orion: a power-performance simulator for interconnection networks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 37: 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

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Design, Performance

Keywords:
cache models, interconnect, memory hierarchies, network-on-chip, non-uniform cache architecture