Hazard mitigation — stalling, forwarding - bypassing, branch prediction

We use the classic 5-stage MIPS pipeline: IF (instruction fetch) → ID (decode + register read) → EX (execute/ALU) → MEM (memory access) → WB (write back to register file).

1. WHAT are the three hazard types?

WHY they exist: pipelining overlaps instructions in time, but real dependencies (data flow, control flow) are sequential. Overlap collides with sequence → hazard.

The most common data hazard is RAW (Read-After-Write): instruction $j$ reads a register that instruction $i$ (earlier) is going to write.

2. Stalling (the brute-force fix)

HOW (mechanics): to stall, the hardware does three things in one cycle:

Disable the PC write (don't fetch a new instruction).
Disable the IF/ID register write (freeze the decoded instruction).
Insert a bubble into ID/EX by zeroing the control signals (so the bubble does nothing).

Formula When must a load cause a stall? (derive it)

Let the producing instruction write its result at the end of stage $W$ and the consuming instruction read it at the start of stage $R$ , both measured in cycles after issue. A naive design reads registers in ID and writes in WB. With normal ALU producers, the result exists at the end of EX of instruction $i$ , which is the same cycle as ID of $i+1$ — fixable by forwarding (Section 3). But a load (lw) produces its value only at the end of MEM. If the next instruction needs it in EX, there's a one-cycle gap that forwarding cannot close (you can't send data backward in time). $\text{stall cycles} = \max\big(0,\; (\text{cycle value available}) - (\text{cycle value needed})\big)$ For lw → immediate use: value available end of MEM (cycle 4), needed start of EX (cycle 3) ⇒ 1 stall. This is the famous load-use hazard.

Worked example Load-use stall

lw  $t0, 0($s0)   # produces $t0 at end of MEM
add $t1, $t0, $s1 \# needs$t0 in EX  --> 1 bubble required

cyc	1	2	3	4	5	6
lw	IF	ID	EX	MEM	WB
add	IF	ID	stall	EX	MEM	WB

Why this step? add must hold in ID one extra cycle so that lw's MEM result can be forwarded into its EX. Without the stall, add would read a stale $t0.

3. Forwarding / Bypassing (the smart fix)

HOW — the forwarding conditions (derive them): an instruction in EX has source registers rs, rt. We compare them with the destination registers of the two instructions ahead.

Worked example Forwarding eliminates a stall

sub $t0, $s1, $s2  \#$t0 ready end of EX (cyc 3)
add $t1, $t0, $s3  \# needs$t0 in EX (cyc 4)

No stall! At cycle 4, add is in EX while sub is in MEM. The EX/MEM latch holds $t0. Forward it → add gets the right value with zero bubbles. Why this step? The value already exists in EX/MEM; we just need a wire and a mux, not a wait.

Figure — Hazard mitigation — stalling, forwarding - bypassing, branch prediction

4. Control hazards & Branch Prediction

Mitigations, from dumb to smart:

Stall until resolved — always pay the penalty. Simple, slow.
Predict not-taken — keep fetching the fall-through path; if wrong, flush. Cheap, ~50% accurate.
Delayed branch — execute the instruction after the branch regardless (the "branch delay slot"). Compiler fills it usefully. (Classic MIPS.)
Dynamic branch prediction — learn each branch's behavior at runtime.

4.1 The 2-bit saturating predictor

States: 00 strong-NT → 01 weak-NT → 10 weak-T → 11 strong-T. Taken → increment (saturating at 11); Not-taken → decrement (saturating at 00). Predict Taken if top bit = 1.

Flashcards

What are the three classes of pipeline hazards?

Structural (hardware conflict), Data (value not ready, e.g. RAW), Control (next PC unknown after a branch).

Why can't forwarding remove the load-use stall?

The load value only exists at end of MEM, but the consumer needs it in EX one cycle earlier in time; you cannot forward data backward in time, so ≥1 stall remains.

What three actions implement a one-cycle stall?

Freeze PC (no new fetch), freeze IF/ID register, and insert a bubble by zeroing ID/EX control signals.

EX-hazard forwarding condition (input A)?

EX/MEM.RegWrite ∧ EX/MEM.rd≠0 ∧ EX/MEM.rd = ID/EX.rs → forward EX/MEM ALU result.

Why does the EX/MEM (closer) forward take priority over MEM/WB?

If two earlier instructions write the same register, program order says the most recent write is correct; EX/MEM holds the newer value, so it wins.

Formula for effective CPI with branch prediction?

CPI = 1 + b·m·p (b=branch fraction, m=mispredict rate, p=penalty cycles).

Why is a 2-bit predictor better than 1-bit for loops?

It has hysteresis: a single anomaly (loop exit) doesn't flip the prediction; you must be wrong twice in a row, so loops mispredict ~once instead of twice.

What is a branch delay slot?

The instruction position right after a branch that always executes; the compiler fills it with useful work to hide the branch penalty.

Define forwarding/bypassing.

Routing a result from a pipeline latch (EX/MEM or MEM/WB) directly to a later instruction's ALU inputs, skipping the register file to avoid a stall.

Recall Feynman: explain it to a 12-year-old

Imagine a sandwich shop line where each worker does one step. Sometimes the "add cheese" worker needs the sauce the previous sandwich just got — if the sauce is already on the counter (a latch), the worker can grab it directly instead of waiting for it to go to the fridge and come back (forwarding). But if the sauce is still being made (a load from memory), even grabbing fast won't help — you must wait one beat (stall). And when a customer might suddenly change their order (branch), the line guesses what they'll want and starts making it. A good guesser (2-bit predictor) only changes its guess if it's wrong two times in a row, so one weird customer doesn't throw it off.

Connections

Pipelining basics — 5-stage MIPS
Datapath and control signals
Out-of-order execution and Tomasulo
Caches and memory hierarchy (why lw latency causes load-use stalls)
Amdahl's Law and CPI analysis
Compiler instruction scheduling

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, pipeline ek factory assembly line jaisa hai — 5 stage (IF, ID, EX, MEM, WB) aur har clock pe ek naya instruction enter hota hai, taaki ideal mein 1 instruction per cycle nikle. Lekin problem tab aati hai jab ek instruction ko aisi value chahiye jo pichla instruction abhi tak register file mein likh hi nahi paaya — isko data hazard (RAW) kehte hain. Sabse seedha solution hai stall: ruk jao, ek bubble (NOP) daal do, jab tak value ready na ho. Correct toh hai, par har stall ek cycle waste karta hai.

Smart trick hai forwarding (bypassing). Idea simple hai: ALU ka result EX stage ke end mein EX/MEM latch mein already physically maujood hota hai — bas register file mein nahi gaya abhi. Toh use seedha wire se agle instruction ke ALU input pe bhej do, zero stall! Par ek important baat: load (lw) ki value toh MEM stage ke end mein banti hai, aur agla instruction use EX mein chahiye hota hai jo time mein pehle aata hai. Aap data ko peeche time mein nahi bhej sakte, isliye load-use hazard mein kam se kam 1 stall pakka hota hai — chahe full forwarding ho. Compiler isko hide karne ke liye beech mein ek independent instruction daal deta hai.

Teesra hazard hai control hazard — branch ke baad pata hi nahi chalta ki next kaunsa instruction fetch karein. Tab tak hum galat instructions fetch kar lete hain, jinhe flush karna padta hai = branch penalty. Iska maths simple hai: $\text{CPI} = 1 + b\cdot m\cdot p$ , jahan $b$ branch fraction, $m$ mispredict rate, $p$ penalty cycles. Isliye branch prediction lagate hain — 2-bit saturating counter loops ke liye best hai kyunki usme hysteresis hota hai: ek anomaly (loop exit) se prediction nahi badalti, do baar galat hona padta hai. Yaad rakho: "Stall when you must, Forward when you can, Predict when you guess."

Hazard mitigation — stalling, forwarding - bypassing, branch prediction

1. WHAT are the three hazard types?

2. Stalling (the brute-force fix)

3. Forwarding / Bypassing (the smart fix)

4. Control hazards & Branch Prediction

4.1 The 2-bit saturating predictor

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections