Branch Prediction

Branch prediction is a critical performance optimization technique in modern pipelined processors. Without it, every conditional branch instruction would stall the pipeline while the processor waits to determine the actual branch outcome, wasting many clock cycles. The goal of branch prediction is to guess the branch direction early enough that the pipeline continues fetching and executing instructions without stalling.

Why Branch Prediction Matters

Modern processors fetch and decode instructions several stages before execution. When a conditional branch is encountered, the processor does not yet know whether the branch will be taken or not, because the condition depends on values computed in the execute stage. In a 5-stage pipeline, this creates a branch hazard with a potential penalty of 3 to 4 cycles per branch. Since branches occur roughly every 5 to 7 instructions in typical programs, even a 20% misprediction rate causes a significant CPI increase.

Branch prediction allows the processor to speculatively continue execution along the predicted path. If the prediction is correct, no cycles are wasted. If wrong, the speculatively executed instructions must be flushed from the pipeline (squashed), and execution restarts from the correct target address. The cost of a misprediction is called the branch penalty and equals the number of pipeline stages between fetch and branch resolution.

Static Branch Prediction

In static branch prediction, the prediction is fixed at compile time or based on simple heuristics. It does not use runtime history. Common static strategies include:

• Always Taken: The processor always predicts that every branch will be taken. Works well for loops since backward branches (end of loop to loop top) are taken most of the time.
• Always Not Taken: The processor assumes branches are not taken. Simple to implement. Works well for forward branches in if-else structures.
• Backward Taken, Forward Not Taken (BTFNT): Backward branches (negative offset) are predicted taken (loop-back pattern), while forward branches (positive offset) are predicted not taken. This is a good heuristic that improves on always-taken without any hardware history table.
• Compiler-annotated: Some ISAs allow compiler to embed branch hints in the instruction encoding. The compiler uses profiling data to set these hints.

Dynamic Branch Prediction

In dynamic branch prediction, the processor uses the runtime history of branches to make predictions. The key hardware structure is the Branch History Table (BHT), also called the Pattern History Table, which is an array of saturating counters indexed by the lower bits of the branch instruction's PC.

1-Bit Predictor

Each entry is a single bit: 1 means predict taken, 0 means predict not taken. After each branch, the bit is updated to reflect actual outcome. The problem is that for a loop that runs N iterations, the predictor mispredicts twice per loop execution (once when the loop first iterates after a not-taken, and once at loop exit). Accuracy for a loop with N iterations = (N-2)/N, which is poor for small loops.

2-Bit Saturating Counter

The 2-bit saturating counter (also called bimodal predictor) uses a 2-bit counter with four states: Strongly Taken (11), Weakly Taken (10), Weakly Not Taken (01), Strongly Not Taken (00). The prediction is taken when counter value is 10 or 11. The counter increments on a taken branch and decrements on a not-taken branch, but saturates at 11 and 00. This requires two consecutive mispredictions to switch prediction direction, improving loop prediction significantly. For a loop with N iterations, only one misprediction occurs at loop exit.

Correlating Predictors

A correlating predictor (also called two-level adaptive predictor) uses the outcomes of the last k branches to index into the BHT. This global history register (GHR) stores the pattern of recent branch outcomes as a shift register. The GHR is concatenated with (or XORed with) the branch PC to form the index into the pattern history table. This captures correlation between branches, for example, an if-else chain where the second branch depends on the outcome of the first.

A tournament predictor combines a local predictor (which uses per-branch history) and a global predictor (which uses global history across all branches), and a meta-predictor selects between them based on which one has been more accurate recently for each branch. Modern processors such as the AMD Zen series use tournament predictors with history lengths of 64 or more bits.

Branch Target Buffer

The Branch Target Buffer (BTB) is a cache that stores the target address of recently seen branch instructions, indexed by the branch PC. When the fetch stage encounters a PC that hits in the BTB, it immediately redirects fetch to the stored target without waiting for decode. This handles both direction prediction and target address prediction in a single cycle, enabling zero-cycle branch overhead on BTB hits with correct predictions.

Performance Calculation

The CPI with branch mispredictions is calculated as: CPI_actual = CPI_ideal + branch_frequency x misprediction_rate x branch_penalty. This formula directly shows why reducing any of the three factors improves performance.

Given:
Ideal CPI = 1.0
Branch instruction frequency = 20% (1 in every 5 instructions)
Misprediction rate = 15%
Branch penalty (pipeline stages before resolution) = 4 cycles

Why this formula applies:
Every mispredicted branch wastes branch_penalty cycles.
Expected wasted cycles per instruction = frequency * misprediction_rate * penalty

Formula:
CPI_actual = CPI_ideal + (branch_freq * misprediction_rate * branch_penalty)

Substitution:
CPI_actual = 1.0 + (0.20 * 0.15 * 4)

Calculation:
CPI_actual = 1.0 + 0.12

Final Answer: CPI_actual = 1.12
This represents a 12% increase in CPI due to branch mispredictions alone.

Exam Tip: GATE commonly tests the CPI penalty formula for branches. A common trap is forgetting to multiply all three terms together. Also, the 2-bit predictor mispredicts only ONCE per loop (at exit), not twice like the 1-bit predictor — this distinction appears in numerical questions.

2-Bit Counter State Machine

• States 00 and 01 predict not taken. States 10 and 11 predict taken.
• On a taken branch, counter increments (up to max 11). On not taken, counter decrements (down to min 00).
• Two consecutive opposite outcomes are needed to switch prediction from taken to not taken or vice versa.
• For a loop with N iterations: prediction is Taken for N-1 iterations (correct), then Not Taken at exit causes one misprediction. Accuracy = (N-1)/N.
• Correlating predictor uses global history of last k branch outcomes to index PHT, capturing inter-branch correlations.
• Tournament predictor chooses between local and global predictors per branch using a meta-predictor table.

Quick Revision

• Branch penalty = number of pipeline stages before branch resolution. CPI_actual = CPI_ideal + (branch_freq x misprediction_rate x penalty).
• Static prediction: fixed at compile time. BTFNT (Backward Taken Forward Not Taken) is the best simple static heuristic.
• 1-bit predictor: 2 mispredictions per loop. 2-bit predictor: 1 misprediction per loop (at exit only).
• 2-bit counter states: 00 (SN), 01 (WN), 10 (WT), 11 (ST). Predict taken when state >= 10.
• BTB caches branch target address indexed by PC. Enables zero-cycle redirection on BTB hit.
• Correlating predictor: uses global history register (GHR) XORed with PC to index PHT for better accuracy.
• GATE trap: misprediction rate and branch frequency are separate terms. Both must be applied to get CPI penalty correctly.