Control hazards and pipeline flushes

What Is a Control Hazard?

Why "control"? Because branches control the flow of execution—they decide which instruction comes next. Unlike data hazards (operand dependencies), control hazards are about which instruction to execute, not which data to use.

When Control Hazards Strike

Consider a5-stage pipeline (IF, ID, EX, MEM, WB):

Cycle 1: Branch instruction enters IF
Cycle 2: Branch enters ID (decode condition, compute target)
Cycle 3: Branch enters EX (resolve condition: taken or not?)
Meanwhile: We've already fetched PC+4 in cycle 2 and PC+8 in cycle 3

If the branch is taken at cycle 3, instructions at PC+4 and PC+8 are from the wrong path. They must be flushed (converted to no-ops).

The Branch Decision Timeline

Formula Branch Resolution Delay

For a classic 5-stage RISC pipeline where branches resolve in EX: $\text{Branch Penalty} = \text{(Stage where branch resolves)} - \text{(Stage where fetch occurs)}$

Derivation:

Branch enters IF at cycle $t$
Branch resolves at EX at cycle $t + 2$ (IF → ID → EX)
By cycle $t + 2$ , we've fetched instructions for cycles $t+1$ (ID stage) and $t+2$ (IF stage)
If branch taken, we discard 2 instructions $\text{Instructions to flush} = 2 \text{ (for EX resolution)}$

If we could resolve earlier (e.g., in ID with dedicated comparators), flush count = 1.

Why this matters: Each flushed instruction is a wasted cycle. A program with 20% branches and 2-cycle penalty loses $0.2 \times 2 = 0.4$ cycles per instruction on average—a 40% performance hit!

Pipeline Flush Mechanism

How to Flush: The Control Signal Kill Switch

Step-by-step:

Detect misprediction: In EX stage, compare branch condition result with prediction (or assume static "not taken")
If (misprediction):
- Set PC = branch_target (from EX/MEM pipeline register)
- Inject pipeline bubles into IF/ID and ID/EX registers
Bubble implementation: Force control signals to 0:
- RegWrite = 0 (don't write registers)
- MemWrite = 0 (don't write memory)
- ALUOp = 0 (harmless NOP operation)

Why bubles, not just "delete"? The pipeline stages are synchronized. You can't remove an instruction mid-flight—it would desynchronize the pipeline. Instead, you convert it to a do-nothing operation that flows through like a normal instruction but changes nothing.

Worked example Flushing Two Instructions

Code:

100: BEQ R1, R2, 200   # Branch to 200 if R1 == R2
104: ADD R3, R4, R5    # Wrong-path instruction 1
108: SUB R6, R7, R8    # Wrong-path instruction 2
...
200: OR R9, R10, R11   # Correct target

Cycle-by-cycle (branch taken): | Cycle | IF | ID | EX | MEM | WB | |-------|----------|-------------|-----| | 1 | BEQ@100 | ... | ... | ... | ... | | 2 | ADD@104 | BEQ@100 | ... | ... | ... | | 3 | SUB@108 | ADD@104 | BEQ@100 ✓ | ... | ... | | 4 | OR@200 | BUBBLE | BUBBLE | BEQ | ... | | 5 | ... | OR@200 | BUBBLE | ... | BEQ | Why cycle 3? BEQ resolves in EX: R1 == R2 is true, so branch is taken.

Why flush ADD and SUB? They entered the pipeline assuming BEQ was not taken (PC incremented by 4 each cycle). Now we know they shouldn't execute.

Cycle 4: OR@200 (correct instruction) is fetched. ADD and SUB become bubles (shown as BUBBLE in the table—they do nothing in EX and MEM).

Cost: 2 wasted cycles (the cycles ADD and SUB spent in the pipeline before becoming bubbles).

Types of Branch Prediction (Flush Avoidance)

To reduce flushes, processors predict branch outcomes:

1. Static Prediction

Why predict not-taken? Simpler hardware (no prediction table). Works well for forward branches (if-then-skip patterns).

2. Static Predict-Taken

Assume all branches are taken. Fetch target address speculatively.

Problem: Must compute target in ID (needs ader + PC forwarding)
Flush if not taken: $\text{Penalty} = 1 \text{ cycle (ID resolution)} \times P(\text{not taken})$

3. Dynamic Prediction (Branch Prediction Buffer)

Use a Branch History Table (BHT) indexed by PC:

$\text{BHT index} = \text{PC}[n:2] \mod 2^k$

where $k$ is the number of index bits (e.g., 10 bits = 1024 entries).

Each entry: 1-bit or 2-bit saturating counter

2-bit counter states: Strongly Taken (11) → Weakly Taken (10) → Weakly Not-Taken (01) → Strongly Not-Taken (00)
Prediction: Taken if counter ≥ 10 (binary)

Why 2 bits? Tolerates one misprediction in a loop (e.g., exit condition). A 1-bit predictor would mispredict twice: loop entry and loop exit.

Worked example 2-Bit Predictor for Loop

Code:

for (i = 0; i < 100; i++) {
    // loop body
    BEQ continue_loop  # Taken99 times, not taken 1 time
}

1-bit predictor:

Predicts Taken (correct 99 times)
Loop exits (not taken) → misprediction #1
Next loop: Predicts Not-Taken (wrong!) → misprediction #2
Total: 2 mispredictions per loop (entry + exit)

2-bit predictor (starts at Strongly Taken = 11):

99 iterations: Taken (correct), counter stays11
Exit: Not-Taken → counter drops to 10 (Weakly Taken), misprediction #1
Next loop: Still predicts Taken (counter = 10) → correct!, counter back to 11
Total: 1 misprediction per loop (exit only)

Why this works: The 2-bit counter requires two consecutive wrong predictions to flip the prediction. One exit doesn't fully change the "trend."

Common Mistakes in Understanding Control Hazards

Advanced: Branch Target Buffer (BTB)

Combined with BHT: Modern CPUs use both:

BTB tells where to jump (if branch is taken)
BHT tells whether to jump (taken vs. not-taken prediction)

Recall Explain to a 12-Year-Old (Feynman Technique)

Imagine you're reading a "Choose Your Own Adventure" book. At the bottom of page 10, it says, "If you fight the dragon, turn to page 45. If you run away, turn to page 12."

You have to make a choice, but here's the trick: your friend is already reading ahead for you to save time. Before you decide, they've started reading page 12 (assuming you'll run away).

But then you choose to fight! Now your friend has to throw away everything they read from page 12 (it's the wrong story path) and start over at page 45. The time they spent reading the wrong page is wasted—that's the "pipeline flush."

A "branch predictor" is like your friend guessing what you'll choose based on what you picked last time. If they guess right, no time wasted! If they guess wrong, they have to backtrack. The better they guess, the faster you get through the book.

Connections

5.2.01-Pipelining-fundamentals — Control hazards are one of three hazard types (structural, data, control)
5.2.05-Data-hazards-and-forwarding — Data hazards also cause stalls, but forwarding helps; control hazards require flushing (no forwarding for PC)
5.2.09-Branch-prediction-techniques — Dynamic predictors (2-bit, gshare, perceptron) improve accuracy
5.2.11-Speculative-execution — Modern CPUs speculatively execute both paths, commit the correct one
4.3.08-Branch-instructions — ISA-level view of branch types (conditional, unconditional, register-indirect)

Flashcards

#flashcards/hardware

What is a control hazard in a pipelined processor? :: A hazard that occurs when the pipeline cannot determine the next instruction to fetch because a branch instruction's outcome is not yet resolved, requiring the pipeline to stall, predict, or flush wrong-path instructions.

Why must a pipeline flush instructions after a mispredicted branch?

Because the pipeline speculatively fetched instructions from the wrong path (assuming the branch was not taken). These instructions must be converted to no-ops (bubbles) to prevent them from modifying architectural state incorrectly.

How is a pipeline flush implemented in hardware?

By injecting bubles (no-ops) into the IF/ID and ID/EX pipeline registers, setting control signals (RegWrite, MemWrite) to 0 so the wrong-path instructions do nothing as they flow through EX, MEM, and WB stages.

What is the branch penalty for a 5-stage pipeline that resolves branches in the EX stage?

2 cycles (the instructions at PC+4 and PC+8 must be flushed if the branch is taken), assuming no branch prediction or static predict-not-taken.

Why does a 2-bit branch predictor outperform a 1-bit predictor for loops?

A 2-bit predictor requires two consecutive mispredictions to change its prediction, so a single loop exit doesn't flip the predictor. A 1-bit predictor mispredicts both the loop exit (not taken) and the next loop entry (predicts not-taken from the exit, but loop re-enters with taken), causing 2 mispredictions per loop.

What is the difference between a Branch History Table (BHT) and a Branch Target Buffer (BTB)?

A BHT predicts whether a branch is taken (direction), while a BTB stores the target address of taken branches to avoid computing it in the ID stage. Modern CPUs use both together.

Why can't control hazards be solved by forwarding like data hazards?

Forwarding passes data from later pipeline stages to earlier ones for the same instruction stream. Control hazards require changing which instructions are in the pipeline (flushing wrong-path instructions and fetching new ones), not just passing data forward.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Control hazards pipeline mek badi dikat hai boss. Socho, tumhara processor ek car ki tarah chal raha hai jo highway pe bahut tez ja rahi hai. Har secondek naya instruction pipeline me aa raha hai—bilkul assembly line ki tarah. Lekin jab ek branch instruction ata hai (matlab BEQ ya BNE jo decide karta hai ki PC kahan jayega), tab problem shuru hoti hai kyunki branch ka result pata nahi chalta until EX stage me pahunch jaye. Tab tak processor already do ya teen age ke instructions fetch kar chuka hota hai, assuming ki branch "not taken" tha. Agar branch actually taken nikla, to wo already-fetched instructions galat path ke hain! Ab processor ko flush karna padta hai—matlab un wrong instructions ko bubles (no-ops) me convert karna padta hai taki wo kuch change na karein registers ya memory me.

Iska cost bahut heavy hai bhai. Har flush pe do cycles waste hote hain (agar branch EX stage me resolve ho). Agar program me 20% branches hain aur har ek taken branch pe2 cycles penalty lagti hai, to overall performance ka40% loss ho sakta hai without any optimization! Isliye modern processors branch prediction use karte hain—ek educated guess lagana ki branch taken hoga ya nahi. Simple approach hai static predict-not-taken, lekin better approach hai dynamic prediction jisme ek 2-bit counter history dekh ke prediction improve karta hai. Loop wale code me ye bahut kaam ata hai kyunki loop 99 baar taken hota hai aur ek baar not-taken (exit condition), to2-bit predictor ye pattern seekh leta hai aur sirf ek baar mispredict karta hai instead of dobaar.

Samajhne ka simple tarika: jaise tum raste me chal rahe ho aur ek fork aya. Tumhara dost already left side ka rasta explore kar raha hai (speculative fetch), lekin tumne right side choose kar liya. Ab dost ko wapas ake right wala rasta explore karna padega—wo jo left pe time lagaya wo waste ho gaya. Yahi pipeline flush ka concept hai. Branch prediction matlab dost ko zyada accurate guess lagana based on past experience, taki kam baar galat rasta explore kare.

Ek aur chez: modern CPUs ke pas Branch Target Buffer (BTB) bhi hota hai jo branch ke target address ko cache kar leta hai taki next time same branch aye to turant target address mil jaye bina compute kiye. Ye sab milke control hazard ka performance hit kam karte hain, lekin misprediction penalty kabhi pura zero nahi hoti. Deep pipelines (14+ stages) me ek misprediction ka cost aur bhi zyada hota hai, isliye branch prediction accuracy crucial hai high-performance processors ke liye.

What Is a Control Hazard?

When Control Hazards Strike

The Branch Decision Timeline

Pipeline Flush Mechanism

How to Flush: The Control Signal Kill Switch

Types of Branch Prediction (Flush Avoidance)

1. Static Prediction

2. Static Predict-Taken

3. Dynamic Prediction (Branch Prediction Buffer)

Common Mistakes in Understanding Control Hazards

Advanced: Branch Target Buffer (BTB)

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Processor Datapath & Pipelining

Connections