Hardware Reference
In-Depth Information
''no branch'' next time. If that prediction is wrong, it will move to state 01, but
predict ''no branch'' next time as well. Only if this prediction is wrong will it now
move to state 11 and predict branches all the time. In effect, the leftmost bit of the
state is the prediction and the rightmost bit is what the branch did last time. While
this design uses only 2 bits of history, a design that keeps track of 4 or 8 bits of his-
tory is also possible.
Branch
No branch
Branch
No
b
ranch
01
10
Bran
c
h
00
11
Predict
no branch
one more
time
Predict
branch
one more
time
Predict
no branch
Predict
branch
No
branch
Branch
No branch
Figure 4-42.
A 2-bit finite-state machine for branch prediction.
This is not our first FSM. Figure 4-28 was also an FSM. In fact, all of our
microprograms can be regarded as FSMs, since each line represents a specific state
the machine can be in, with well-defined transitions to a finite set of other states.
FSMs are very widely used in all aspects of hardware design.
So far, we have assumed that the target of each conditional branch was known,
typically either as an explicit address to branch to (contained within the instruction
itself), or as a relative offset from the current instruction (i.e., a signed number to
add to the program counter). Often this assumption is valid, but some conditional
branch instructions compute the target address by doing arithmetic on registers,
and then going there. Even if the FSM of Fig. 4-42 accurately predicts the branch
will be taken, such a prediction is of no use if the target address is unknown. One
way of dealing with this situation is to store the actual address branched to the last
time in the history table, as shown in Fig. 4-41(c). In this way, if the table says that
the last time the branch at address 516 was taken it went to address 4000, if the
prediction is now for ''branch,'' the working assumption will be a branch to 4000
again.
A different approach to branch prediction is to keep track of whether the last
k
conditional branches encountered were taken, irrespective of which instructions
they were. This
k
-bit number, kept in the
branch history shift register
, is then
compared in parallel to all the entries of a history table with a
k
-bit key and, if a hit
occurs, the prediction found there used. Somewhat surprisingly, this technique
works quite well in actual practice.
