The effect of instruction fetch bandwidth on value prediction

ABSTRACT

Value prediction attempts to eliminate true-data dependencies by dynamically predicting the outcome values of instructions and executing true-data dependent instructions based on that prediction. In this paper we attempt to understand the limitations of using this paradigm in realistic machines. We show that the instruction-fetch bandwidth and the issue rate have a very significant impact on the efficiency of value prediction. In addition, we study how recent techniques to improve the instruction-fetch rate affect the efficiency of value prediction and its hardware organization.

REFERENCES

• 1: 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
• 2: S. Davidson, D. Landskov, B. D. Shriver and P. W. Mallet. Some Experiments in Local Microcode Compaction for Horizontal Machines. IEEE Transactions on Computers, Vol. C-30, no. 7, July, 1981, pp. 460-477.
• 3: Simonjit Dutta , Manoj Franklin, Control flow prediction with tree-like subgraphs for superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.258-263, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 4: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 5: Joseph Allen Fisher, The optimization of horizontal microcode within and beyond basic blocks: an application of processor scheduling with resources, 1979
• 6: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Alternative fetch and issue policies for the trace cache fetch mechanism, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.24-33, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: F. Gabbay and A. Mendelson. Speculative Execution based on Value Prediction. EE Department TR #1080, Technion - Israel Institute of Technology, November, 1996 ( http ://w ww-ee, tec h nion. ac. il/- fredg).
• 8: F. Gabbay and A. Mendelson. An Experimental and Analytical Study of Speculative Execution based on Value Prediction. EE Department TR #1124, Technion - Israel Institute of Technology, June, 1997.
• 9: 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
• 10: 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]
• 11: M. Johnson. Superscalar Microprocessor Design. Prentice Hall, Englewood Cliffs, 1990, N.J.
• 12: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 13: 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
• 14: 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
• 15: S. W. Melvin , M. C. Shebanow , Y. N. Patt, Hardware support for large atomic units in dynamically scheduled machines, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.60-63, November 28-December 02, 1988, San Diego, California, United States
• 16: S. J. Patel, D. H. Friendly and Y. N. Part. Critical Issues Regarding the Trace Cache Fetch Mechanism. Technical Report CSE---TR-335-97, Univ. of Michigan, May, 1997.
• 17: A. Peleg and U. Weiser. Dynamic Flow Instruction Cache Memory Organized Around Trace Segments Independent of Virtual Address Line. U. S. Paten Number 5,381,533, 1994.
• 18: 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
• 19: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 20: Introduction to Shade, Sun Microsystems Laboratories, Inc. TR 415-960-1300, Revision A of l/Apr/92.
• 21: 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
• 22: 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
• 23: A. Smith and J. Lee. Branch Prediction Strategies and Branch-Target Buffer Design. Computer 17:1, January, 1984.
• 24: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 25: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• 26: Shlomo Weiss , James E. Smith, A study of scalar compilation techniques for pipelined supercomputers, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.105-109, October 1987, Palo Alto, California, United States
• 27: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 28: Tse-Yu Yeh , Deborah T. Marr , Yale N. Patt, Increasing the instruction fetch rate via multiple branch prediction and a branch address cache, Proceedings of the 7th international conference on Supercomputing, p.67-76, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165956]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

General Terms:
Performance