| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Prefetch Taxonomy
February 2004 (vol. 53 no. 2)
pp. 126-140
Abstract—The growing difference between processor and main memory cycle time demands the use of aggressive prefetch algorithms to reduce the effective memory access latency. However, prefetching can significantly increase memory traffic and unsuccessful prefetches may pollute the cache. Metrics such as coverage and accuracy result from a simplistic classification of individual prefetches as “good” or “bad.” They do not capture the full effect of each prefetch and, hence, do not accurately reflect the quality of the prefetch algorithm. Gross statistics such as changes in the number of misses, total traffic, and IPC are not attributable to individual prefetches. Such gross metrics are therefore useful only for ranking existing prefetch algorithms; they do not evaluate the effect of individual prefetches so that an algorithm might be tuned. In this paper, we introduce a new, accurate, and complete taxonomy, called the Prefetch Traffic and Miss Taxonomy (PTMT), for classifying each prefetch by precisely accounting for the difference in traffic and misses it generates, either directly or indirectly. We illustrate the use of PTMT by evaluating two data prefetch algorithms.
[1] 126 J. Bennett and M. Flynn, Prediction Caches for Superscalar Processors Proc. 30th Ann. Int'l Symp. Microarchitecture, pp. 81-91, Dec. 1997.[2] D. Burger and T. Austin, The SimpleScalar Tool Set, Version 2.0 Technical Report TR 1342, Univ. of Wisconsin, June 1997.[3] D. Callahan, K. Kennedy, and A. Porterfield, Software Prefetching Proc. Fourth Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 40-52, Apr. 1991.[4] P. Cao, E. Felton, A. Karlin, and K. Li, A Study of Integrated Prefetching and Caching Strategies Proc. ACM SIGMETRICS, pp. 188-196, June 1995.[5] M. Charney, Correlation-Based Hardware Prefetching PhD dissertation, Cornell Univ., Aug. 1995.[6] M. Charney and T. Puzak, Prefetching and Memory System Behavior of the SPEC95 Benchmark Suite IBM J. Research and Development, vol. 41, no. 3, pp. 265-286, May 1997.[7] T. Chen and J. Baer, Reducing Memory Latency via Non-Blocking and Prefetching Caches Proc. Fifth Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 51-61, Oct. 1992.[8] T.-F. Chen and J.-L. Baer, "A Performance Study of Software and Hardware Data Prefetching Schemes," Proc. 21st Int'l Symp. Computer Architecture, pp. 223-232, 1994.[9] W. Chen, S. Mahlke, P. Chang, and W. Hwu, Data Access Microarchitectures for Superscalar Processors with Compiler-Assisted Data Prefetching Proc. 24th Int'l Symp. Microarchitecture, pp. 69-73, Nov. 1991.[10] J.D. Gindele, Buffer Block Prefetching Method IBM Technical Disclosure Bull., vol. 20, no. 2, pp. 696-697, July 1977.[11] D. Joseph and D. Grunwald, Prefetching Using Markov Predictors Proc. 24th Int'l Symp. Computer Architecture, pp. 252-263, May 1997.[12] N.P. Jouppi, “Improving Direct-Mapped Cache Performance by the Addition of a Small Fully Associative Cache and Prefetch Buffers,” Proc. 17th Int'l Symp. Computer Architecture, pp. 364-373, May 1990.[13] A. Klaiber and H. Levy, “An Architecture for Software-Controlled Data Prefetching,” Proc. 18th Ann. Int'l Symp. Computer Architecture, pp. 43-53, May 1991.[14] M.H. Lipasti, W.J. Schmidt, S.R. Kunkel,, and R.R. Roediger, “SPAID: Software Prefetching in Pointer- and Call-Intensive Environments,” Proc. 28th Ann. ACM/IEEE Int'l Symp. Microarchitecture, pp. 231-236 1995.[15] C.-K. Luk and T. Mowry, Compiler Based Prefetching for Recursive Data Structures Proc. Seventh Int'l Conf. Architectural Support for Programming Languages and Operating Systems, pp. 222-233, Oct. 1996.[16] S. Mehrotra and L. Harrison, Examination of a Memory Access Classification Scheme for Pointer-Intensive and Numeric Programs Proc. 10th Int'l Conf. Supercomputing, pp. 133-139, May 1996.[17] J. Pomerene, T. Puzak, R. Rechtschaffen, and F. Sparacio, Prefetching System for a Cache Having a Second Directory for Sequentially Accessed Blocks US Patent 4,807,110, Feb. 1989.[18] A. Roth and G. Sohi, "Effective Jump-Pointer Prefetching for Linked Data Structures," Proc. 26th Ann. Int'l Symp. Computer Architecture, IEEE Press, Piscataway, N.J., 1999, pp. 111-121.[19] A. Smith, Cache Memories ACM Computing Surveys, pp. 473-530, Sept. 1982.[20] V. Srinivasan, Hardware Solutions to Reduce Effective Memory Access Time PhD dissertation, Univ. of Michigan, Jan. 2001.[21] Standard Performance Evaluation Corp., CPU2000 documentation http://www.spec.org/osg/cpu2000docs, 2000.[22] Transaction Processing Performance Council http:/www. tpc.org, 2003.[23] S. Vlaovic, E.S. Davidson, and G.S. Tyson, Improving BTB Performance in the Presence of DLLs Proc. 33rd Int'l Symp. Microarchitecture, pp. 77-86, Dec. 2000.
Index Terms:
Prefetch algorithms, cache memory systems.
Citation:
Viji Srinivasan, Edward S. Davidson, Gary S. Tyson, "A Prefetch Taxonomy," IEEE Transactions on Computers, vol. 53, no. 2, pp. 126-140, Feb. 2004, doi:10.1109/TC.2004.1261824
