Pipeline hazards — structural, data (RAW - WAR - WAW), control

The classic 5-stage RISC pipeline (we use this throughout):

Stage	Name	What it does
IF	Instruction Fetch	read instruction from memory
ID	Instruction Decode	decode + read registers
EX	Execute	ALU computes result
MEM	Memory access	load/store data
WB	Write Back	write result into register file

1. The core problem: WHY hazards exist

WHY do they happen at all? Because pipelining assumes instructions are independent enough to be in flight simultaneously. Real programs violate this:

They share hardware (one memory, one register file) → structural hazard.
They depend on each other's data (one produces a value the next consumes) → data hazard.
They change the control flow (branches decide which instruction comes next, but we already fetched something) → control hazard.

Three families. Memorize the WHY of each, not just the name.

2. Structural hazards

WHAT is the classic case? A single, unified memory used for both instruction fetch (IF) and data access (MEM). Look at the cycle grid:

        c1  c2  c3  c4  c5
I1:     IF  ID  EX  MEM WB
I2:         IF  ID  EX  MEM
I3:             IF  ID  EX
I4:                 IF  ID  EX ...

In c4, I1 is in MEM (data memory) and I4 is in IF (instruction memory). If both share one memory port, they collide.

HOW do we fix it?

Stall I4 one cycle (insert a bubble) — cheap but slows you down.
Duplicate the resource — separate I-cache and D-cache (Harvard-style). This is why real CPUs have split L1 caches. Removing the structural hazard by design is the preferred fix.

3. Data hazards — RAW, WAR, WAW

We classify by the order of accesses as seen in program order. Let instruction $i$ come before instruction $j$ .

3.1 RAW — Read After Write (a true dependence)

$j$ tries to read an operand that $i$ must write first.

Worked example RAW

I1: ADD R1, R2, R3   # R1 = R2 + R3   (writes R1 in WB, cycle 5)
I2: SUB R4, R1, R5    # reads R1 in ID, cycle 3

Why is this a hazard? I1 doesn't write R1 until WB (c5), but I2 reads R1 in ID (c3). Naively, I2 reads the old R1.

	c1	c2	c3	c4	c5
I1 ADD	IF	ID	EX	MEM	WB ← R1 written
I2 SUB		IF	ID ← needs R1	EX	MEM

The value is computed by end of I1's EX (c3) but only written at c5. Gap = hazard.

HOW to fix RAW:

Forwarding / bypassing — route the ALU result directly from the EX/MEM pipeline register back into the EX input of the next instruction, before WB. This kills most RAW stalls.
Load-use hazard — the one RAW that forwarding cannot fully remove: a load's value isn't ready until end of MEM (c4), but a dependent instruction needs it in EX (c4 too). You must insert one stall (bubble), then forward.
Stall as the universal fallback.

3.2 WAR — Write After Read (an anti-dependence)

$j$ tries to write a register before $i$ has read it.

WHY can't this happen in our simple in-order pipeline? Because reads happen in ID (early) and writes happen in WB (late), and instructions flow in order. I1 (earlier) reads in ID before I2 (later) writes in WB. WAR & WAW only become real hazards with out-of-order execution or when writes can occur in early stages.

3.3 WAW — Write After Write (an output dependence)

$i$ and $j$ both write the same register; the final value must be $j$ 's (later) write.

HOW handled: register renaming (give each write a fresh physical register) eliminates WAR and WAW entirely. They are name dependences (caused by reusing register names), not true data flow — RAW is the only true dependence.

4. Control (branch) hazards

WHY: A branch is resolved late (say in EX/MEM), but IF must fetch the next instruction immediately. So we fetch instructions after the branch before knowing if they should run.

HOW to fix:

Stall/flush until branch resolves — costs branch-penalty cycles.
Predict (not-taken, or dynamic prediction with a Branch History Table). On mispredict, flush the wrongly-fetched instructions.
Delayed branch — define the next slot (the branch delay slot) to always execute; compiler fills it usefully (old MIPS).

Performance cost (derive it)

Let the base pipeline CPI = 1 (ideal). Suppose a fraction $b$ of instructions are branches, the branch penalty is $p$ cycles per mispredicted/taken branch, and misprediction rate $m$ .

Derivation from first principles — average cycles per instruction = ideal cycles + extra stall cycles: $\text{CPI} = 1 + (\text{stall cycles per instruction})$ Each branch contributes $p$ penalty cycles only when mispredicted, with probability $m$ . Branches are a fraction $b$ of all instructions, so: $\boxed{\;\text{CPI} = 1 + b\cdot m\cdot p\;}$

Figure — Pipeline hazards — structural, data (RAW - WAR - WAW), control

5. One-glance summary

Hazard	Cause	Type	Primary fix
Structural	resource conflict	hardware	duplicate resource (split caches)
RAW	true data dependence	data	forwarding (+1 stall for load-use)
WAR	anti-dependence	name	register renaming
WAW	output dependence	name	register renaming
Control	unknown branch outcome	control	prediction + flush, delay slot

Recall Feynman: explain to a 12-year-old

Imagine a sandwich-making line: one person adds bread, the next adds cheese, etc., all working at once. Structural trouble: two workers need the same single knife at the same moment — buy a second knife. Data trouble: the cheese-person needs the bread that hasn't been placed yet — either wait, or hand the bread over directly instead of waiting for it to be put on the counter (that's forwarding). Control trouble: a sign says "make a different sandwich if the customer is vegetarian," but you already started making meatballs before you read the sign — you have to throw away the meatball sandwich and start over (flush). Good guessing (prediction) means you rarely waste work.

Flashcards

Define a pipeline hazard

A situation preventing the next instruction from executing in its slot, due to a correctness or resource problem when stages overlap.

Three families of hazards

Structural (resource conflict), Data (RAW/WAR/WAW), Control (branch).

Structural hazard classic example

Single unified memory used by IF and MEM in the same cycle; fixed by splitting into I-cache and D-cache.

RAW hazard meaning

Read After Write — a later instruction reads a register an earlier one hasn't written yet; the only TRUE data dependence.

WAR hazard meaning

Write After Read — later instruction writes a register before earlier one reads it; an anti-dependence (name dependence).

WAW hazard meaning

Write After Write — two instructions write the same register; final value must be the later one's; an output (name) dependence.

Why no WAR/WAW in simple in-order pipeline

Reads happen early (ID), writes happen late (WB), and instructions flow in order, so the earlier instruction always reads/writes first.

Primary fix for RAW

Forwarding/bypassing the ALU result from a pipeline register to the next EX input.

Which RAW needs a stall even with forwarding

Load-use: a load's value isn't ready until end of MEM, too late to forward into the dependent instruction's EX; insert one bubble.

Fix for WAR and WAW

Control hazard cause

Branch outcome/target unknown when the next instruction must be fetched.

Branch penalty CPI formula

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

Pipeline speedup with stalls

Speedup = k / (1 + s), k stages, s = average stall cycles per instruction.

Delayed branch slot

The instruction right after a branch that always executes; compiler fills it usefully.

Connections

Instruction Pipelining basics
Forwarding and bypassing
Branch prediction (static vs dynamic)
Out-of-order execution and Tomasulo
Register renaming
Cache hierarchy (I-cache vs D-cache)
CPI and performance equation
Amdahl's Law

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, pipeline ek assembly line jaisa hai — har clock cycle me ek nayi instruction andar ghusti hai aur paanch stages (IF, ID, EX, MEM, WB) me parallel kaam hota hai. Problem tab aati hai jab instructions ek-doosre pe depend karti hain ya ek hi hardware maangti hain. Isko hi hazard bolte hain. Teen type: structural (resource ki ladai, jaise ek hi memory ko IF aur MEM dono ek saath maang rahe), data (ek instruction ka result doosri ko chahiye), aur control (branch ka result pata nahi, isliye galat instruction fetch ho gayi).

Data hazards me sabse important hai RAW (Read After Write) — yeh ek sachchi dependence hai, kyunki sach me ek value pehle banni chahiye phir use honi chahiye. Iska fix hai forwarding: ALU ka result seedha agle instruction ke EX me bhej do, WB ka wait mat karo. Lekin ek case me forwarding bhi fail hota hai — load-use: load ki value MEM ke end me aati hai, tab tak agli instruction ko EX me chahiye thi, isliye ek bubble (stall) daalna padta hai. WAR aur WAW sirf naam ki dependence hain (same register naam reuse karne ki wajah se), inko register renaming se khatam kar dete hain — simple in-order pipeline me toh yeh aate hi nahi kyunki read jaldi (ID) aur write der se (WB) hota hai.

Control hazard ka matlab: branch lega ya nahi, yeh EX me decide hota hai, par fetch toh pehle ho gaya. Isliye ya toh predict karo, galat nikla toh flush kar do, ya delay slot use karo. Cost ka formula yaad rakho: $CPI = 1 + b \cdot m \cdot p$ — yani sirf branches (fraction $b$ ), unme se jo mispredict ( $m$ ) hue, unka penalty ( $p$ ). Isiliye accha branch predictor banana itna important hai — chhota sa $bmp$ bhi pura performance bigaad sakta hai. Bas yaad rakho: sirf RAW asli hai, baaki naam ke chakkar hain.

Pipeline hazards — structural, data (RAW - WAR - WAW), control

1. The core problem: WHY hazards exist

2. Structural hazards

3. Data hazards — RAW, WAR, WAW

3.1 RAW — Read After Write (a true dependence)

3.2 WAR — Write After Read (an anti-dependence)

3.3 WAW — Write After Write (an output dependence)

4. Control (branch) hazards

Performance cost (derive it)

5. One-glance summary

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections