The effects of predicated execution on branch prediction

ABSTRACT

High performance architectures have always had to deal with the performance limiting impact of branch operations. Microprocessor designs are going to have to deal with this problem as well, as they move towards deeper pipelines and support for multiple instruction issue. Branch prediction schemes are often used to alleviate the negative impact of branch operations by allowing the speculative execution of instructions after an unresolved branch. Another technique is to eliminate branch instructions altogether. Predication can remove forward branch instructions by translating the instructions following the branch into predicate form.This paper analyzes a variety of existing predication models for eliminating branch operations, and the effect that this elimination has on the branch prediction schemes in existing processors, including single issue architectures with simple prediction mechanisms, to the newer multi-issue designs with correspondingly more sophisticated branch predictors. The effect on branch prediction accuracy, branch penalty and basic block size is studied.

REFERENCES

• AlAv93: Donald Alpert , Dror Avnon, Architecture of the Pentium Microprocessor, IEEE Micro, v.13 n.3, p.11-21, May 1993 [doi>10.1109/40.216745]
• AADM93: Tom Asprey , Gregory S. Averill , Eric DeLano , Russ Mason , Bill Weiner , Jeff Yetter, Performance Features of the PA7100 Microprocessor, IEEE Micro, v.13 n.3, p.22-35, May 1993 [doi>10.1109/40.216746]
• CMCW91: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• DeHB89: James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
• FiFr92: 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
• HePa90: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• LeS84: I.K.L. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design", Computer, vol. 17, no. 1 (January 1984), pp. 6-22.
• McLe93: Edward McLellan, The Alpha AXP Architecture and 21064 Processor, IEEE Micro, v.13 n.3, p.36-47, May 1993 [doi>10.1109/40.216747]
• PnSo94: D. N. Pnevmatikatos , G. S. Sohi, Guarded execution and branch prediction in dynamic ILP processors, Proceedings of the 21ST annual international symposium on Computer architecture, p.120-129, April 18-21, 1994, Chicago, Illinois, United States
• Russ78: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• Site92: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• Smit81: 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
• SrWa94: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• YeP91: 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]
• YeP93: 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
• 94: "PowerPC 601 RISC Microprocessor Users's Manual Addendum for 604", Motorola / IBM Microelectronics(1993, 1994).

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

General Terms:
Design, Performance

Keywords:
ATOM, Alpha, HP-RISC, Pentium, PowerPC, branch prediction, high-performance, predication