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

4.1.19 · Coding › Computer Architecture (Deep)

Classic 5-stage RISC pipeline (hum ise poore note mein use karte hain):

Stage	Name	Kya karta hai
IF	Instruction Fetch	memory se instruction padhna
ID	Instruction Decode	decode + registers padhna
EX	Execute	ALU result compute karta hai
MEM	Memory access	load/store data
WB	Write Back	result register file mein likhna

1. Core problem: hazards KYUN hote hain

Yeh hote kyun hain? Kyunki pipelining assume karti hai ki instructions itni independent hain ki simultaneously in-flight ho sakti hain. Real programs ise violate karte hain:

Woh hardware share karte hain (ek memory, ek register file) → structural hazard.
Woh ek doosre ke data par depend karte hain (ek value produce karta hai jo agla consume karta hai) → data hazard.
Woh control flow change karte hain (branches decide karte hain ki kaun si instruction aage aayegi, lekin hum kuch aur pehle hi fetch kar chuke hain) → control hazard.

Teen families. Har ek ka WHY yaad rakho, sirf naam nahi.

2. Structural hazards

Classic case KAUNSA hai? Ek single, unified memory jo dono instruction fetch (IF) aur data access (MEM) ke liye use hoti hai. Cycle grid dekho:

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

c4 mein, I1 MEM (data memory) mein hai aur I4 IF (instruction memory) mein hai. Agar dono ek hi memory port share karein, toh collision hoga.

FIX KAISE KAREIN?

Stall I4 ko ek cycle (bubble insert karo) — sasta lekin speed kam karta hai.
Resource duplicate karo — alag I-cache aur D-cache (Harvard-style). Isliye real CPUs mein split L1 caches hote hain. Structural hazard ko design se hi remove karna preferred fix hai.

3. Data hazards — RAW, WAR, WAW

Hum classify karte hain accesses ke order se, jaise program order mein dikh raha hai. Maano instruction $i$ pehle aata hai instruction $j$ se.

3.1 RAW — Read After Write (ek true dependence)

$j$ ek aisa operand read karne ki koshish karta hai jo $i$ ko pehle write karna chahiye.

Worked example RAW

I1: ADD R1, R2, R3   # R1 = R2 + R3   (R1 ko WB mein likhta hai, cycle 5)
I2: SUB R4, R1, R5    # R1 ko ID mein padhta hai, cycle 3

Yeh hazard kyun hai? I1 R1 ko WB (c5) tak nahi likhta, lekin I2 R1 ko ID (c3) mein padhta hai. Naively, I2 purana R1 padh leta hai.

	c1	c2	c3	c4	c5
I1 ADD	IF	ID	EX	MEM	WB ← R1 likha gaya
I2 SUB		IF	ID ← R1 chahiye	EX	MEM

Value I1 ke EX (c3) ke end tak compute ho jaati hai lekin c5 tak write nahi hoti. Gap = hazard.

RAW FIX KAISE KAREIN:

Forwarding / bypassing — ALU result ko directly EX/MEM pipeline register se agli instruction ke EX input mein route karo, WB se pehle. Yeh zyaadaatar RAW stalls khatam kar deta hai.
Load-use hazard — woh ek RAW jo forwarding poori tarah remove nahi kar sakta: load ki value MEM (c4) ke end tak ready nahi hoti, lekin dependent instruction ko EX (c4) mein chahiye. Aapko ek stall (bubble) insert karna padega, phir forward karo.
Stall universal fallback ke roop mein.

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

$j$ ek register write karne ki koshish karta hai usse pehle ki $i$ ne use read kiya ho.

Yeh hamare simple in-order pipeline mein kyun nahi ho sakta? Kyunki reads ID (early) mein hote hain aur writes WB (late) mein, aur instructions order mein flow karte hain. I1 (pehle wala) ID mein read karta hai I2 (baad wale) ke WB mein likhne se pehle. WAR & WAW tabhi real hazards bante hain jab out-of-order execution ho ya jab writes early stages mein ho sakti hain.

3.3 WAW — Write After Write (ek output dependence)

$i$ aur $j$ dono same register likhte hain; final value $j$ ka (baad wala) write hona chahiye.

Worked example WAW

I1: MUL R1, R2, R3   # slow, R1 late likhta hai
I2: ADD R1, R4, R5    # fast, R1 early likhta hai

Agar MUL zyaada time le aur R1 ko ADD ke baad likhe, toh R1 mein galat (purani) value aa jaayegi.

KAISE handle hota hai: register renaming (har write ko ek fresh physical register do) WAR aur WAW dono ko khatam kar deta hai. Yeh name dependences hain (register names reuse karne se hote hain), true data flow nahi — RAW hi ek true dependence hai.

4. Control (branch) hazards

KYUN: Branch late resolve hota hai (maano EX/MEM mein), lekin IF ko agla instruction turant fetch karna hota hai. Toh hum branch ke baad wali instructions tab fetch karte hain jab yeh nahi pata ki unhe run karna chahiye ya nahi.

FIX KAISE KAREIN:

Stall/flush jab tak branch resolve ho — branch-penalty cycles ka cost aata hai.
Predict (not-taken, ya Branch History Table se dynamic prediction). Mispredict hone par, galat fetched instructions ko flush karo.
Delayed branch — agli slot (branch delay slot) ko hamesha execute hone ke liye define karo; compiler ise usefully fill karta hai (purana MIPS).

Performance cost (derive karo)

Maano base pipeline CPI = 1 (ideal). Maano $b$ fraction instructions branches hain, branch penalty hai $p$ cycles per mispredicted/taken branch, aur misprediction rate $m$ hai.

First principles se derivation — average cycles per instruction = ideal cycles + extra stall cycles: $CPI = 1 + (stall cycles per instruction)$ Har branch $p$ penalty cycles contribute karta hai sirf tab jab mispredict ho, probability $m$ ke saath. Branches saari instructions ka $b$ fraction hain, toh: $CPI = 1 + b \cdot m \cdot p$

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

5. Ek nazar mein summary

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

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek sandwich banane wali line: ek banda bread laata hai, doosra cheese laata hai, sab ek saath kaam karte hain. Structural takleef: do workers ko ek hi chhuri ek hi waqt chahiye — doosri chhuri khareed lo. Data takleef: cheese-wale ko woh bread chahiye jo abhi rakhi hi nahi gayi — ya toh ruko, ya bread seedha directly pakdao kounter par rakhne ka intezaar kiye bina (yahi forwarding hai). Control takleef: ek sign kehta hai "agar customer vegetarian hai toh alag sandwich banao," lekin tune sign padhne se pehle meatballs banana shuru kar diya — ab meatball sandwich phenkni padegi aur dobara shuru karna padega (flush). Accha andaza (prediction) matlab rarely kaam waste hota hai.

Flashcards

Pipeline hazard define karo

Ek aisi situation jo agli instruction ko uske slot mein execute hone se rokti hai, jab stages overlap karte hain toh correctness ya resource problem ki wajah se.

Teen families of hazards

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

Structural hazard ka classic example

Single unified memory jo IF aur MEM dono ek hi cycle mein use karte hain; split karke I-cache aur D-cache fix karta hai.

RAW hazard ka matlab

Read After Write — baad wali instruction ek register padhti hai jo pehle wali ne abhi likha nahi; yeh ek hi TRUE data dependence hai.

WAR hazard ka matlab

Write After Read — baad wali instruction ek register likhti hai pehle wali ke padhne se pehle; yeh ek anti-dependence (name dependence) hai.

WAW hazard ka matlab

Write After Write — do instructions same register likhti hain; final value baad wali ki honi chahiye; yeh ek output (name) dependence hai.

Simple in-order pipeline mein WAR/WAW kyun nahi

Reads early hote hain (ID), writes late hote hain (WB), aur instructions order mein flow karte hain, isliye pehle wali instruction hamesha pehle read/write karti hai.

RAW ke liye primary fix

Forwarding/bypassing — ALU result ko pipeline register se agli EX input tak pohnchaana.

Kaun sa RAW forwarding ke baad bhi stall chahta hai

Load-use: load ki value MEM ke end tak ready nahi hoti, itni der mein dependent instruction ke EX mein forward karna impossible; ek bubble insert karo.

WAR aur WAW ka fix

Control hazard ka cause

Branch outcome/target pata nahi hota jab agla instruction fetch karna hota hai.

Branch penalty CPI formula

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

Stalls ke saath pipeline speedup

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

Delayed branch slot

Branch ke baad wali instruction jo hamesha execute hoti hai; compiler ise usefully fill karta hai.

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