Dynamic Branch Prediction Mechanisms

In this lesson, you will learn how dynamic branch prediction uses historical execution patterns to guess the outcome of branches before they are actually resolved.

The Limitation of Static Prediction

Previously, we discussed static prediction, where the hardware assumes a branch is always taken or always not taken. However, real-world code (like if-else blocks or loops) often switches behaviors. If a branch pattern changes, static prediction forces a pipeline flush, causing a performance penalty. Dynamic prediction solves this by "learning" from previous outcomes.

Saturating Counters (1-bit and 2-bit)

The simplest dynamic mechanism is a 1-bit saturating counter. It stores a single bit: the outcome of the last time this specific branch was executed. If it was taken, the CPU predicts "taken."

To improve this, we use a 2-bit saturating counter. This acts like a state machine with four states: Strongly Not Taken, Weakly Not Taken, Weakly Taken, and Strongly Taken. It requires two consecutive "mispredictions" to flip the prediction, which prevents a single loop exit from ruining the prediction accuracy for the next time the loop runs.

// Simplified 2-bit counter logic
if (branch_taken) {
    if (state < 3) state++; // Move toward Strongly Taken
} else {
    if (state > 0) state--; // Move toward Strongly Not Taken
}
predict_taken = (state >= 2);

Two-Level Adaptive Predictors

Sometimes, branches depend on a sequence of past events (e.g., a branch that is taken every third time it runs: T, T, N, T, T, N). A simple counter cannot recognize this pattern.

A two-level adaptive predictor solves this using two structures:

1. Branch History Table (BHT): A shift register that records the last N branch outcomes (e.g., 1101 means the last four branches were Taken, Taken, Not Taken, Taken).
2. Pattern History Table (PHT): An array of 2-bit counters. The shift register acts as an index into this table.

By using the history pattern as an index, the processor can "learn" that a specific sequence of previous branches almost always leads to a certain outcome, effectively identifying correlations across different code segments.

Key Takeaway: Dynamic branch prediction minimizes pipeline stalls by using saturating counters to track recent behavior and two-level predictors to identify complex, repeating branch patterns.