Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers

ABSTRACT

Projections of computer technology forecast processors with peak performance of 1,000 MIPS in the relatively near future. These processors could easily lose half or more of their performance in the memory hierarchy if the hierarchy design is based on conventional caching techniques. This paper presents hardware techniques to improve the performance of caches. Miss caching places a small fully-associative cache between a cache and its refill path. Misses in the cache that hit in the miss cache have only a one cycle miss penalty, as opposed to a many cycle miss penalty without the miss cache. Small miss caches of 2 to 5 entries are shown to be very effective in removing mapping conflict misses in first-level direct-mapped caches. Victim caching is an improvement to miss caching that loads the small fully-associative cache with the victim of a miss and not the requested line. Small victim caches of 1 to 5 entries are even more effective at removing conflict misses than miss caching. Stream buffers prefetch cache lines starting at a cache miss address. The prefetched data is placed in the buffer and not in the cache. Stream buffers are useful in removing capacity and compulsory cache misses, as well as some instruction cache conflict misses. Stream buffers are more effective than previously investigated prefetch techniques at using the next slower level in the memory hierarchy when it is pipelined. An extension to the basic stream buffer, called multi-way stream buffers, is introduced. Multi-way stream buffers are useful for prefetching along multiple intertwined data reference streams. Together, victim caches and stream buffers reduce the miss rate of the first level in the cache hierarchy by a factor of two to three on a set of six large benchmarks.

REFERENCES

• 1: J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, Proceedings of the 15th Annual International Symposium on Computer architecture, p.73-80, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 2: Borg, Anita, Kessler, Rick E., Lazana, Georgia, and Wall, David W. Long Address Traces from RISC Machines: Generation and Analysis. Tech. Rept. 89114, Digital Equipment Corporation Western Research Laboratory, September, 1989.
• 3: Digital Equipment Corporation, Inc. VAX Hardware Handbook, volume I - 1984. Maynard, Massachusetts, 1984.
• 4: Joel S. Emer , Douglas W. Clark, A Characterization of Processor Performance in the vax-11/780, Proceedings of the 11th annual international symposium on Computer architecture, p.301-310, January 1984
• 5: Eustace, Alan. Private communication.
• 6: M. K. Farrens , a. R. Pleszkun, Improving performance of small on-chip instruction caches, Proceedings of the 16th annual international symposium on Computer architecture, p.234-241, April 1989, Jerusalem, Israel
• 7: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 8: N. P. Jouppi , D. W. Wall, Available instruction-level parallelism for superscalar and superpipelined machines, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.272-282, April 03-06, 1989, Boston, Massachusetts, United States
• 9: N. P. Jouppi, Architectural and organizational tradeoffs in the design of the MultiTitan CPU, Proceedings of the 16th annual international symposium on Computer architecture, p.281-289, April 1989, Jerusalem, Israel
• 10: Nielsen, Michael J. K. Titan System Manual. Tech. Rept. 86/l, Digital Equipment Corporation Western Research Laboratory, September, 1986.
• 11: Ousterhout, John. Why Aren't Operating Systems Getting Faster As Fast As Hardware? Tech. Rept. Technote 11, Digital Equipment Corporation Western Research Laboratory, October, 1989.
• 12: Smith, Alan J. "Sequential program prefetching in memory hierarchies. "IEEE Computer 11, 12 (December 1978), 7-21.
• 13: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

General Terms:
Experimentation, Performance