Branch Hazards, Dynamic Predictors & Branch Target Buffers
“Branch penalties, 2-bit saturating counters, Branch Target Buffers (BTB), and delayed branch.”
1.Control Hazards & Branch Penalty Dynamics
§ 4.1.A Control Hazard occurs when the pipeline cannot determine the next instruction to fetch because a conditional branch instruction has not yet been resolved.
Branch Resolution Points:
1. If branch outcome and target address are resolved at the EX stage (Stage 3): The penalty for a taken branch is 2 stall cycles (instructions fetched during ID and EX must be flushed).
2. If branch outcome is resolved early at the ID stage (Stage 2) with dedicated hardware: The penalty for a taken branch is reduced to 1 stall cycle.
Branch Hazard Mitigation Strategies:
- Delayed Branching: The instruction immediately following the branch (in the 'delay slot') is ALWAYS executed regardless of whether the branch is taken. The compiler fills this slot with useful work.
- Static Branch Prediction: Assume branch is always taken (or always not taken).
- Dynamic Branch Prediction (2-Bit Saturating Counter): Uses a 4-state finite state machine per branch instruction:
- Strongly Taken (11)
- Weakly Taken (10)
- Weakly Not Taken (01)
- Strongly Not Taken (00)
Requires TWO consecutive mispredictions to change prediction direction. Highly accurate for loops!
- Branch Target Buffer (BTB): A small cache indexed by branch PC that stores predicted target addresses. If hit, the target is fetched in the very next cycle with 0 stalls!
2. GATE Worked Numerical: 2-Bit Dynamic Predictor Accuracy
Trace loop branches carefully! For a loop executing N times, the branch is TAKEN (N-1) times and NOT TAKEN on the final exit.
Problem: A loop for (int i = 0; i < 4; i++) is executed. The conditional branch at the loop bottom is predicted using a 2-bit saturating predictor initialized to Strongly Not Taken (00). Find the number of mispredictions for the first execution of this loop.
Step 1: Understand branch behavior:
Iteration 1 (i = 0): Loop repeats \implies Branch is TAKEN (T).
Iteration 2 (i = 1): Loop repeats \implies Branch is TAKEN (T).
Iteration 3 (i = 2): Loop repeats \implies Branch is TAKEN (T).
Iteration 4 (i = 3): Loop terminates \implies Branch is NOT TAKEN (NT).
Sequence of outcomes: T, T, T, NT.
Step 2: Trace predictor state transitions:
Initial State: 00 (Strongly Not Taken) \implies Predicts NT.
Branch 1 (Outcome: T): Prediction NT is INCORRECT (Misprediction 1). State moves 00 \to 01 (Weakly Not Taken).
Branch 2 (Outcome: T): Prediction NT is INCORRECT (Misprediction 2). State moves 01 \to 10 (Weakly Taken).
Branch 3 (Outcome: T): Prediction T is CORRECT! State moves 10 \to 11 (Strongly Taken).
Branch 4 (Outcome: NT): Prediction T is INCORRECT (Misprediction 3). State moves 11 \to 10 (Weakly Taken).
Step 3: Total mispredictions = 3 mispredictions out of 4 branch executions.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Rapid GATE-focused conceptual coverage with numericals.
Past-paper-focused approach with clear COA numerical explanations.
Graduate-level depth on how real modern processors are designed.