Dashboard/Block 2: Pipeline & Execution/Week 5
Week 5Pipeline & Execution

Branch Prediction

Branch instructions create control hazards in the pipeline. This week covers static and dynamic branch prediction techniques, including 1-bit and 2-bit saturating counters, the Branch History Table (BHT), and the Branch Target Buffer (BTB).

Learning Objectives

Compare static vs dynamic branch prediction strategies
Trace through 1-bit and 2-bit saturating counter state machines
Calculate branch prediction accuracy and performance impact
Understand BTB structure and operation

Key Concepts

Static Branch Prediction

Static prediction uses fixed rules determined at compile time:

  • -Always Not Taken: predict branch not taken — simple, fetches next sequential instruction
  • -Always Taken: predict branch taken — better for loops
  • -BTFN (Backward Taken, Forward Not Taken): backward branches (loops) are predicted taken, forward branches (if/else) not taken
  • -

    Always Not Taken: 0 penalty on correct prediction, full penalty on misprediction

  • -

    Always Taken: good for loops (typically ~90% of backward branches are taken)

  • -

    BTFN exploits the pattern that backward branches are usually loop-back edges

  • -

    Static prediction accuracy: typically 60-70% across all programs

Dynamic Branch Prediction

Dynamic prediction uses runtime history to predict branches. The 1-bit predictor remembers the last outcome. The 2-bit saturating counter requires two consecutive mispredictions to change the prediction:

  • -SNT (Strongly Not Taken) → WNT (Weakly Not Taken) → WT (Weakly Taken) → ST (Strongly Taken)
  • -Prediction: SNT/WNT → Not Taken, WT/ST → Taken
  • -

    1-bit predictor: changes prediction after every misprediction — poor for loops (misses first and last iteration)

  • -

    2-bit counter: tolerates one anomalous outcome — standard in simple processors

  • -

    BHT (Branch History Table): indexed by lower bits of branch PC, stores predictor state

  • -

    Correlating predictors: use history of recent branches to index the predictor

Branch Target Buffer (BTB)

The BTB caches the target address of previously taken branches. On a branch instruction, the BTB is checked in the IF stage. If there's a hit and the prediction is Taken, the target address is used immediately to fetch the next instruction — eliminating the branch penalty.

  • -

    BTB stores: branch PC (tag) + predicted target address

  • -

    BTB hit + Taken prediction: no penalty (fetch from target next cycle)

  • -

    BTB miss: treated as Not Taken, penalty if actually Taken

  • -

    BTB is typically combined with a BHT for direction prediction

W4: Advanced Pipeline & Hazard ResolutionW6: Out-of-Order Execution