Hardware Reference
In-Depth Information
branches will be taken and that all forward ones will not be taken. The reasoning
behind the first part is that backward branches are frequently located at the end of a
loop. Most loops are executed multiple times, so guessing that a branch back to
the top of the loop will be taken is generally a good bet.
The second part is shakier. Some forward branches occur when error condi-
tions are detected in software (e.g., a file cannot be opened). Errors are rare, so
most of the branches associated with them are not taken. Of course, there are
plenty of forward branches not related to error handling, so the success rate is not
nearly as good as with backward branches. While not fantastic, this rule is at least
better than nothing.
If a branch is correctly predicted, there is nothing special to do. Execution just
continues at the target address. The trouble comes when a branch is predicted
incorrectly. Figuring out where to go and going there is not difficult. The hard
part is undoing instructions that have already been executed and should not have
been.
There are two ways of going about this. The first way is to allow instructions
fetched after a predicted conditional branch to execute until they try to change the
machine's state (e.g., storing into a register). Instead of overwriting the register,
the value computed is put into a (secret) scratch register and only copied to the real
register after it is known that the prediction was correct. The second way is to
record the value of any register about to be overwritten (e.g., in a secret scratch
register), so the machine can be rolled back to the state it had at the time of the
mispredicted branch. Both solutions are complex and require industrial-strength
bookkeeping to get them right. And if a second conditional branch is hit before it
is known whether the first one was predicted right, things can get really messy.
Dynamic Branch Prediction
Clearly, having the predictions be accurate is of great value, since it allows the
CPU to proceed at full speed. As a consequence, much ongoing research aims at
improving branch prediction algorithms (Chen et al., 2003, Falcon et al., 2004,
Jimenez, 2003, and Parikh et al., 2004). One approach is for the CPU to maintain
a history table (in special hardware), in which it logs conditional branches as they
occur, so they can be looked up when they occur again. The simplest version of
this scheme is shown in Fig. 4-41(a). Here the history table contains one entry for
each conditional branch instruction. The entry contains the address of the branch
instruction along with a bit telling whether it was taken the last time it was ex-
ecuted. Using this scheme, the prediction is simply that the branch will go the
same way it went last time. If the prediction is wrong, the bit in the history table is
changed.
There are several ways to organize the history table. In fact, these are precisely
the same ways used to organize a cache. Consider a machine with 32-bit instruc-
tions that are word aligned so that the low-order 2 bits of each memory address are
