文档介绍：A STUDY OF BRANCH PREDICTION STRATEGIES
JAMES E. SMITH
Control Data Corporation
Arden Hills. Minnesota
ABSTRACT Because of the wide variation in branching behavior
between different applications, different programming
In high-puter systems. performance losses
due to conditional branch instructrons can be minrmized by languages, and even individual programs, there is no
predicting a branch e and fetching, decoding, and/or good analytic model for studying branch prediction. For
issuing subsequent instructions before the actual e is this reason, we used instruction trace data to measure
known. This paper discusses branch prediction strategies wrth experimentally the accuracy of branch prediction
the goal of maxtmizing prediction accuracy. First. currently
strategies.
used techniques are discussed and analyzed using instruction
tmce data. Then, new techniques are proposed and are shown
to provide greater accuracy and more flexibility at low cost. Originally, ten FORTRAN programs, primarily scientific,
were chosen. It was found, however, that several were
heavily dominated by inner loops, which made them very
INTRODUCTION predictable by every strategy considered. Two
programs, SC12 and ADVAN, were chosen from this
It is well known1-3,10 that In a highly puter inner-loop-dominated class. Four other programs were
system, branch instructions can break the smooth flow not as heavily dominated by inner loops and were less
of instruction fetching and execution. This results in predictable. All were chosen for the study.
delay, because a branch that is taken changes the
location of instruction fetches and because the issuing The six FORTRAN programs used in this study were:
of instructions must often wait until conditional branch
decisions are made. 1. ADVAN : Calculates the solution of three
simultaneous partial differential
To reduce delay, one can attempt to predict the equations
direction