Data prefetch mechanisms

ABSTRACT

The expanding gap between microprocessor and DRAM performance has necessitated the use of increasingly aggressive techniques designed to reduce or hide the latency of main memory access. Although large cache hierarchies have proven to be effective in reducing this latency for the most frequently used data, it is still not uncommon for many programs to spend more than half their run times stalled on memory requests. Data prefetching has been proposed as a technique for hiding the access latency of data referencing patterns that defeat caching strategies. Rather than waiting for a cache miss to initiate a memory fetch, data prefetching anticipates such misses and issues a fetch to the memory system in advance of the actual memory reference. To be effective, prefetching must be implemented in such a way that prefetches are timely, useful, and introduce little overhead. Secondary effects such as cache pollution and increased memory bandwidth requirements must also be taken into consideration. Despite these obstacles, prefetching has the potential to significantly improve overall program execution time by overlapping computation with memory accesses. Prefetching strategies are diverse, and no single strategy has yet been proposed that provides optimal performance. The following survey examines several alternative approaches, and discusses the design tradeoffs involved when implementing a data prefetch strategy.

REFERENCES

• 1: Thomas Alexander , Gershon Kedem, Distributed Prefetch-buffer/Cache Design for High Performance Memory Systems, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.254, February 03-07, 1996
• 2: ANACKER,W.AND WANG, C. P. 1967. Performance evaluation of computing systems with memory hierarchies. IEEE Trans. Comput. 16,6, 764-773.
• 3: Jean-Loup Baer , Tien-Fu Chen, An effective on-chip preloading scheme to reduce data access penalty, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.176-186, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125932]
• 4: David Bernstein , Doron Cohen , Ari Freund, Compiler techniques for data prefetching on the PowerPC, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.19-26, June 27-29, 1995, Limassol, Cyprus
• 5: Doug Burger , James R. Goodman , Alain Kägi, Limited Bandwidth to Affect Processor Design, IEEE Micro, v.17 n.6, p.55-62, November 1997 [doi>10.1109/40.641597]
• 6: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, ACM SIGARCH Computer Architecture News, v.19 n.2, p.40-52, Apr. 1991
• 7: CASMIRA,J.P.AND KAELI, D. R. 1995. Modeling cache pollution. In Proceedings of the Second IASTED Conference on Modeling and Simulation. 123-126.
• 8: CHAN, K. K. 1996. Design of the HP PA 7200 CPU. Hewlett-Packard J. 47, 1, 25-33.
• 9: CHANG,P.Y.,KAELI, D., AND LIU, Y. 1994. Branchdirected data cache prefetching. In Proceedings of Second Workshop on Shared-Memory Multiprocessing Systems.
• 10: Tien-Fu Chen, An effective programmable prefetch engine for on-chip caches, Proceedings of the 28th annual international symposium on Microarchitecture, p.237-242, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 11: 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
• 12: Jean-Loup Baer , Tien-Fu Chen, Effective Hardware-Based Data Prefetching for High-Performance Processors, IEEE Transactions on Computers, v.44 n.5, p.609-623, May 1995 [doi>10.1109/12.381947]
• 13: 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]
• 14: F. Dahlgren , P. Stenstrom, Effectiveness of hardware-based stride and sequential prefetching in shared-memory multiprocessors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.68, January 22-25, 1995
• 15: DAHLGREN, F., DUBOIS, M., AND STENSTROM,P. 1993. Fixed and adaptive sequential prefetching in shared-memory multiprocessors. In Proceedings of the International Conference on Parallel Processing (St. Charles, IL). 56-63.
• 16: FU, B., SAINI, A., AND GELSINGER, P. P. 1989. Performance and microarchitecture of the i486 processor. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA). 182-187.
• 17: 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
• 18: 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
• 19: GORNISH,E.H.AND VEIDENBAUM, A. V. 1994. An integrated hardware/software scheme for shared-memory multiprocessors. In Proceedings of International Conference on Parallel Processing (St. Charles, IL). 281-284.
• 20: Edward H. Gornish , Elana D. Granston , Alexander V. Veidenbaum, Compiler-directed data prefetching in multiprocessors with memory hierarchies, Proceedings of the 4th international conference on Supercomputing, p.354-368, June 11-15, 1990, Amsterdam, The Netherlands
• 21: HARRISON,L.AND MEHROTRA, S. 1994. A data prefetch mechanism for accelerating general computation. 1351. University of Illinois at Urbana-Champaign, Champaign, IL.
• 22: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 23: 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
• 24: Alexander C. Klaiber , Henry M. Levy, An architecture for software-controlled data prefetching, ACM SIGARCH Computer Architecture News, v.19 n.3, p.43-53, May 1991
• 25: 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
• 26: David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993 [doi>10.1145/158439.158907]
• 27: Mikko H. Lipasti , William J. Schmidt , Steven R. Kunkel , Robert R. Roediger, SPAID: software prefetching in pointer- and call-intensive environments, Proceedings of the 28th annual international symposium on Microarchitecture, p.231-236, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 28: Yue Liu , David R. Kaeli, Branch-Directed and Stride-Based Data Cache Prefetching, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.225-230, October 07-09, 1996
• 29: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, ACM SIGOPS Operating Systems Review, v.30 n.5, p.222-233, Dec. 1996
• 30: Todd Mowry , Anoop Gupta, Tolerating latency through software-controlled prefetching in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.12 n.2, p.87-106, June 1991 [doi>10.1016/0743-7315(91)90014-Z]
• 31: 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
• 32: OBERLIN, S., KESSLER, R., SCOTT, S., AND THORSON, G. 1996. Cray T3E architecture overview. Cray Supercomputers, Chippewa Falls, MN.
• 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: R. Hugo Patterson , Garth A. Gibson, Exposing I/O concurrency with informed prefetching, Proceedings of the third international conference on on Parallel and distributed information systems, p.7-16, October 1994, Autin, Texas, United States
• 35: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 36: Steven Przybylski, The performance impact of block sizes and fetch strategies, Proceedings of the 17th annual international symposium on Computer Architecture, p.160-169, May 28-31, 1990, Seattle, Washington, United States
• 37: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 38: Vatsa Santhanam , Edward H. Gornish , Wei-Chung Hsu, Data prefetching on the HP PA-8000, Proceedings of the 24th annual international symposium on Computer architecture, p.264-273, June 01-04, 1997, Denver, Colorado, United States
• 39: Ivan Sklenar, Prefetch unit for vector operations on scalar computers (abstract), Proceedings of the 19th annual international symposium on Computer architecture, p.430, May 19-21, 1992, Queensland, Australia
• 40: SMITH, A. J. 1978. Sequential program prefetching in memory hierarchies. IEEE Computer 11, 12, 7-21.
• 41: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 42: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 43: A Compiler-Assisted Data Prefetch Controller, Proceedings of the 1999 IEEE International Conference on Computer Design, p.372, October 10-13, 1999
• 44: Steven P. VanderWiel , David J. Lilja, When Caches Aren't Enough: Data Prefetching Techniques, Computer, v.30 n.7, p.23-30, July 1997 [doi>10.1109/2.596622]
• 45: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 46: YOUNG,H.C.AND SHEKITA, E. J. 1993. An intelligent I-cache prefetch mechanism. In Proceedings of the International Conference on Computer Design (ICCD'93, Cambridge, MA). IEEE Computer Society Press, Los Alamitos, CA, 44-49.
• 47: Zheng Zhang , Josep Torrellas, Speeding up irregular applications in shared-memory multiprocessors: memory binding and group prefetching, Proceedings of the 22nd annual international symposium on Computer architecture, p.188-199, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

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

Additional Classification:
  B. Hardware

General Terms:
Design, Performance

Keywords:
memory latency, prefetching