Page 1128 - The Mechatronics Handbook

FIGURE 42.5 Branch prediction.

A more modern approach to reducing branch penalties uses hardware to dynamically predict the
outcome of a branch. Branch prediction strategies reduce overall branch penalties by allowing the
hardware to continue processing instructions along the predicted control path, thus eliminating wasted
cycles. Efficient execution can be maintained while branch targets are correctly predicted. However, a
large performance penalty is incurred when a branch is mispredicted. Branch target buffer is a cache
structure that is accessed in parallel with the instruction fetch. It records the past history of branch
instructions so that a prediction can be made while the branch is fetched again. This prediction method
adapts the branch prediction to the run-time program behavior, generating a high prediction accuracy.
The target addresses of the branch is also saved in the buffer so that the target instruction can be fetched
immediately if a branch is predicted taken.
3
Several methodologies of branch target prediction have been constructed. Figure 42.5 illustrates
several general branch prediction schemes. The most common implementation retains history informa-
tion for each branch as shown in Fig. 42.5(a). The history includes the previous branch directions for
making predictions on future branch directions. The simplest history is last taken, which uses 1-bit to
recall whether the branch condition was taken or not taken. A more effective branch predictor uses a 2-
bit saturating state history counter to determine the future branch outcome similar to Fig. 42.5(b). Two
bits rather than 1 bit allows each branch to be tagged as strongly or weakly taken or not taken. Every
correct prediction reinforces the prediction, while an incorrect prediction weakens it. It takes two con-
secutive mispredictions to reverse the direction (whether taken or not taken) of the prediction.
Recently, more complex two-level adaptive branch prediction schemes have been built, which use two
levels of branch history to make predictions, as shown in Fig. 42.5(c). The first level is the branch outcome
history of the last branches encountered. The second level is the branch behavior for the last occurrences of
a specific pattern of branch histories. There are alternative ways of constructing both levels of adaptive branch
prediction schemes, the mechanisms can contain information that is either based on individual branches,
groups (set-based), and all (global). Individual formation contains the branch history for each branch ins-
truction. Set-based information groups branches according to their instruction address, thereby forming
sets of branch history. Global information uses a global history containing all branch outcomes. The second
level containing branch behaviors can also be constructed using any of the three types. In general, the first-
level branch history pattern is used as an index into the second-level branch history.

Memory Subsystem
The memory system serves as a repository of information in a microprocessor system. The processing
unit retrieves information stored in memory, operates on the information, and returns new information
back to memory. The memory system is constructed of basic semiconductor DRAM units called modules
or banks.

©2002 CRC Press LLC