Memory bandwidth limitations of future microprocessors

ABSTRACT

This paper makes the case that pin bandwidth will be a critical consideration for future microprocessors. We show that many of the techniques used to tolerate growing memory latencies do so at the expense of increased bandwidth requirements. Using a decomposition of execution time, we show that for modern processors that employ aggressive memory latency tolerance techniques, wasted cycles due to insufficient bandwidth generally exceed those due to raw memory latencies. Given the importance of maximizing memory bandwidth, we calculate effective pin bandwidth, then estimate optimal effective pin bandwidth. We measure these quantities by determining the amount by which both caches and minimal-traffic caches filter accesses to the lower levels of the memory hierarchy. We see that there is a gap that can exceed two orders of magnitude between the total memory traffic generated by caches and the minimal-traffic caches---implying that the potential exists to increase effective pin bandwidth substantially. We decompose this traffic gap into four factors, and show they contribute quite differently to traffic reduction for different benchmarks. We conclude that, in the short term, pin bandwidth limitations will make more complex on-chip caches cost-effective. For example, flexible caches may allow individual applications to choose from a range of caching policies. In the long term, we predict that off-chip accesses will be so expensive that all system memory will reside on one or more processor chips.

REFERENCES

• 1: Santosh G. Abraham , Rabin A. Sugumar , Daniel Windheiser , B. R. Rau , Rajiv Gupta, Predictability of load/store instruction latencies, Proceedings of the 26th annual international symposium on Microarchitecture, p.139-152, December 01-03, 1993, Austin, Texas, United States
• 2: Forest Baskett. Keynote address. International Symposium on Shared Memory MuItiprocessing, April 1991.
• 3: L.A. Belady A Study of Replacement Algorithms for a Virtual- Storage Computer. IBM Systems Journal, 5(2):78-101, I966.
• 4: Doug Burger and Todd M. Austin. Evaluating Future Microprocessors: the SimpleScalar Tool Set. Technical Report 1300, Computer Sciences Department, University of Wisconsin, Madison, WI, April 1996.
• 5: Douglas C. Burger, Alain Kagi, and James R. Goodman. The Declining Effectiveness of Dynamic Caching for General-Purpose Microprocessors. Technical Report 1261, Computer Sciences Department, University of Wisconsin, Madison, WI, January 1995.
• 6: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
• 7: T.-F. Chen , J.-L. Baer, A performance study of software and hardware data prefetching schemes, Proceedings of the 21ST annual international symposium on Computer architecture, p.223-232, April 18-21, 1994, Chicago, Illinois, United States
• 8: William Y. Chen , Scott A. Mahlke , Pohua P. Chang , Wen-mei W. Hwu, Data access microarchitectures for superscalar processors with compiler-assisted data prefetching, Proceedings of the 24th annual international symposium on Microarchitecture, p.69-73, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123478]
• 9: D. Citron , L. Rudolph, Creating a wider bus using caching techniques, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.90, January 22-25, 1995
• 10: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace scheduling compiler, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.180-192, October 1987, Palo Alto, California, United States
• 11: Stefanos Damianakis, Kai Li, and Anne Rogers. An Analysis of a Combined Hardware-Software Mechanism for Speculative Loads. Technical Report TR-455-94, Princeton University, Princeton, NJ, April 1994.
• 12: Matthew Farrens , Arvin Park, Dynamic base register caching: a technique for reducing address bus width, Proceedings of the 18th annual international symposium on Computer architecture, p.128-137, May 27-30, 1991, Toronto, Ontario, Canada
• 13: John W. C. Fu , Janak H. Patel, Data prefetching in multiprocessor vector cache memories, Proceedings of the 18th annual international symposium on Computer architecture, p.54-63, May 27-30, 1991, Toronto, Ontario, Canada
• 14: John W. C. Fu , Janak H. Patel , Bob L. Janssens, Stride directed prefetching in scalar processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.102-110, December 01-04, 1992, Portland, Oregon, United States
• 15: Hector Garcia-Molina, Richard J. Lipton, and Jacobo Valdes. A Massive Memory Machine. IEEE Transactions on Computers, C- 33(5):391-399, May 1984.
• 16: Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Hiding memory latency using dynamic scheduling in shared-memory multiprocessors, Proceedings of the 19th annual international symposium on Computer architecture, p.22-33, May 19-21, 1992, Queensland, Australia
• 17: J.D. Gindele. Buffer Block Prefetching Method. IBM Tech. Disclosure Bull., 20(2):696--697, July 1977.
• 18: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 19: Mark D. Hill , James R. Larus , Alvin R. Lebeck , Madhusudhan Talluri , David A. Wood, Wisconsin Architectural Research Tool Set, ACM SIGARCH Computer Architecture News, v.21 n.4, p.8-10, Sept. 1993 [doi>10.1145/165496.165500]
• 20: Mark D. Hill , Alan Jay Smith, Experimental evaluation of on-chip microprocessor cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.158-166, January 1984
• 21: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 22: L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
• 23: Andrew S. Huang , John P. Shen, A limit study of local memory requirements using value reuse profiles, Proceedings of the 28th annual international symposium on Microarchitecture, p.71-81, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 24: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 25: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 26: Alexander C. Klaiber , Henry M. Levy, An architecture for software-controlled data prefetching, Proceedings of the 18th annual international symposium on Computer architecture, p.43-53, May 27-30, 1991, Toronto, Ontario, Canada
• 27: L. I. Kontothanassis , R. A. Sugumar , G. J. Faanes , J. E. Smith , M. L. Scott, Cache performance in vector supercomputers, Proceedings of the 1994 conference on Supercomputing, p.255-264, December 1994, Washington, D.C., United States
• 28: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 29: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 30: James Laudon , Anoop Gupta , Mark Horowitz, Interleaving: a multithreading technique targeting multiprocessors and workstations, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.308-318, October 05-07, 1994, San Jose, California, United States
• 31: G. D. McNiven , E. S. Davidson, Analysis of memory referencing behavior for design of local memories, Proceedings of the 15th Annual International Symposium on Computer architecture, p.56-63, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 32: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 33: S. Palacharla , R. E. Kessler, Evaluating stream buffers as a secondary cache replacement, Proceedings of the 21ST annual international symposium on Computer architecture, p.24-33, April 18-21, 1994, Chicago, Illinois, United States
• 34: Betty Prince, Memory in the fast lane, IEEE Spectrum, v.31 n.2, p.38-41, Feb. 1994 [doi>10.1109/6.259491]
• 35: Anne Rogers , Kai Li, Software support for speculative loads, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.38-50, October 12-15, 1992, Boston, Massachusetts, United States
• 36: Edward Rothberg , Jaswinder Pal Singh , Anoop Gupta, Working sets, cache sizes, and node granularity issues for large-scale multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.14-26, May 16-19, 1993, San Diego, California, United States
• 37: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 38: Burton J. Smith. Architecture and Applications of the HEP Multiprocessor Computer System. In Real-Time Signal Processing IV, pages 241-248, 1981.
• 39: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 40: 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
• 41: Gurindar S. Sohi, Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computers, IEEE Transactions on Computers, v.39 n.3, p.349-359, March 1990 [doi>10.1109/12.48865]
• 42: Standard Performance Evaluation Corporation. SPEC Newsletter, Fairfax, Virginia, December 1991.
• 43: Standard Performance Evaluation Corporation. SPEC Newsletter, Fairfax, Virginia, September 1995.
• 44: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 45: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Measurement, Theory