Runtime identification of cache conflict misses: The adaptive miss buffer

ABSTRACT

This paper describes the miss classification table, a simple mechanism that enables the processor or memory controller to identify each cache miss as either a conflict miss or a capacity (non-conflict) miss. The miss classification table works by storing part of the tag of the most recently evicted line of a cache set. If the next miss to that cache set has a matching tag, it is identified as a conflict miss. This technique correctly identifies 88% of misses.Several applications of this information are demonstrated, including improvements to victim caching, next-line prefetching, cache exclusion, and a pseudo-associative cache. This paper also presents the adaptive miss buffer (AMB), which combines several of these techniques, targeting each miss with the most appropriate optimization, all within a single small miss buffer. The AMB's combination of techniques achieves 16% better performance than any single technique alone.

REFERENCES

• 1: Anant Agarwal , Stephen D. Pudar, Column-associative caches: a technique for reducing the miss rate of direct-mapped caches, Proceedings of the 20th annual international symposium on Computer architecture, p.179-190, May 16-19, 1993, San Diego, California, United States
• 2: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• 3: 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]
• 4: Jamison D. Collins , Dean M. Tullsen, Hardware identification of cache conflict misses, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.126-135, November 16-18, 1999, Haifa, Israel
• 5: Alan L. Cox , Robert J. Fowler, Adaptive cache coherency for detecting migratory shared data, Proceedings of the 20th annual international symposium on Computer architecture, p.98-108, May 16-19, 1993, San Diego, California, United States
• 6: 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]
• 7: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 8: Hiroaki Hirata , Kozo Kimura , Satoshi Nagamine , Yoshiyuki Mochizuki , Akio Nishimura , Yoshimori Nakase , Teiji Nishizawa, An elementary processor architecture with simultaneous instruction issuing from multiple threads, Proceedings of the 19th annual international symposium on Computer architecture, p.136-145, May 19-21, 1992, Queensland, Australia
• 9: INTEL, C. 2000. In Itanium Processor Microarchitecture Reference for Software Optimization (Aug. 2000), pp. ftp://download.intel.com/design/IA-64/Downloads/24547401.pdf.
• 10: INTEL, C. 2001. In Intel Pentium 4 Processor in the 423-pin Package at 1.30 GHz, 1.40GHz, and 1.50 GHz (Jan. 2001), pp. ftp://download.intel.com/ design/ Pentium4/ datashts/24919802.pdf.
• 11: 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
• 12: Doug Joseph , Dirk Grunwald, Prefetching Using Markov Predictors, IEEE Transactions on Computers, v.48 n.2, p.121-133, February 1999 [doi>10.1109/12.752653]
• 13: 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
• 14: MILUTINOVIC, V., TOMASEVIC, M., MARKOVI,B.,AND TREMBLAY, M. 1996. A new cache architecture concept: the split temporal/spatial cache. In Proceedings of the 8th Mediterranean Electrotechnical Conference (May 1996), 1108-1111.
• 15: Basem A. Nayfeh , Lance Hammond , Kunle Olukotun, Evaluation of design alternatives for a multiprocessor microprocessor, Proceedings of the 23rd annual international symposium on Computer architecture, p.67-77, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 16: Thomas Roberts Puzak, Analysis of cache replacement-algorithms, 1985
• 17: 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
• 18: ROMER, T. H., LEE, D., BERSHAD,B.N.,AND CHEN, J. B. 1994. Dynamic page mapping policies for cache conflict resolution on standard hardware. In Proceedings of the First Annual Symposium on Operating Systems Design and Implementation (Nov. 1994), 255-266.
• 19: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 20: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 21: 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
• 22: SONG, P. 1997. Ultrasparc-3 aims at mp servers. Microprocessor Report 11, 14 (Oct.), 29-34.
• 23: Per Stenström , Mats Brorsson , Lars Sandberg, An adaptive cache coherence protocol optimized for migratory sharing, Proceedings of the 20th annual international symposium on Computer architecture, p.109-118, May 16-19, 1993, San Diego, California, United States
• 24: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 25: TULLSEN, D. M. 1996. Simulation and modeling of a simultaneous multithreading processor. In Proceedings of the 22nd Annual Computer Measurement Group Conference (Dec. 1996), 384-393.
• 26: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 27: 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.m Miscellaneous

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Measurement techniques

General Terms:
Design, Performance

Keywords:
Cache architecture, adaptive miss buffer, cache exclusion, conflict misses, prefetching, victim cache