Stream chaining: exploiting multiple levels of correlation in data prefetching

ABSTRACT

Data prefetching has long been an important technique to amortize the effects of the memory wall, and is likely to remain so in the current era of multi-core systems. Most prefetchers operate by identifying patterns and correlations in the miss address stream. Separating streams according to the memory access instruction that generates the misses is an effective way of filtering out spurious addresses from predictable streams. On the other hand, by localizing streams based on the memory access instructions, such prefetchers both lose the complete time sequence information of misses and can only issue prefetches for a single memory access instruction at a time.

This paper proposes a novel class of prefetchers based on the idea of linking various localized streams into predictable chains of missing memory access instructions such that the prefetcher can issue prefetches along multiple streams. In this way the prefetcher is not limited to prefetching deeply for a single missing memory access instruction but can instead adaptively prefetch for other memory access instructions closer in time.

Experimental results show that the proposed prefetcher consistently achieves better performance than a state-of-the-art prefetcher -- 10% on average, being only outperformed in very few cases and then by only 2%, and outperforming that prefetcher by as much as 55% -- while consuming the same amount of memory bandwidth.

REFERENCES

• 1: K. Albayraktaroglu , A. Jaleel , Xue Wu , M. Franklin , B. Jacob , Chau-Wen Tseng , D. Yeung, BioBench: A Benchmark Suite of Bioinformatics Applications, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.2-9, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430554]
• 2: 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]
• 3: J. Doweck. "Inside Intel Core Microarchitecture and Smart Memory Access." White paper, Intel Corporation, 2006. http://download.intel.com/technology/architecture/sma.pdf.
• 4: 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
• 5: Zhigang Hu , Stefanos Kaxiras , Margaret Martonosi, Timekeeping in the memory system: predicting and optimizing memory behavior, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 6: Zhigang Hu , Margaret Martonosi , Stefanos Kaxiras, TCP: Tag Correlating Prefetchers, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.317, February 08-12, 2003
• 7: 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
• 8: 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
• 9: Gokul B. Kandiraju , Anand Sivasubramaniam, Going the distance for TLB prefetching: an application-driven study, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 10: An-Chow Lai , Cem Fide , Babak Falsafi, Dead-block prediction & dead-block correlating prefetchers, Proceedings of the 28th annual international symposium on Computer architecture, p.144-154, June 30-July 04, 2001, Göteborg, Sweden
• 11: H. Q. Le , W. J. Starke , J. S. Fields , F. P. O'Connell , D. Q. Nguyen , B. J. Ronchetti , W. M. Sauer , E. M. Schwarz , M. T. Vaden, IBM POWER6 microarchitecture, IBM Journal of Research and Development, v.51 n.6, p.639-662, November 2007
• 12: Kyle J. Nesbit , James E. Smith, Data Cache Prefetching Using a Global History Buffer, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.96, February 14-18, 2004 [doi>10.1109/HPCA.2004.10030]
• 13: Kyle J. Nesbit , Ashutosh S. Dhodapkar , James E. Smith, AC/DC: An Adaptive Data Cache Prefetcher, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.135-145, September 29-October 03, 2004 [doi>10.1109/PACT.2004.4]
• 14: 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
• 15: Daniel Gracia Perez , Gilles Mouchard , Olivier Temam, MicroLib: A Case for the Quantitative Comparison of Micro-Architecture Mechanisms, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.43-54, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.25]
• 16: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos. SESC simulator. http://sesc.sf.net
• 17: P. Shivakumar and N. P. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. WRL Research Report, 2001/2.
• 18: Yan Solihin , Jaejin Lee , Josep Torrellas, Using a user-level memory thread for correlation prefetching, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 19: Stephen Somogyi , Thomas F. Wenisch , Anastassia Ailamaki , Babak Falsafi , Andreas Moshovos, Spatial Memory Streaming, Proceedings of the 33rd annual international symposium on Computer Architecture, p.252-263, June 17-21, 2006
• 20: Stephen Somogyi , Thomas F. Wenisch , Anastasia Ailamaki , Babak Falsafi, Spatio-temporal memory streaming, Proceedings of the 36th annual international symposium on Computer architecture, June 20-24, 2009, Austin, TX, USA
• 21: Viji Srinivasan , Edward S. Davidson , Gary S. Tyson , Mark J. Charney , Thomas R. Puzak, Branch History Guided Instruction Prefetching, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.291, January 20-24, 2001
• 22: Thomas F. Wenisch , Stephen Somogyi , Nikolaos Hardavellas , Jangwoo Kim , Anastassia Ailamaki , Babak Falsafi, Temporal Streaming of Shared Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.222-233, June 04-08, 2005
• 23: Weifeng Zhang , Brad Calder , Dean M. Tullsen, A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework, Proceedings of the International Symposium on Code Generation and Optimization, p.50-64, March 26-29, 2006 [doi>10.1109/CGO.2006.4]

INDEX TERMS

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

General Terms:
Performance

Keywords:
data prefetching