Branch Prediction Strategies

The High Cost of Being Wrong

Before we dive into the strategies, let's reinforce why branch prediction is so critical. In a deep pipeline (modern CPUs can have 10-20+ stages), a single misprediction means all the instructions in flight behind the branch are on the wrong path and must be discarded. This wastes a significant number of clock cycles and dramatically reduces the processor's effective throughput.

Our goal is to maximize the number of correct predictions to minimize this penalty.

Static Branch Prediction: The Fixed-Rule Approach

Static prediction strategies follow fixed rules that do not change based on the runtime behavior of the code. The prediction is either hard-wired into the CPU design or determined by the compiler.

The simplest strategies, which we touched on last time, are:

• Always Predict Not-Taken: Assumes branches are never taken. This is effective for simple if statements that handle exceptional cases, but performs poorly on loops.
• Always Predict Taken: Assumes branches are always taken. This is better for loops but poor for if statements.

A more intelligent static approach relies on compiler heuristics. The most common is Backward Branch Taken, Forward Branch Not-Taken (BTFNT).

• Backward Branch: A branch whose target address is lower than the current Program Counter (PC). These are almost always loop-closing branches, which are taken most of the time. The compiler can generate code where loops jump backward.
• Forward Branch: A branch whose target address is higher than the PC. These are typically if-then-else constructs or error checks, which are less predictably taken.

This simple heuristic is surprisingly effective and is often used as a fallback mechanism in modern processors when the dynamic predictor has no information about a branch.

Another static technique, now largely historical but important to know for interviews, is the Branch Delay Slot. The ISA is designed such that the instruction immediately following a branch is always executed, regardless of the branch outcome. The compiler's job is to find an independent instruction to place in this "slot."

While simple and low-power, static predictors are not adaptive. They fail when branch behavior is complex or changes over the program's execution.

Dynamic Branch Prediction: Learning from History

Dynamic branch prediction uses dedicated hardware to record the past history of branches and use that history to predict future outcomes. This allows the processor to adapt to the program's runtime behavior.

Let's begin by watching an overview of the core concepts.

Let's break down those initial predictors in more detail.

1-Bit Predictor (Last-Time Predictor)

This is the simplest dynamic predictor. The BHT stores one bit for each branch, recording whether it was Taken or Not-Taken the last time it was executed. The next prediction is simply the last outcome.

• State Machine: A simple 2-state machine (Predict Taken, Predict Not-Taken).
• Flaw: It performs poorly for branches that are almost always taken, like a for loop. It will correctly predict every taken branch inside the loop, but it will mispredict the final iteration when the loop exits. Then, the next time the loop is entered, it will mispredict the first iteration because its last recorded state was "Not-Taken." This results in two mispredictions per loop execution.

2-Bit Predictor (Bimodal Predictor)

To fix the flaw of the 1-bit predictor, a 2-bit scheme is used. This adds hysteresis, preventing the prediction from changing on a single different outcome. Each branch has a 2-bit saturating counter in the BHT, representing four states:

• 11: Strongly Taken
• 10: Weakly Taken
• 01: Weakly Not-Taken
• 00: Strongly Not-Taken

The prediction is based on the most significant bit (1 = Taken, 0 = Not-Taken). The counter is incremented when the branch is actually taken (saturating at 11) and decremented when not-taken (saturating at 00).

Because of this improved accuracy, 2-bit predictors (or variants) form the basis of virtually all modern branch predictors.

Advanced Dynamic Prediction: Exploiting Correlation

A 2-bit bimodal predictor works well for branches with a strong bias (like loops), but it can fail when a branch's outcome is correlated with the outcome of other recent branches.

Consider this example:

if (d == 0) { ... } // branch 1
if (d == 2) { ... } // branch 2

if (d == 0 || d == 2) { // branch 3
    // This branch is correlated with branches 1 and 2
}

The outcome of branch 3 is not random; it is highly dependent on the outcomes of branch 1 and branch 2. A simple bimodal predictor for branch 3 would not capture this relationship.

This leads to two-level predictors.

These two-level predictors dramatically improve accuracy by learning more complex patterns in program behavior.

State-of-the-Art: Hybrid / Tournament Predictors

Some branches are best predicted by their local history, while others are better predicted by global history. So, why not use both?

This is the idea behind Hybrid or Tournament Predictors.

• Multiple predictors (e.g., a local predictor and a global predictor) run in parallel.
• A meta-predictor (or choice predictor) also keeps track of which predictor has been more accurate for a given branch or history pattern.
• The meta-predictor's output is used to select which prediction to ultimately use.

Interview Deep Dive: Real-World Implementations

These concepts are not just academic. They are directly implemented in the processors designed by the companies you are targeting. Information is often proprietary, but analysis reveals the strategies used. The "Demystifying Intel Branch Predictors" paper provides fantastic insight. Here are the key findings:

• Intel P6 Architecture (Pentium Pro, Pentium II/III):

  • Relied on a local history predictor.
  • Each entry in its 512-entry Branch Target Buffer (BTB) was associated with a 4-bit local history.
  • This predictor was excellent at capturing patterns for individual branches.

• Intel NetBurst Architecture (Pentium 4):

  • Switched to a powerful global history predictor.
  • It used a 16-bit Global History Register.
  • It also featured a very large 4K-entry BTB and an "Execution Trace Cache," which stored sequences of decoded instructions along a predicted path, effectively acting as a highly advanced form of branch prediction.

This shift from a local to a global prediction strategy between major architectures highlights a real-world design trade-off. The NetBurst design's bet on global correlation was part of its strategy to achieve very high clock speeds by enabling a very deep pipeline.

Conclusion

We've journeyed from simple static rules to the sophisticated, learning-based hardware of modern dynamic predictors. Mitigating control hazard penalties is a constant battle between hardware complexity, power consumption, and prediction accuracy.

Key Takeaways:

• Static Prediction uses fixed rules (e.g., BTFNT). It is simple but inflexible.
• Dynamic Prediction uses hardware to learn from past branch behavior at runtime.
• 1-bit predictors are simple but have a "double misprediction" flaw on standard loops.
• 2-bit predictors add hysteresis, significantly improving accuracy by requiring two consecutive wrong outcomes to flip a strong prediction.
• Two-Level Predictors exploit correlation, using either global history (outcomes of any recent branch) or local history (outcomes of a specific branch) to make more intelligent predictions.
• Tournament Predictors combine multiple strategies (e.g., local and global) and use a meta-predictor to choose the best one for the current situation, achieving state-of-the-art accuracy.

Preview of the Next Lesson:
We've now examined the memory system (caches, MMU) and core execution logic (pipelining, branch prediction). In the next lesson, we will step back and compare the two dominant Instruction Set Architecture (ISA) philosophies: RISC (Reduced Instruction Set Computer) vs. CISC (Complex Instruction Set Computer). We'll explore how this fundamental design choice impacts everything from compiler design to pipeline complexity and performance, using ARM and x86 as our primary examples.