Visual walkthrough — Load-use hazard and stalls

5.2.7 · D2 · Hardware › Processor Datapath & Pipelining › Load-use hazard and stalls

Yeh page parent topic ke central result ko bilkul zero se rebuild karta hai. Agar koi word unfamiliar lagta hai, toh use hone se pehle uski picture milegi.

Step 1 — Pipeline stage asal mein hoti kya hai

KYA HAI. Ek modern processor ek instruction finish karne ke baad agla nahi shuru karta. Woh kaam ko paanch chote workshops mein baant deta hai aur instruction ko ek clock beat mein ek karte hue unme se guzarne deta hai, bilkul jaise ek gaadi assembly line pe. Paanch workshops (Five-stage MIPS pipeline) yeh hain:

• IF — Instruction Fetch: instruction ko memory se uthao.
• ID — Instruction Decode: uske zaroori register values padho.
• EX — Execute: ALU arithmetic karta hai.
• MEM — Memory: data memory se baat karo (sirf loads/stores yeh use karte hain).
• WB — Write Back: result ko register mein likho.

YEH PAANCH HI KYUN, ek bada blob kyun nahi? Kyunki agar har workshop har beat busy ho, toh aap har five beats mein ek ki jagah (lagbhag) har beat mein ek instruction finish karte ho. Yahi pipelining ka poora point hai — throughput.

PICTURE. Neeche, ek instruction ek horizontal strip hai jo daayein slide kar rahi hai, machine ki har drumbeat pe ek box. Woh drumbeat wahi hai jo hum ab naam dene wale hain.

Step 2 — Do instructions stack karna: diagonal

KYA HAI. Do instructions pipeline mein back-to-back daalo. Doosri wali pehli se ek cycle baad start hoti hai. Dono draw karo aur woh ek staircase bana leti hain — har instruction ki strip upar wali se ek box daayein shift hoti hai.

DIAGONAL KYUN? Kyunki pipeline har cycle mein sirf ek nayi instruction fetch kar sakti hai. Toh instruction #2 IF mein tab tak nahi ghus sakti jab tak #1 IF nahi chod deti. Yeh forced ek-cycle offset is page ki har timing kahani ka source hai — ise yaad rakho.

PICTURE. Do strips, ek se offset. Peele "offset" arrow ko follow karo: doosri row exactly ek cycle daayein dhakeli gayi hai.

Ab hum exact cycles pin karte hain jahan har stage land karta hai. Agar instruction #1 cycle 1 mein IF shuru kare:

Yeh do numbers yaad rakho: #1 ka MEM cycle 4 hai, aur #2 ka EX cycle 4 hai. Woh collide karte hain. Step 4 mein woh collision bite karta hai.

Step 3 — Value produce kab hoti hai, aur chahiye kab hoti hai?

KYA HAI. Har instruction ka ek moment hota hai jab woh apna result produce karti hai aur ek moment jab follower ko woh chahiye hota hai. Dono ko clock pe locate karna hoga.

• Ek normal ALU instruction (jaise add) apna answer EX ke dauran produce karta hai.
• Ek load (lw) compute nahi karta — woh memory read karta hai, toh woh apni value MEM ke dauran produce karta hai.
• Jo bhi instruction ALU ko feed karne ke liye registers read karti hai, use woh values EX ke start mein chahiye hoti hain.

YEH MOMENT KYUN MATTERS? Kyunki hum poochne wale hain: kya hum value time pe hand over kar sakte hain? Time pe hand-off tabhi kaam karta hai jab produced ≤ needed ho. Agar value baad mein paida ho jab wo chahiye ho, toh koi clever wiring nahi bachayegi.

PICTURE. Do vertical event-markers: ek green "PRODUCED" flag aur ek red "NEEDED" flag, ek load aur uske follower ke liye wahan rakhe gaye jahan har event hota hai.

Step 3b — Actual forwarding wires (taaki kuch bhi hand-wave na ho)

KYA HAI. "Forwarding" koi ek magic wire nahi hai; yeh ek choti, fixed set of named bypass paths hai. Har path ek pipeline register se start hoti hai (ek latch jiska naam do stages ke beech ke liye hai, jaise EX/MEM EX ke baad aur MEM se pehle ek result hold karta hai) aur consumer input pe khatam hoti hai:

• EX/MEM → EX: pichli instruction ka EX result, ek cycle purana, is instruction ke ALU mein. (Back-to-back add→add fix karta hai.)
• MEM/WB → EX: do cycles purana result (EX/MEM se, ya load ki memory value) ALU mein. (add→gap→add fix karta hai, aur — stall ke baad — load→add.)
• MEM/WB → MEM: ek value baad wale store ke store-data port mein deliver hoti hai. (load→store fix karta hai, Step 6.)
• MEM/WB → ID: ek value ID mein baithe early-resolving branch ke register-compare inputs mein route hoti hai. (Sirf Step 7 ke branch case ke liye chahiye; wahan draw ki gayi hai.)

SAB KO NAME KYUN KIYA? Kyunki poora load-use argument yahi hai: "inme se kaunsi wires time pe reach kar sakti hain, aur kaunsi nahi." Step 4 mein impossible path precisely MEM/WB → EX usi cycle mein hai jab memory read ho raha hai — woh path physically exist nahi karta kyunki value abhi MEM/WB latch mein nahi hai.

PICTURE. IF·ID·EX·MEM·WB ka ek stage strip jisme bypass arrows draw aur source latch aur destination input ke saath labelled hain.

Step 4 — Collision: load ki value ek cycle der se paida hoti hai

KYA HAI. Classic pair lo aur produce/need flags ko real cycle numbers pe overlay karo:

lw   $2, 20($1)     # dest reg: MEM mein produce hota hai
add  $4, $2, $3     # us reg ki value: EX ke start mein chahiye

Step 2 se: load ka MEM cycle 4 hai; add ka EX cycle 4 hai.

• Load ka $2 cycle 4 ke end tak ready nahi hoga (memory read tabhi khatam hota hai).
• add ko $2 cycle 4 ke start mein chahiye (uska ALU tab fire karta hai).

FORWARDING KYUN NAHI BACHA SAKTA. Ek forwarding wire spatial hai: yeh ek value stages ke beech sideways move karti hai, clock time mein hamesha forward (is cycle mein ya baad wali cycle mein). Yahaan need cycle 4 ke start par hoti hai aur value cycle 4 ke end par aati hai — usi cycle ke andar baad mein. Ise satisfy karne ke liye aapko ek MEM/WB → EX wire chahiye hogi jo MEM/WB latch load hone se pehle fire kare, yaani ek value ek cycle ke andar peeche time mein flow kare — physically impossible. ALU-ALU case se compare karo, jahan producer ka EX cycle 3 ke end mein khatam hota hai aur follower ka EX use cycle 4 ke start mein chahiye hai: wahan, EX/MEM → EX time mein forward move karta hai aur kaam karta hai. Loads special sirf isliye hain kyunki unka birth stage (MEM) ek stage baad mein baithta hai.

PICTURE. Red "impossible" arrow end-of-cycle-4 value se start-of-cycle-4 need ki taraf peeche (backward) point karne ki koshish kar raha hai. Arrow crossed out hai.

Step 5 — Ilaaj: exactly ek bubble insert karo

KYA HAI. Hum add (aur uske peeche sab kuch) ko ek cycle delay karte hain. Uska EX cycle 4 se cycle 5 par slide karta hai. Ab:

• Load ka $2 ready: cycle 4 ka end ($4^{+}$).
• add ko $2 chahiye: cycle 5 ka start ($5^{-}$). Kyunki $4^{+}<5^{-}$, ✅ inequality hold karti hai.

Value ab load ke MEM/WB register mein rehti hai aur Step 3b ki MEM/WB → EX wire cycle 5 mein ise deliver karti hai.

SIRF EK BUBBLE KYUN, AUR DELAY IMPLEMENT KAISE KARTE HAIN? Failure ek cycle ke andar ek instant ki thi, toh need ko agle cycle mein push karna ise exactly close karta hai. Hazard detection unit yeh delay teen simultaneous moves se karta hai (dekhein Pipeline control signals):

1. PC freeze karo — kuch naya fetch mat karo (wahi agla instruction dobara padha jaata hai).
2. IF/ID register freeze karo — add agle cycle mein pehli baar ke jaisa dobara decode hota hai.
3. ID/EX control signals zero karo — ID se abhi nikal rahi instruction NOP ban jaati hai: koi register write nahi, koi memory touch nahi, koi real op nahi. Woh zeroed slot pipe mein travel karta hua hi woh bubble hai jo humne abhi define kiya.

PICTURE. Step 2 ka staircase, ab add ki row mein ek grey NOP box wedged in, uska EX cycle 5 par push karte hue. Ek green forwarding arrow load ke MEM/WB se add ke EX mein jaata hai.

Step 6 — Forgiveness wala case: load → store ko bubble nahi chahiye

KYA HAI. Loaded value ka har use collide nahi karta. Ek store apna store-data register late, MEM mein consume karta hai, EX mein nahi:

lw  $2, 0($1)     # dest reg: MEM mein produce hota hai (cycle 4)
sw  $2, 4($1)     # wahi reg: MEM mein chahiye (cycle 5)

Cycles: lw MEM = 4. sw (ek cycle peeche) MEM = 5.

• Produce hua: cycle 4 ka end ($4^{+}$). Chahiye: cycle 5 ($5$, uska MEM). Kyunki $4^{+}<5$, inequality hold karti hai — Step 3b ki MEM/WB → MEM wire bina stall ke $2 cross karti hai.

YEH KYUN MATTERS. Yeh prove karta hai ki hazard is baare mein hai ki kaunse stage ko value chahiye, na ki "loads slow hain" ke baare mein. Consumer ke need-stage ko EX se MEM badlo aur poori problem gayab ho jaati hai.

PICTURE. Wahi staircase, lekin ab store ke liye need-flag MEM (cycle 5) par baithti hai, load ke produced-flag (cycle 4 ka end) ke safely baad. Green forwarding arrow, koi bubble nahi.

Step 6b — Scheduling escape: beech mein ek independent instruction slip karo

KYA HAI. Load aur use ke beech koi bhi instruction daalo jo $2 use na kare:

lw   $2, 20($1)   # dest reg: MEM mein produce hota hai (cycle 4)
and  $7, $8, $9   # independent filler, $2 ko touch nahi karta
add  $4, $2, $3   # $2 ki zaroorat EX mein hai

Cycles (har row upar wali se ek cycle baad IF shuru karta hai): lw IF=1, toh MEM=4. and IF=2. add IF=3, isliye uska EX = 3 + 2 = cycle 5.

• Produce hua: cycle 4 ka end ($4^{+}$). Chahiye: cycle 5 ka start ($5^{-}$). Kyunki $4^{+}<5^{-}$, inequality hold karti hai — MEM/WB → EX value deliver karta hai, koi bubble nahi.

YEH KYUN KAAM KARTA HAI. Filler instruction dependent add ko ek cycle baad push karti hai bina ek NOP par slot waste kiye — and ka real kaam us gap ko bharta hai jo warna ek bubble bharta. Yahi exactly woh hai jo Compiler instruction scheduling aur out-of-order hardware karta hai: real kaam ko delay slot mein reorder karo.

PICTURE. Teen-row staircase; independent and load aur use ke beech wali row mein baithta hai, aur add ka EX (cycle 5) load ke produced-flag (cycle 4 ka end) ke safely baad hai.

Step 7 — Nastier edge case: load ek branch ko feed kar raha hai (do bubbles)

KYA HAI. Ek branch (jaise beq) yeh decide karne ke liye do registers compare karta hai ki jump kahaan karein. Classic five-stage MIPS mein comparison early, ID mein resolve hoti hai, taaki branch penalty choti rahe (dekhein Branch hazards and prediction). Toh ek branch apne source registers ID ke start mein, EX mein nahi, chahiye hai. Ab unhe load se feed karo:

lw   $2, 0($1)    # dest reg: MEM mein produce hota hai (cycle 4)
beq  $2, $3, L    # $2 compare karta hai, ID mein chahiye (cycle 3 naive)

Cycles: lw MEM = 4. beq (ek cycle peeche) ID = 3.

• Produce hua: cycle 4 ka end ($4^{+}$). Chahiye: cycle 3 ka start ($3^{-}$). Kyunki $4^{+}>3^{-}$ inequality wide margin se fail hoti hai — need poore ek cycle plus ek instant pehle aati hai.

YEH EK NAHI DO BUBBLES KYUN. Hume branch ka ID cycle 3 se ek aisi cycle par slide karna hai jiska start $4^{+}$ ke baad ho. Cycle 4 ka start ($4^{-}$) abhi bhi $4^{+}$ se pehle hai, toh woh kaafi nahi — hume cycle 5 chahiye, jiska start $5^{-}>4^{+}$ hai. ID ko cycle 3 se cycle 5 par move karna two-cycle delay hai. Tabhi MEM/WB → ID wire (Step 3b mein add kiya gaya chautha path) $2 ko branch ke comparator mein time pe deliver karta hai. Loads jo early-compare branch ko feed karte hain woh worst load-use case hain.

HARDWARE DO BUBBLES KAISE INSERT KARTA HAI. Hazard detection unit Step-5 ki recipe ko ek ki jagah do consecutive cycles ke liye repeat karta hai (dekhein Pipeline control signals):

1. Cycle A: PC freeze, IF/ID freeze, ID/EX control signals zero → pehla bubble pipe mein enter karta hai, beq ID mein rehta hai.
2. Cycle B: hazard phir se detect hota hai (load sirf WB tak pahuncha hai, value abhi register file mein committed nahi), PC aur IF/ID dobara freeze, ID/EX phir zero → doosra bubble enter karta hai, beq abhi ID mein hold hai.
3. Cycle C (= cycle 5): load ki value ab MEM/WB latch mein baithti hai; MEM/WB → ID forward comparator ko feed karta hai, branch resolve hoti hai, aur normal fetching resume hoti hai.

PICTURE. Load row aur branch row; branch ka ID-need flag cycle 3 par baithta hai, load ke cycle-4 produced flag se kaafi pehle; do grey bubbles ID ko cycle 5 par push karte hain, aur ek green MEM/WB → ID arrow wahan value deliver karta hai.

Step 8 — Cost count karna: ek snippet se average CPI tak

KYA HAI. Single bubble ko performance number mein badlo. Teen-instruction snippet lw; add; sub lo.

• Ideal (koi hazard nahi): $n$ instructions ek 5-stage pipe mein $n+(5-1)=n+4$ cycles mein khatam hoti hain. Yahaan $n=3\Rightarrow 3+4=7$ cycles.
• Ek required bubble ke saath: $7+1=8$ cycles.

$n+4$ KYUN? Pehli instruction ko saare 5 stages chahiye ($5$ cycles), aur baad ki har instruction sirf $1$ cycle aur add karti hai (Step 2 ka diagonal). Toh $5+(n-1)=n+4$.

Ab ek program par average. CPI = cycles per instruction define karo. Har unavoidable bubble ek stall cycle add karta hai, weighted by kitni baar hota hai:

$\text{CPI}=\underset{\begin{array}{c}\text{ideal:}\\ \text{1 instr/cycle}\end{array}}{\underbrace{1.0}}+\underset{\begin{array}{c}\text{fraction of instrs}\\ \text{that hit a load-use stall}\end{array}}{\underbrace{f_{\text{stall}}}}\times \underset{\begin{array}{c}\text{cycles lost}\\ \text{per stall}\end{array}}{\underbrace{1}}$

Loads = $20\%$ instructions aur unme se aadhe immediately use hote hain: $f_{\text{stall}}=0.20\times 0.50=0.10\Rightarrow \text{CPI}=1.0+0.10=\mathrm{1.10.}$

PICTURE. Ek bar chart: snippet ke liye ideal 7 cycles vs stalled 8 cycles, aur CPI 1.00 vs 1.10 ke liye doosra bar pair — top par red sliver woh tax hai jo load-use hazard lagata hai.

Ek-picture summary

Final figure poori kahani stack karta hai: load ki row apni value MEM ke end mein paida hote hue (cycle 4, green flag); cycle-4 EX par naive add collide kar raha hai (red, impossible backward arrow); bubble wedge in kiya gaya; aur fixed add cycle-5 EX par value ek legal forward-in-time green wire se receive karta hua. Ek cycle lost — yahi load-use hazard ki keemat hai.

Yeh bhi dekhein: Hazard detection unit · Data hazards and forwarding · Pipeline control signals · Compiler instruction scheduling · Branch hazards and prediction · Memory hierarchy and cache