Control Hazards

Introduction

Control hazards are caused by branch instructions — the pipeline doesn't know which instruction to fetch next until the branch condition is resolved. By the time we figure out whether a branch is taken, we've already fetched several instructions that might be wrong. In modern deep pipelines, mispredicted branches can waste 15-20 cycles of work. Branch prediction — guessing correctly which way a branch will go — is one of the most important performance features in modern CPUs.

The Branch Problem

Consider a conditional branch in a 5-stage pipeline:

The branch condition is evaluated in the EX stage (cycle 3), but we've already fetched the next instruction(s) in cycles 2-3. If the branch is taken, those fetched instructions are wrong and must be discarded (flushed).

Branch penalty = Number of instructions that must be flushed on misprediction.

Branch Prediction

Static Prediction

Always predict not-taken:

• Fetch the next sequential instruction
• If branch is actually taken, flush and redirect
• Works well for forward branches (often not taken)

Always predict taken:

• Assume branches always go to target
• Works well for backward branches (loops usually repeat)

Predict by direction:

• Backward branches → predict taken (loop bodies)
• Forward branches → predict not-taken (error checks, early exits)

Dynamic Prediction

Use past branch behavior to predict future behavior.

1-Bit Predictor:

• Remember: was this branch taken last time?
• Predict same way next time
• Problem: always mispredicts twice at loop boundaries

2-Bit Saturating Counter (most common):

Must mispredict TWICE before changing prediction. This handles loop exits gracefully — one misprediction at loop end doesn't change the prediction for next iteration.

Branch History Table (BHT):

• Table indexed by lower bits of branch instruction address
• Each entry holds a 2-bit predictor
• Thousands of entries for different branches

Correlating Predictors:

• Use global history (last N branch outcomes) to predict current branch
• Different branches are correlated — knowing recent branch history helps

Tournament Predictors:

• Multiple predictors (local + global) compete
• A meta-predictor selects which one to trust for each branch
• Used in modern high-performance CPUs

Branch Target Buffer (BTB)

Prediction isn't just about taken/not-taken — we also need the target address immediately:

During IF: look up current PC in BTB. If found and predicted taken, start fetching from target address immediately — no wasted cycles!

Branch Delay Slot (MIPS)

MIPS uses a clever trick: the instruction AFTER the branch ALWAYS executes, regardless of branch outcome:

The compiler fills this slot with:

1. An instruction from BEFORE the branch (that's always needed)
2. An instruction from the branch target (if safe to execute speculatively)
3. NOP (worst case — wastes the slot)

This eliminates 1 cycle of branch penalty architecturally.

Speculative Execution

Modern CPUs go beyond prediction — they execute down the predicted path:

1. Predict branch direction
2. Fetch AND execute instructions along predicted path
3. Keep results in temporary buffers (not committed to registers/memory)
4. If prediction correct: commit results (fast — work already done!)
5. If prediction wrong: flush pipeline, discard speculative results

This means the CPU does potentially unnecessary work, but correct predictions (95%+ of the time) make it worthwhile.

Modern Branch Prediction Performance

Impact of Pipeline Depth

Branch penalty increases with pipeline depth:

This is why the Pentium 4 (20+ stages) needed extremely good branch prediction — each misprediction cost ~20 cycles!

Key Takeaways

1. Control hazards arise because branch outcomes aren't known until after fetch
2. Branch penalty = cycles wasted on misprediction = pipeline depth before resolution
3. Dynamic prediction (2-bit counters, correlating predictors) achieves 93-97% accuracy
4. Branch Target Buffer provides both prediction AND target address in one cycle
5. Speculative execution proceeds down predicted path; flushes on misprediction
6. Deeper pipelines have higher misprediction penalties, requiring better prediction
7. Branch prediction is one of the most critical performance features in modern CPUs