Correlated load-address predictors

ABSTRACT

As microprocessors become faster, the relative performance cost of memory accesses increases. Bigger and faster caches significantly reduce the absolute load-to-use time delay. However, increase in processor operational frequencies impairs the relative load-to-use latency, measured in processor cycles (e.g. from two cycles on the Pentium® processor to three cycles or more in current designs). Load-address prediction techniques were introduced to partially cut the load-to-use latency. This paper focuses on advanced address-prediction schemes to further shorten program execution time.Existing address prediction schemes are capable of predicting simple address patterns, consisting mainly of constant addresses or stride-based addresses. This paper explores the characteristics of the remaining loads and suggests new enhanced techniques to improve prediction effectiveness:• Context-based prediction to tackle part of the remaining, difficult-to-predict, load instructions.• New prediction algorithms to take advantage of global correlation among different static loads.• New confidence mechanisms to increase the correct prediction rate and to eliminate costly mispredictions.• Mechanisms to prevent long or random address sequences from polluting the predictor data structures while providing some hysteresis behavior to the predictions.Such an enhanced address predictor accurately predicts 67% of all loads, while keeping the misprediction rate close to 1%. We further prove that the proposed predictor works reasonably well in a deep pipelined architecture where the predict-to-update delay may significantly impair both prediction rate and accuracy.

REFERENCES

• Aust95: Todd M. Austin , Gurindar S. Sohi, Zero-cycle loads: microarchitecture support for reducing load latency, Proceedings of the 28th annual international symposium on Microarchitecture, p.82-92, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• Baer91: 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]
• Chen95: 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]
• Eick93: R.J. Eickemeyer and S. Vassiliadis, "A Load-lnstruction Unit for Pipelined Processors," in IBM Journal of Research and Development. 1993.
• Gonz97s: José González , Antonio González, Speculative execution via address prediction and data prefetching, Proceedings of the 11th international conference on Supercomputing, p.196-203, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263631]
• Lipa96a: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• Lipa96b: M. l-I. Lipasti and J. P. Shen, "Exceeding the Dataflow Limit via Value Prediction," in MICRO-29, t996.
• Mora98: Enric Morancho , José María Llabería , Angel Olivé, Split Last-Address Predictor, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.230, October 12-18, 1998
• Saze96: Yiannakis Sazeides , Stamatis Vassiliadis , James E. Smith, The performance potential of data dependence speculation & collapsing, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.238-247, December 02-04, 1996, Paris, France
• Saze97: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• Sezn96: André Seznec , Stéphan Jourdan , Pascal Sainrat , Pierre Michaud, Multiple-block ahead branch predictors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.116-127, October 01-04, 1996, Cambridge, Massachusetts, United States
• Wang97: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Management, Measurement, Performance

Keywords:
context-based predictor, global correlation, load-address prediction, predictor implementation, recursive data structures