Branch classification: a new mechanism for improving branch predictor performance

ABSTRACT

There is wide agreement that one of the most important impediments to the performance of current and future pipelined superscalar processors is the presence of conditional branches in the instruction stream. Speculative execution seems to be one solution of choice to the branch problem, but speculative work is discarded if a branch is mispredicted. Therefore, we need a very accurate branch predictor; 95% accuracy is not good enough. This paper proposes branch classification to help improve the accuracy of branch predictors. Branch classification allows an individual branch instruction to be associated with the branch predictor best suited to predict its direction. Using this approach, a hybrid branch predictor can be constructed such that each component branch predictor predicts those branches for which it is best suited. This paper suggests one classification scheme, analyzes several branch predictors, and proposes a hybrid branch predictor that achieves higher prediction accuracy than any branch predictor previously reported in the literature.

REFERENCES

• 1: P. Chow , M. Horowitz, Architectural tradeoffs in the design of MIPS-X, Proceedings of the 14th annual international symposium on Computer architecture, p.300-308, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30384]
• 2: J. A. DeRosa , H. M. Levy, An evaluation of branch architectures, Proceedings of the 14th annual international symposium on Computer architecture, p.10-16, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30352]
• 3: Joel S. Emer , Douglas W. Clark, A Characterization of Processor Performance in the vax-11/780, Proceedings of the 11th annual international symposium on Computer architecture, p.301-310, January 1984
• 4: P.M. Kogge, The Architecture of Pipelined Computers, pp.237-243, McGraw-Hill, 1981.
• 5: J.K.F. Lee and A.J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," IEEE Computer, pp.6-22, january 1984.
• 6: S. McFarling, "Combining Branch Predictors", WRL Technical Note TN-36, Digital Equipment Corporation, June 1993.
• 7: 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
• 8: Charles Melear, The Design of the 88000 RISC Family, IEEE Micro, v.9 n.2, p.26-38, March 1989 [doi>10.1109/40.24848]
• 9: 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
• 10: 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
• 11: 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]
• 12: 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:
  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

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

General Terms:
Experimentation, Performance

Keywords:
branch classification, branch predictor, processor performance, speculative execution, superscalar