An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches

ABSTRACT

Growing wire delays will force substantive changes in the designs of large caches. Traditional cache architectures assume that each level in the cache hierarchy has a single, uniform access time. Increases in on-chip communication delays will make the hit time of large on-chip caches a function of a line's physical location within the cache. Consequently, cache access times will become a continuum of latencies rather than a single discrete latency. This non-uniformity can be exploited to provide faster access to cache lines in the portions of the cache that reside closer to the processor. In this paper, we evaluate a series of cache designs that provides fast hits to multi-megabyte cache memories. We first propose physical designs for these Non-Uniform Cache Architectures (NUCAs). We extend these physical designs with logical policies that allow important data to migrate toward the processor within the same level of the cache. We show that, for multi-megabyte level-two caches, an adaptive, dynamic NUCA design achieves 1.5 times the IPC of a Uniform Cache Architecture of any size, outperforms the best static NUCA scheme by 11%, outperforms the best three-level hierarchy--while using less silicon area--by 13%, and comes within 13% of an ideal minimal hit latency solution.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 3: D. Bailey, J. Barton, T. Lasinski, and H. Simon. The NAS parallel benchmarks. Technical Report RNR-91-002 Revision 2, NASA Ames Research Laboratory, Mountain View, CA, August 1991.
• 4: François Bodin , André Seznec, Skewed associativity enhances performance predictability, Proceedings of the 22nd annual international symposium on Computer architecture, p.265-274, June 22-24, 1995, S. Margherita Ligure, Italy
• 5: Fredrik Dahlgren , Per Stenström, On reconfigurable on-chip data caches, Proceedings of the 24th annual international symposium on Microarchitecture, p.189-198, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123504]
• 6: R. Desikan, D. Burger, S. W. Keckler, and T. M. Austin. Sim-alpha: A validated execution-driven alpha 21264 simulator. Technical Report TR-01-23, Department of Computer Sciences, University of Texas at Austin, 2001.
• 7: Antonio González , Carlos Aliagas , Mateo Valero, A data cache with multiple caching strategies tuned to different types of locality, Proceedings of the 9th international conference on Supercomputing, p.338-347, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224622]
• 8: L. Gwennap. Alpha 21364 to ease memory bottleneck. Microprocessor Report, 12(14), October 1998.
• 9: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 10: J. M. Hill and J. Lachman. A 900MHz 2.25 MB cache with on-chip CPU now in Cu SOI. In Proceedings of the IEEE International Solid-State Circuits Conference, pages 171-177, February 2001.
• 11: M. Horowitz, R. Ho, and K. Mai. The future of wires. In Seminconductor Research Corporation Workshop on Interconnects for Systems on a Chip, May 1999.
• 12: M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, p.14, May 25-29, 2002, Anchorage, Alaska
• 13: Jaehyuk Huh , Doug Burger , Stephen W. Keckler, Exploring the Design Space of Future CMPs, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.199-210, September 08-12, 2001
• 14: J. Rubinstein, P. Penfield, and M. A. Horowitz. Signal delay in RC tree networks. IEEE Transactions on Computer-Aided Design, CAD-2(3):202-211, 1983.
• 15: Teresa L. Johnson , Wen-mei W. Hwu, Run-time adaptive cache hierarchy management via reference analysis, Proceedings of the 24th annual international symposium on Computer architecture, p.315-326, June 01-04, 1997, Denver, Colorado, United States
• 16: N. Jouppi and S. Wilton. An enhanced access and cycle time model for on-chip caches. Technical Report TR-93-5, Compaq WRL, July 1994.
• 17: Richard Eugene Kessler, Analysis of multi-megabyte secondary CPU cache memories, University of Wisconsin at Madison, Madison, WI, 1992
• 18: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 19: R. E. Kessler , M. D. Hill , D. A. Wood, A Comparison of Trace-Sampling Techniques for Multi-Megabyte Caches, IEEE Transactions on Computers, v.43 n.6, p.664-675, June 1994 [doi>10.1109/12.286300]
• 20: 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
• 21: K.-F. Lee, H.-W. Hon, and R. Reddy. An overview of the SPHINX speech recognition system. IEEE Transactions on Acoustics, Speech and Signal Processing, 38(1):35-44, 1990.
• 22: Doug Matzke, Will Physical Scalability Sabotage Performance Gains?, Computer, v.30 n.9, p.37-39, September 1997 [doi>10.1109/2.612245]
• 23: H. Pilo, A. Allen, J. Covino, P. Hansen, S. Lamphier, C. Murphy, T. Traver, and P. Yee. An 833MHz 1.5w 18Mb CMOS SRAM with 1.67Gb/s/pin. In Proceedings of the 2000 IEEE International Solid-State Circuits Conference, pages 266-267, February 2000.
• 24: Michael D. Powell , Amit Agarwal , T. N. Vijaykumar , Babak Falsafi , Kaushik Roy, Reducing set-associative cache energy via way-prediction and selective direct-mapping, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 25: Steven A. Przybylski , John L. Hennessy, Performance directed memory hierarchy design, 1988
• 26: The national technology roadmap for semiconductors. Semiconductor Industry Association, 1999.
• 27: P. Shivakumar and N. P. Jouppi. Cacti 3.0: An integrated cache timing, power and area model. Technical report, Compaq Computer Corporation, August 2001.
• 28: Kimming So , Rudolph N. Rechtschaffen, Cache Operations by MRU Change, IEEE Transactions on Computers, v.37 n.6, p.700-709, June 1988 [doi>10.1109/12.2208]
• 29: Gurindar S. Sohi , Manoj Franklin, High-bandwidth data memory systems for superscalar processors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.53-62, April 08-11, 1991, Santa Clara, California, United States
• 30: Standard Performance Evaluation Corporation. SPEC Newsletter, Fairfax, VA, September 2000.
• 31: Gary Tyson , Matthew Farrens , John Matthews , Andrew R. Pleszkun, A modified approach to data cache management, Proceedings of the 28th annual international symposium on Microarchitecture, p.93-103, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 32: Kenneth M. Wilson , Kunle Olukotun, Designing high bandwidth on-chip caches, Proceedings of the 24th annual international symposium on Computer architecture, p.121-132, June 01-04, 1997, Denver, Colorado, United States
• 33: S. Wilton and N. Jouppi. Cacti: An enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits, 31(5):677-688, May 1996.