Selective value prediction

ABSTRACT

Value Prediction is a relatively new technique to increase instruction-level parallelism by breaking true data dependence chains. A value prediction architecture produces values, which may be later consumed by instructions that execute speculatively using the predicted value.This paper examines selective techniques for using value prediction in the presence of predictor capacity constraints and reasonable misprediction penalties. We examine prediction and confidence mechanisms in light of these constraints, and we minimize capacity conflicts through instruction filtering. The latter technique filters which instructions put values into the value prediction table. We examine filtering techniques based on instruction type, as well as giving priority to instructions belonging to the longest data dependence path in the processor's active instruction window. We apply filtering both to the producers of predicted values and the consumers. In addition, we examine the benefit of using different confidence levels for instructions using predicted values on the longest dependence path.

REFERENCES

• 1: R. Iris Bahar , Gianluca Albera , Srilatha Manne, Power and performance tradeoffs using various caching strategies, Proceedings of the 1998 international symposium on Low power electronics and design, p.64-69, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.295115]
• 2: Bryan Black , Brian Mueller , Stephanie Postal , Ryan Rakvic , Noppanunt Utamaphethai , John Paul Shen, Load execution latency reduction, Proceedings of the 12th international conference on Supercomputing, p.29-36, July 1998, Melbourne, Australia [doi>10.1145/277830.277842]
• 3: D.C. Burger and T. M. Austin. The simplescatar tool set, version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin, Madison, June 1997.
• 4: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 5: B. Calder, P. Feller, and A. Eustaee. Value profiling and optimization. Journal of Instruction Level Parallelism, 1999.
• 6: 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]
• 7: Thomas M. Conte , Kishore N. Menezes , Patrick M. Mills , Burzin A. Patel, Optimization of instruction fetch mechanisms for high issue rates, Proceedings of the 22nd annual international symposium on Computer architecture, p.333-344, June 22-24, 1995, S. Margherita Ligure, Italy
• 8: Karel Driesen , Urs Hölzle, The cascaded predictor: economical and adaptive branch target prediction, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.249-258, November 1998, Dallas, Texas, United States
• 9: A. N. Eden , T. Mudge, The YAGS branch prediction scheme, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.69-77, November 1998, Dallas, Texas, United States
• 10: R. J. Eickemeyer and S. Vassiliadis. A load instruction unit for pipelined processors. IBM Journal of Research and Development, 37:547-564, July I993.
• 11: E Gabbay and A. Mendelson. Speculative execution based on value prediction. EE Department TR 1080, Technion - Israel lnstitue of Technology, November 1996.
• 12: Freddy Gabbay , Avi Mendelson, Can program profiling support value prediction?, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.270-280, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: Freddy Gabbay , Avi Mendelson, The effect of instruction fetch bandwidth on value prediction, Proceedings of the 25th annual international symposium on Computer architecture, p.272-281, June 27-July 02, 1998, Barcelona, Spain
• 14: José González , Antonio González, The potential of data value speculation to boost ILP, Proceedings of the 12th international conference on Supercomputing, p.21-28, July 1998, Melbourne, Australia [doi>10.1145/277830.277840]
• 15: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 16: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 17: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 18: K.L. Lick, Hybrid Branch Prediction Using Limited Dual Path Execution. PhD thesis, University of California, Riverside, December t996.
• 19: 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
• 20: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 21: S. McFarling, Combining branch predictors. Technical Report TN-36, Digital Equipment Corporation, Western Research Lab, June 1993.
• 22: Glenn Reinman , Brad Calder, Predictive techniques for aggressive load speculation, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.127-137, November 1998, Dallas, Texas, United States
• 23: G. Reinman, B. Calder, D. Tutlsen, G. Tyson, and T. Austin. Profile guided load marking for memory renaming. Technical Report UCSD- CS98-593, University of California, San Diego, July 1998.
• 24: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 25: Bohuslav Rychlik , John Faistl , Bryon Krug , John P. Shen, Efficacy and Performance Impact of Value Prediction, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.148, October 12-18, 1998
• 26: 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
• 27: Yiannakis Sazeides , James E. Smith, Modeling program predictability, Proceedings of the 25th annual international symposium on Computer architecture, p.73-84, June 27-July 02, 1998, Barcelona, Spain
• 28: Srikanth T. Srinivasan , Alvin R. Lebeck, Load latency tolerance in dynamically scheduled processors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.148-159, November 1998, Dallas, Texas, United States
• 29: D. Tullsen and B. Calder. Computing along the critical path. Technical report, University of California, San Diego, 1998.
• 30: 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
• 31: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

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

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

General Terms:
Design, Experimentation, Management, Theory