Pipelining Design Techniques - Fundamentals of Computer Organization and Architecture - page 198

assume that whenever a conditional branch is encountered, the system predicts that
the branch will not be taken (or alternatively will be taken). In this way, fetching of
instructions in sequential address order will continue (or fetching of instructions
starting from the target branch instruction will continue). At the completion of the
branch instruction execution, the results will be known and a decision will have
to be made as to whether the instructions that were executed assuming that the
branch will not be taken (or taken) were the intended correct instruction sequence
or not. The outcome of this decision is one of two possibilities. If the prediction
was correct, then execution can continue with no wasted time units. If, on the
other hand, the wrong prediction has been made, then care must be taken such
that the status of the machine, measured in terms of memory and register contents,
should be restored as if no speculative execution took place.
Prediction based on the above scheme will lead to the same branch prediction
decision every time a given instruction is encountered, hence the name static
branch prediction. It is the simplest branch prediction scheme and is done during
compilation time.
Another technique that can be used in branch prediction is dynamic branch pre-
diction. In this case, prediction is done at run time, rather than at compile time.
When a branch is encountered, then a record is checked to find out whether that
same branch has been encountered before and if so, what was the decision made
at that time; that is, was the branch taken or not taken. A run time decision is
then made whether to take or not to take the branch. In making such a decision, a
two-state algorithm, “likely to be taken” (LTK) or “likely not to be taken”
(LNK), can be followed. If the current state is LTK and if the branch is taken,
then the algorithm will maintain the LTK state; otherwise it will switch to the
LNK. If, on the other hand, the current state is LNK and the branch is not taken,
then the algorithm will maintain the LNK state; otherwise it will switch to the
LTK state. This simple algorithm should work fine, particularly if the branch is
going backwards, for example during the execution of a loop. It will, however,
lead to misprediction when control reaches the last pass through the loop. A more
robust algorithm that uses four states has been used by the ARM 11 microarchitec-
ture (see below).
It is interesting to notice that a combination of dynamic and static branch predic-
tion techniques can lead to performance improvement. An attempt to use a dynamic
branch prediction is first made, and if it is not possible, then the system can resort to
the static prediction technique.
Consider, for example, the ARM 11 microarchitecture (the first implementation
of the ARMv6 instruction set architecture). This architecture uses a dynamic

static
branch prediction combination. A record in the form of a 64-entry, four-state branch
target address cache (BTAC) is used to help the dynamic branch prediction finding
whether a given branch has been encountered before. If the branch has been encoun-
tered, the record will also show whether it was most frequently taken or most fre-
quently not taken. If the BTAC shows that a branch has been encountered before,
then a prediction is made based on the previous outcome. The four states are:
strongly taken, weakly taken, strongly not taken, and weakly not taken.

/