Minimizing branch misprediction penalties for superpipelined processors

ABSTRACT

Branch misprediction penalties depend on branch misprediction rates and branch penalties. Dynamic branch schemes take advantage of hardware to record and predict branch behavior at run-time for reducing branch misprediction rates. Static branch schemes take advantage of scheduling safe instructions into branch delay slots at compile-time for reducing branch penalties. This paper evaluates and compares the performance of various state-of-the-art static and dynamic branch schemes for super-pipelined processors.

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: Pradeep K. Dubey , Michael J. Flynn, Branch Strategies: Modeling and Optimization (Pipeline Processing), IEEE Transactions on Computers, v.40 n.10, p.1159-1167, October 1991 [doi>10.1109/12.93749]
• 4: Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
• 5: T. Gross, I. Hennessy, "Reducing the Cost of Branches," in Proceedings of the 13th Annual International Symposium on Computer Architecture, May 1986.
• 6: Ralph Haygood, A Prolog Benchmark Suite for Aquarius, University of California at Berkeley, Berkeley, CA, 1989
• 7: Bruce K. Holmer , Barton Sano , Michael Carlton , Peter Van Roy , Ralph Haygood , William R. Bush , Alvin M. Despain , Joan M. Pendleton , Tep Dobry, Fast Prolog with an extended general purpose architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.282-291, May 28-31, 1990, Seattle, Washington, United States
• 8: J.K.F. Lee and A.J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," Computer, Jan. 1984.
• 9: 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
• 10: 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
• 11: C-L Su, "An instruction Scheduler and Register Allocator for Prolog Parallel Microprocessors," in Proceeding of International Computer Symposium, 1992
• 12: C.-L Su , A. M. Despain, Branch with masked squashing in superpipelined processors, Proceedings of the 21ST annual international symposium on Computer architecture, p.130-140, April 18-21, 1994, Chicago, Illinois, United States
• 13: 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
• 14: Peter Van Roy , Alvin M. Despain, High-Performance Logic Programming with the Aquarius Prolog Compiler, Computer, v.25 n.1, p.54-68, January 1992 [doi>10.1109/2.108055]

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.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose)

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Experimentation, Measurement, Performance