The effect of speculatively updating branch history on branch prediction accuracy, revisited

ABSTRACT

Recent research has suggested that the branch history register need not contain the outcomes of the most recent branches in order for the Two-Level Adaptive Branch Predictor to work well. From this result, it is tempting to conclude that the branch history register need not be speculatively updated. This paper revisits this work and explains when the most recent branch outcomes can be omitted without significantly affecting performance. It also explains why this result does not imply that speculative update is not important. This paper shows that because the number of unresolved branches present in the machine varies during program execution, branch predictors without speculative update perform significantly worse than branch predictors with speculative update.

REFERENCES

• 1: W. W. Hwu , Y. N. Patt, Checkpoint repair for out-of-order execution machines, Proceedings of the 14th annual international symposium on Computer architecture, p.18-26, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30353]
• 2: J. K. F. Lee and A. J. Smith, "Branch prediction strategies and branch target buffer design," IEEE Computer, pp. 6-22, January 1984.
• 3: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 4: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 5: A. R. Talcott, June 1994. Personal communication.
• 6: A. R. Talcott , W. Yamamoto , M. J. Serrano , R. C. Wood , M. Nemirovsky, The impact of unresolved branches on branch prediction scheme performance, Proceedings of the 21ST annual international symposium on Computer architecture, p.12-21, April 18-21, 1994, Chicago, Illinois, United States
• 7: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]
• 8: 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
• 9: Tse-Yu Yeh , Yale N. Patt, A comprehensive instruction fetch mechanism for a processor supporting speculative execution, Proceedings of the 25th annual international symposium on Microarchitecture, p.129-139, December 01-04, 1992, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

General Terms:
Measurement

Keywords:
dynamic branch prediction, out-of-order execution, speculative execution, superscalar processors, two-level adaptive branch prediction