Bloom filtering cache misses for accurate data speculation and prefetching

ABSTRACT

A processor must know a load instruction's latency to schedule the load's dependent instructions at the correct time. Unfortunately, modern processors do not know this latency until well after the dependent instructions should have been scheduled to avoid pipeline bubbles between themselves and the load. One solution to this problem is to predict the load's latency, by predicting whether the load will hit or miss in the data cache. Existing cache hit/miss predictors, however, can only correctly predict about 50% of cache misses.This paper introduces a new hit/miss predictor that uses a Bloom Filter to identify cache misses early in the pipeline. This early identification of cache misses allows the processor to more accurately schedule instructions that are dependent on loads and to more precisely prefetch data into the cache. Simulations using a modified SimpleScalar model show that the proposed Bloom Filter is nearly perfect, with a prediction accuracy greater than 99% for the SPECint2000 benchmarks. IPC (Instructions Per Cycle) performance improved by 19% over a processor that delayed the scheduling of instructions dependent on a load until the load latency was known, and by 6% and 7% over a processor that always predicted a load would hit the cache and with a counter-based hit/miss predictor respectively. This IPC reaches 99.7% of the IPC of a processor with perfect scheduling.

REFERENCES

• 1: Compaq Computer Corporation. Alpha 21264 Microprocessor Hardware Reference Manual, 1999.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: D. Burger and T. Austin. The SimpleScalar Tool Set, Version 2.0. Technical Report #1342, CS Department, Univ. of Wisconsin-Madison, June 1997.
• 4: B. Calder , D. Grunwald , J. Emer, Predictive sequential associative cache, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.244, February 03-07, 1996
• 5: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 6: P. Glaskowsky. Pentium 4 (Partially) Previewed. Microprocessor Report, Aug. 2000.
• 7: G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, and P. Roussel. The Microarchitecture of the Pentium 4 Processor. Intel Technical Journal, Q1 2001.
• 8: 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
• 9: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 10: Lishing Liu, Cache designs with partial address matching, Proceedings of the 27th annual international symposium on Microarchitecture, p.128-136, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192742]
• 11: Enric Morancho , José María Llabería , Àngel Olivé, Recovery Mechanism for Latency Misprediction, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.118, September 08-12, 2001
• 12: Andreas Moshovos , Gokhan Memik , Alok Choudhary , Babak Falsafi, JETTY: Filtering Snoops for Reduced Energy Consumption in SMP Servers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.85, January 20-24, 2001
• 13: David B. Papworth, Tuning the Pentium Pro Microarchitecture, IEEE Micro, v.16 n.2, p.8-15, April 1996 [doi>10.1109/40.491458]
• 14: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 15: Adi Yoaz , Mattan Erez , Ronny Ronen , Stephan Jourdan, Speculation techniques for improving load related instruction scheduling, Proceedings of the 26th annual international symposium on Computer architecture, p.42-53, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

General Terms:
Algorithms, Design, Performance

Keywords:
bloom filter, data cache, data prefetching, data speculation, instruction scheduling