Mastering Modern Processors: A Deep Dive into Two-Level Adaptive Branch Prediction

The Two-Level Adaptive Predictor is a sophisticated technique in computer architecture designed to accurately predict the outcome of conditional branches, a critical task for maintaining the performance of modern pipelined processors. It operates on the principle that the behavior of a branch is often correlated with the behavior of recently executed branches. By separating the mechanism into two levels, it can learn and predict complex, repeating patterns that simpler predictors cannot handle. The first level, the Branch History Register (BHR), is a shift register that records the recent global or local history of branch outcomes as a bit pattern. This pattern is then used as an index into the second level, the Pattern History Table (PHT). The PHT is a table of 2-bit saturating counters, each associated with a specific history pattern. The selected counter provides the final prediction. After the branch is resolved, both the BHR and the relevant PHT counter are updated, allowing the system to adapt and learn over time. Different configurations, such as GAg (Global history, Global table), offer a trade-off between hardware cost and prediction accuracy. While GAg is efficient, it can suffer from aliasing, where different branches contend for the same prediction entries. The invention of the two-level predictor was a pivotal moment in CPU design, enabling the deeper pipelines and higher clock speeds that define modern computing, and its concepts are foundational to the even more complex predictors in use today.

1. Introduction: The Pipeline's Dilemma

Modern processors achieve high performance through instruction pipelining, executing multiple stages of different instructions simultaneously, much like an assembly line. This process works beautifully until the pipeline encounters a conditional branch instruction (e.g., an if-else statement). The processor doesn't know which path of execution to take—the if block or the else block—until the condition is evaluated late in the pipeline.

This uncertainty forces the processor to either stall (pause and wait), creating a performance-killing bubble in the pipeline, or to guess the outcome. The penalty for guessing wrong is significant: the processor must flush all the speculatively executed (and incorrect) instructions from the pipeline and restart from the correct path. This is known as the branch penalty. As pipelines get deeper in modern CPUs, this penalty increases, making accurate branch prediction absolutely critical for performance.

2. The Limits of Simple Predictors

Early branch predictors were simple. A 1-bit predictor would remember the last outcome of a branch and predict the same way next time. This fails spectacularly for branches at the end of loops, which are 'Taken' many times and then 'Not-Taken' once. This pattern causes two mispredictions per loop execution.

A 2-bit saturating counter improves on this by adding hysteresis. It uses four states: Strongly Not-Taken, Weakly Not-Taken, Weakly Taken, and Strongly Taken. It takes two consecutive wrong outcomes to change the prediction from 'Strongly' one way to the other. This correctly predicts the single 'Not-Taken' at the end of a simple loop. However, it still fails to identify more complex patterns. For example, consider a branch whose behavior is Taken, Not-Taken, Taken, Not-Taken, .... A 2-bit counter will mispredict every single time after the initial learning phase.

3. The Two-Level Adaptive Predictor: Learning from History

The breakthrough came with the realization that the outcome of a branch often depends on the outcomes of recently executed branches. This is the core principle behind the Two-Level Adaptive Predictor. Instead of just using the past behavior of a single branch to predict its future, it uses the pattern of recent global or local branch outcomes to make a prediction.

It achieves this by decoupling the recording of history from the act of prediction into two distinct levels of hardware structures.

3.1 Architecture Components

A two-level predictor consists of two key components:

Level 1: Branch History Register (BHR): This is a simple shift register of k bits. Its purpose is to record the outcome of the last k branches. For each branch that is 'Taken', a '1' is shifted in; for 'Not-Taken', a '0' is shifted in. The BHR captures the recent pattern of branch behavior.

Level 2: Pattern History Table (PHT): This is a table containing 2^k entries. Each entry is a standard 2-bit saturating counter (as described above). The value in the BHR is used as an index to select one of these counters. The chosen counter then provides the actual prediction (Strongly Taken, etc.).

3.2 How It Works: A Step-by-Step Example

Let's trace a branch inside a nested loop that exhibits a T-NT-T-NT pattern. Assume we have a 2-bit BHR (k=2) and a PHT with 2^2 = 4 entries, all initialized to 'Weakly Not-Taken' (01).

Initial State: BHR = 00 (history of two Not-Taken branches).

First Branch (Outcome: Taken):

Prediction: The BHR is 00. We look up PHT[00]. It says 'Weakly Not-Taken'. Misprediction! Update: The actual outcome was 'Taken'. We update PHT[00] to 'Weakly Taken' (10). We shift a '1' (for Taken) into the BHR. BHR is now 01.

Second Branch (Outcome: Not-Taken):

Prediction: The BHR is 01. We look up PHT[01]. It says 'Weakly Not-Taken'. Correct Prediction! Update: The actual outcome was 'Not-Taken'. We update PHT[01] to 'Strongly Not-Taken' (00). We shift a '0' (for Not-Taken) into the BHR. BHR is now 10.

Third Branch (Outcome: Taken):

Prediction: The BHR is 10. We look up PHT[10]. It says 'Weakly Not-Taken'. Misprediction! Update: The outcome was 'Taken'. We update PHT[10] to 'Weakly Taken' (10). We shift a '1' into the BHR. BHR is now 01.

Fourth Branch (Outcome: Not-Taken):

Prediction: The BHR is 01. We look up PHT[01], which is now 'Strongly Not-Taken' (00). Correct Prediction! Update: The outcome was 'Not-Taken'. PHT[01] remains 'Strongly Not-Taken'. We shift a '0' into the BHR. BHR is now 10.

Fifth Branch (Outcome: Taken):

Prediction: The BHR is 10. We look up PHT[10], which is now 'Weakly Taken' (10). Correct Prediction! Update: The outcome was 'Taken'. We update PHT[10] to 'Strongly Taken' (11). We shift a '1' into the BHR. BHR is now 01.

As you can see, after a brief training period, the predictor has learned that the history 01 (a Taken followed by a Not-Taken) is followed by a Not-Taken branch, and the history 10 (a Not-Taken followed by a Taken) is followed by a Taken branch. It has successfully learned the T-NT pattern.

3.3 Flavors and Configurations

Two-level predictors are not one-size-fits-all. They are classified based on how the BHR and PHT are maintained. We use 'G' for Global, 'P' for Per-address, and 'S' for Per-Set.

History (BHR) Variants:

G (Global): A single, global BHR is used for all branches in the program. This is good for capturing correlation between different branches. P (Per-address): A separate BHR is maintained for each branch instruction (indexed by the branch's address). This is better for isolating the history of a single branch.

Pattern Table (PHT) Variants:

g (Global): One large, global PHT is shared by all branches. p (Per-address): Each branch instruction gets its own private PHT.

This leads to common configurations:

GAg (Global BHR, Global PHT): The most common and hardware-efficient design. A single BHR's value indexes into a single, shared PHT. Its main drawback is aliasing, where different branches with different behaviors but the same recent history pattern interfere with each other's entries in the PHT.
PAg (Per-address BHR, Global PHT): Each branch has its own history register, but they all use their history to index into a shared PHT. Better isolation than GAg but still prone to aliasing in the PHT.
PAp (Per-address BHR, Per-address PHT): The most powerful but also most hardware-intensive. Each branch has its own private history and its own private table of predictors. This eliminates interference but is often too costly in terms of chip area.

In practice, GAg-style predictors provided a huge leap in performance and were foundational in CPUs like the Intel Pentium Pro. Modern designs often use hybrid or 'tournament' predictors that combine a two-level predictor with a simpler predictor and dynamically choose the best one for a given branch.

Key points

Branch prediction is essential to prevent pipeline stalls in modern processors, which would otherwise severely degrade performance.
Simple predictors (like 1-bit or 2-bit counters) are limited because they cannot learn complex, repeating patterns of branch outcomes.
Two-Level Adaptive Predictors work by decoupling history recording (Level 1) from prediction making (Level 2).
The Branch History Register (BHR) records the outcomes (Taken/Not-Taken) of the last 'k' branches as a k-bit pattern.
The Pattern History Table (PHT) is a table of 2-bit counters, where the BHR's pattern is used as an index to select a counter for the prediction.
This architecture allows the predictor to learn that a specific *pattern* of past outcomes is likely to be followed by a 'Taken' or 'Not-Taken' result.
Common configurations include GAg (Global History, Global Table), which is efficient but can suffer from aliasing, where unrelated branches interfere with each other's predictions.
Other configurations like PAg and PAp offer better prediction isolation at the cost of increased hardware complexity.
Two-level predictors were a major advancement in computer architecture and form the basis for even more sophisticated hybrid predictors used in today's CPUs.

Browse public study notes