5.2.7 · D3Load-use hazard aur stalls
Tumne load-use hazard ko Load-use hazard and stalls mein pehle hi dekha hai. Us parent note ne tumhe ek clean case dikhaya tha: lw phir add, ek stall, khatam. Lekin real world mein zyada messy shapes aate hain — stores, zero registers, dependents ki chains, load ke baad branches. Ye page har distinct case class ko ek-ek karke walk through karta hai, taaki tum koi aisa scenario kabhi na dekho jise tum pehle solve hote nahi dekh chuke.
Kisi bhi example se pehle, chalte hain panch cheezein naam karte hain jo pipeline ke har stage ko define karti hain, taaki koi symbol tumhe surprise na kare. Phir hum stall , bubble , aur exact three-condition test define karenge — jo kuch bhi chahiye sab is page par hai.
Definition The five stages (hamaara poora alphabet)Ek MIPS instruction (dekho Five-stage MIPS pipeline ) panch stages se guzarta hai, har clock cycle mein ek:
IF — Instruction Fetch : instruction ko memory se pakdo.ID — Instruction Decode : jo register values chahiye unhe padho.EX — Execute : ALU (calculator) mein arithmetic karo.MEM — Memory : data memory se padho ya usme likho.WB — Write Back : result ko register mein store karo.
Ek data hazard ka matlab hai ki ek instruction ko aisi value chahiye jo ek earlier, abhi-bhi-pipeline-mein-chalti instruction ne abhi produce khatam nahi ki hai.
N N + 4 5 Pehla instruction sab 5 5 har cycle mein finish hota hai, kyunki stages overlap karte hain. Toh:
total cycles = first finishes 5 + one per cycle after ( N − 1 ) = N + 4. "+ 4 pipeline fill cost hai (wo 4 N = 2 ⇒ 6 N = 3 ⇒ 7
Definition Stall aur bubble (neeche har jagah use hote hain)Ek stall ek decision hai ki ek instruction ko ek cycle ke liye rokke raho instead of use next stage mein aage badhne do. Jo empty slot yeh pipeline mein ruke hue instruction ke peechhe chodta hai use bubble kehte hain — socho ek fake "do-nothing" instruction (ek NOP) pipe mein neeche slide kar raha hai. "1 bubble insert karo" aur "1 cycle stall karo" ek hi cheez hain: dependent instruction ID mein ek cycle wait karta hai, aur ek hole EX/MEM/WB se guzarta hai bina kuch kaam kiye.
Definition Teen-condition stall test (self-contained)Hazard detection unit ID/EX pipeline register mein carry ki gayi fields ko compare karta hai — yeh latches ka ek set hai jo us instruction ki info hold karta hai jo abhi EX mein hai. Do fields matter karti hain:
ID/EX.MemRead — ek 1-bit flag jo 1 ID/EX.RegisterRt — destination register number jisme load write karega.
Yeh incoming instruction ke source-register numbers bhi padhta hai, IF/ID.RegisterRs aur IF/ID.RegisterRt . Stall tab insert hota hai jab teeno conditions sach hon:
(1) ID/EX.MemRead = 1 (2) ID/EX.RegisterRt = IF/ID.RegisterRs OR ID/EX.RegisterRt = IF/ID.RegisterRt (3) ID/EX.RegisterRt = 0 ( a load is in EX ) ( the loaded reg is used next ) ( not the $0 register )
Definition Forwarding paths jinpar hum rely karte hainForwarding (Data hazards and forwarding se) ek wire hai jo freshly-computed value ko seedha wahan bhejti hai jahan zaroori hai , slow write-to-register-then-read-back route ko skip karke. Teen paths is page par aate hain — definition ke neeche figure dekho:
MEM/WB → EX : aisi value bhejta hai jo abhi MEM se nikli hai, baad wale instruction ke EX stage ke ALU inputs mein.MEM/WB → MEM : value ko baad wale store ke MEM stage mein bhejta hai (taaki store freshly-loaded data likh sake).MEM/WB → ID : value ko baad wale instruction ke ID stage mein bhejta hai — yeh sirf un designs mein hota hai jo branches ko early resolve karte hain (wo registers ko ID mein compare karte hain). Hume Example 6 mein chahiye.
Forwarding figure ko is tarah padho: har stage box ek baar draw hai, aur curved arrows dikhate hain kahan ek value MEM/WB latch par janmi (right mein red source) ko teleport kiya ja sakta hai. Red-highlighted WB box woh jagah hai jahan value physically rehti hai; curved arrows us se peelkar EX , MEM , ya ID par land karte hain baad wale instruction ke. Koi arrow waqt mein peeche point nahi karta — har arrow ek aisi stage par land karta hai jo baad wale cycle mein ho rahi hai, yehi poora point hai.
Intuition Ek fact jo is page par sab kuch drive karta haiEk lw (load word) apni value END of MEM par produce karta hai — yahi woh moment hai jab number memory se aata hai. Neeche har sawal actually yeh hai: "Kya woh instruction jo yeh value chahta hai, use MEM cycle ke khatam hone SE PEHLE chahiye, ya BAAD MEIN?" Agar pehle → stall. Agar baad mein → sirf forwarding kaam aa jaata hai.
Timeline figure ko is tarah padho neeche: panch boxes ek single lw ke panch stages hain, cycles 1–5 mein left-to-right rakhe hue. Chaar boxes black hain; sirf MEM box red hai , kyunki MEM wahan hota hai jahan memory read hoti hai. Red arrow us MEM box ke right edge ko point karta hai — woh instant (cycle 4 ka end) jab loaded number pehli baar exist karta hai. Kuch bhi is value ko us edge se pehle read nahi kar sakta. Is "ready at end of MEM" landmark ko yaad kar lo; har example apna need-cycle iske against measure karta hai.
Yeh har case class hai jo yeh topic produce kar sakta hai. Baad ke har example ko us cell se tag kiya gaya hai jise woh fill karta hai.
#
Case class
Kya ise alag banata hai
Stall?
A
Load → ALU use (immediate)
consumer ko data EX mein chahiye, load ke ek cycle baad
1 stall
B
Load → independent instr → use
ek gap delay absorb karta hai
0 stalls
C
Load → store us value ka
consumer ko data MEM mein chahiye, EX se baad
0 stalls
D
Load into $zero
condition-3 guard: $0 kabhi nahi badlata
0 stalls
E
Load → use as base address of another load
lw→lw address register ke through chain1 stall
F
Load → branch using loaded value
branch early resolve hota hai → data aur bhi jaldi chahiye
2 stalls
G
Ek load ke baad do dependents ek saath
sirf pehla dependent stall trigger karta hai
1 stall
H
Word problem: CPI of a real loop
bohot saare instructions par limiting/aggregate behaviour
—
I
Exam twist: 4 pairs mein se kaunsa stall karta hai
3-condition test coldly apply karo
mixed
Hum A–I sab neeche cover karenge.
Worked example Example 1 — Cell A: Load → ALU use (canonical stall)lw $2, 20 ($1) add $4, $2, $3 Forecast: abhi guess karo — kitne stall cycles, aur kis cycle mein add finally EX execute karta hai?
Step 1. Dono timelines ko cycle ke hisaab se align karke likho.
Yeh step kyun? "Bahut jaldi / bahut deri" ke baare mein reason karna impossible hai bina dono EX/MEM cycles ko side by side dekhe.
Cycle: 1 2 3 4 5
lw IF ID EX MEM WB <- $2 ready END of cycle 4
add IF ID EX ... <- wants $2 START of cycle 4
Step 2. Need cycle ko ready cycle se compare karo: add ko $2 cycle 4 ke start mein chahiye; yeh cycle 4 ke end mein ready hai. Need earlier hai → hazard .
Yeh step kyun? Yahi poora test hai — do integers ki comparison (need-cycle vs ready-cycle).
Step 3. 1 bubble insert karo: add ko ID mein ek extra cycle rokke rakho (ek NOP uske peechhe EX se slide karta hai).
Yeh step kyun? Ek cycle ki delay add ke EX ko cycle 4 se cycle 5 par push kar deti hai, jo data ready hone ke baad hai — yeh sabse pehla EX hai jahan ALU legally start kar sakta hai.
Cycle: 1 2 3 4 5 6
add IF ID (stall) EX MEM <- forward MEM/WB -> EX at cycle 5
Step 4. Dono instructions ke liye total cycles gino: aakhri stage (add ka WB) cycle 7 mein land karta hai, toh total 7 cycles.
Yeh step kyun? Total run time bas "cycle number jab aakhri WB finish ho" hai; ise count karna hazard ki cost batata hai.
Verify: 2 instructions ideally 2 + 4 = 6 7 = 7 − 6 = 1
Worked example Example 2 — Cell B: ek independent instruction delay ko hide kar deta hailw $2, 20 ($1) and $7, $8, $9 add $4, $2, $3 (and $2 se independent hai; add $2 use karta hai.)
Forecast: stall ya no stall?
Step 1. Inhe line up karo.
Yeh step kyun? and load aur use ke beech mein hai — count se zyada position matter karti hai.
Cycle: 1 2 3 4 5 6
lw IF ID EX MEM WB
and IF ID EX MEM WB
add IF ID EX MEM <- $2 needed at start of cycle 5
Step 2. add ka EX ab cycle 5 mein hai. $2 cycle 4 ke end mein ready hai. Ready ≤ need → no hazard .
Yeh step kyun? Independent and ne cycle-4 ka EX slot use kar liya, add ko ek cycle baad free mein slide kar diya.
Step 3. Cycle 5 mein MEM/WB → EX se forward karo (hamaari forwarding definition se upar wala MEM/WB → EX wire).
Yeh step kyun? Stall ke bina bhi, value ko abhi bhi ek spatial shortcut chahiye jahan se woh nikli (MEM/WB) se jahan padhi jaayegi (EX); forwarding yeh provide karta hai taaki slow write-then-read skip ho.
Verify: 3 instructions, ideal 3 + 4 = 7 7 Compiler instruction scheduling automatically arrange karne ki koshish karta hai.
Worked example Example 3 — Cell C: load phir loaded value store karolw $2, 0 ($1) sw $2, 4 ($1) (sw $2 store karta hai — ise $2 apne MEM stage mein chahiye, EX mein nahi.)
Forecast: dono instructions adjacent hain aur $2 par dependent hain. Stall ya nahi?
Step 1. Yaad karo kab ek store apna data register read karta hai : ek sw apni store-data value MEM stage mein use karta hai (yahi cycle hai jab woh memory mein likhta hai), EX mein nahi.
Yeh step kyun? Poora jawab is baat par depend karta hai ki kaunsi stage $2 consume karti hai.
Cycle: 1 2 3 4 5
lw IF ID EX MEM WB <- $2 ready END cycle 4
sw IF ID EX MEM <- $2 consumed in MEM = cycle 5
Step 2. Need cycle = 5 (store ka MEM). Ready cycle = 4 (load ka MEM). Ready < need → no hazard .
Yeh step kyun? Stores forgiving hote hain: unhe value late chahiye hoti hai.
Step 3. Ek MEM/WB → MEM forwarding path (hamaari forwarding definition se) $2 ko cycle 5 mein deliver karta hai. Koi bubble nahi.
Yeh step kyun? Value MEM/WB se cycle 4 ke end mein nikli aur store ke MEM mein cycle 5 mein pahunchni chahiye — ek purely spatial hop jo yeh doosra forwarding wire exactly is kaam ke liye exist karta hai.
Verify: 2 instructions, ideal 2 + 4 = 6 6 = 0
Worked example Example 4 — Cell D:$zero mein load karna (degenerate)
lw $0, 8 ($1) add $4, $0, $3 (Load ka target $0 hai, hardwired zero register.)
Forecast: "agla instruction loaded register use karta hai" — Example 1 jaisa lagta hai. Kya stall aayega?
Step 1. MIPS rule yaad karo: register $0 hardwired to 0 hai; isme write karna discard ho jaata hai.
Yeh step kyun? Agar destination $0 hai, toh koi real value produce nahi hoti, toh wait karne ke liye kuch nahi hai.
Step 2. Hamare teen-condition test ki condition (3) apply karo: stall tabhi hoga jab ID/EX.RegisterRt ≠ 0. Yahan load ka destination field ID/EX.RegisterRt number 0 $0) hold karta hai, toh condition (3) false hai.
Yeh step kyun? ID/EX.RegisterRt exactly woh latch hai jise detector inspect karta hai; jab yeh 0 ke equal hota hai toh detector design kiya gaya hai ki fire na kare , ek useless bubble se bachne ke liye.
Step 3. add $0 = 0 padhta hai (hamesha available), koi dependency exist nahi karti → no stall .
Verify: 2 instructions, ideal 6 6 = 0
Worked example Example 5 — Cell E: load doosre load kaaddress feed karta hai
lw $2, 0 ($1) lw $5, 0 ($2) (Doosra lw $2 ko apne base address ke roop mein use karta hai.)
Forecast: doosra lw $2 ko apna memory address build karne ke liye use karta hai. Kaunsi stage $2 use karti hai, aur kya stall aata hai?
Step 1. Address kahan compute hota hai? EX mein (ALU base + offset add karta hai).
Yeh step kyun? Bhaale yeh ek load hai, register $2 EX mein consume hota hai, bilkul ek ALU input ki tarah — toh test ki condition (2) IF/ID.RegisterRs par match karti hai.
Cycle: 1 2 3 4 5 6
lw $2 IF ID EX MEM WB <- $2 ready END cycle 4
lw $5 IF ID EX MEM <- $2 needed START cycle 4 (to add offset)
Step 2. Need = cycle 4 ka start, ready = cycle 4 ka end → hazard , Example 1 jaisi shape.
Yeh step kyun? Loads aur ALU ops dono apna address/operand register EX mein read karte hain, toh timing mismatch identical hai.
Step 3. 1 stall insert karo; doosre load ka EX cycle 5 mein slide ho jaata hai; MEM/WB → EX forward karo.
Yeh step kyun? Bubble address computation ko tab tak delay karta hai jab tak $2 ready na ho jaaye, aur MEM/WB → EX wire cycle 5 mein $2 ko address adder ko deta hai.
Verify: 2 instructions, ideal 6 = 7 = 1
Worked example Example 6 — Cell F: load ek branch condition feed karta hailw $2, 0 ($1) beq $2, $3, LABEL (Maano branch ID stage mein resolve hota hai — ek common optimization; dekho Branch hazards and prediction .)
Forecast: beq ko $2 kab chahiye, aur kitne stalls?
Step 1. Early-resolve design mein, branch apne registers ID mein compare karta hai, EX mein nahi.
Yeh step kyun? Comparison ko pehle karna branches ko fast banata hai lekin unhe apne operands aur jaldi chahiye hote hain.
Cycle: 1 2 3 4 5
lw $2 IF ID EX MEM WB <- $2 ready END cycle 4
beq IF ID ... <- $2 needed in ID = cycle 3
Step 2. Need = cycle 3, ready = cycle 4. Branch ka consuming ID $2 ke ready hone (cycle 4 ka end) ke baad land karne ke liye, uska ID cycle 5 par push hona chahiye.
Yeh step kyun? Consumer data jitni jaldi chahiye, utne zyada bubbles gap close karne ke liye chahiye.
Step 3. 2 stalls insert karo taaki beq ka ID cycle 5 mein land kare, $2 ready hone ke baad.
Yeh step kyun? ID ko cycle 3 se cycle 5 par move karna do cycles ka shift hai, toh do bubbles chahiye.
Cycle: 1 2 3 4 5
beq IF (stall)(stall) ID <- $2 forwarded in via MEM/WB -> ID
Step 4. $2 ko cycle 5 mein MEM/WB → ID forwarding path se deliver karo (teesra path jo humne upar define kiya, jo sirf early-resolve designs mein exist karta hai).
Yeh step kyun? $2 MEM/WB latch se cycle 4 ke end mein nikla; branch ka comparator ID mein rehta hai; MEM/WB → ID wire exactly woh bypass hai jo value ko us latch se ID comparator mein cycle 5 mein le jaata hai.
Verify: need-cycle 3, ready-cycle 4; ID ko cycle 5 tak push karne ke liye stalls chahiye = 5 − 3 = 2 worst load-use case hain.
Worked example Example 7 — Cell G: ek saath do dependentslw $2, 0 ($1) add $4, $2, $5 sub $6, $2, $7 (Dono add aur sub $2 use karte hain.)
Forecast: do instructions $2 use karte hain. Kitne stalls total — ek, ya do?
Step 1. Sirf woh instruction jo ID mein hai jabki load EX mein hai detector ko trigger karta hai.
Yeh step kyun? Hazard detection unit ki condition (1) EX-stage load check karti hai; yeh ek baar fire karta hai, immediately-following dependent par.
Cycle: 1 2 3 4 5 6 7
lw IF ID EX MEM WB
add IF ID (stall)EX MEM WB <- stalled once, EX cycle 5
sub IF (stall)ID EX MEM <- rides the same bubble
Step 2. Single stall ke baad, add cycle 5 mein EX execute karta hai aur MEM/WB → EX ke zariye $2 forward karta hai. Kyunki bubble ne uske peechhe sab kuch ek cycle baad slide kar diya, sub ka EX ab cycle 6 mein land karta hai.
Yeh step kyun? Ek bubble ek wall hai: baad ka har instruction ek cycle peeche slide ho jaata hai, toh hume sub ko uski nayi position par re-check karna chahiye.
Step 3. sub ko re-test karo: uska EX (cycle 6) $2 ready hone (cycle 4 ka end) ke kafi baad hai, toh uska need-cycle ready-cycle se zyada hai → sub ke liye koi extra stall nahi .
Yeh step kyun? "Need vs ready" rule har consumer par apply hota hai; sub pehle bubble ke pushback se free mein pass kar jaata hai.
Verify: 3 instructions, ideal 3 + 4 = 7 = 8 = 1 = 1
Worked example Example 8 — Cell H: ek real loop ka CPI (aggregate/limiting behaviour)Ek program 1000 30% 40% CPI = 1.0 C ycles P er I nstruction.)
Forecast: compute karne se pehle CPI ko do decimals mein guess karo.
Step 1. Fraction of instructions jo stall cause karte hain = 0.30 × 0.40 = 0.12 Yeh step kyun? Sirf loads-with-immediate-use stall karte hain; do probabilities multiply karo.
Step 2. Har aisa instruction exactly 1 CPI = 1.0 + 0.12 × 1 = 1.12. Yeh step kyun? Yeh parent note ka formula hai CPI = 1.0 + ( stall freq ) × 1
Step 3. Percent slowdown = ( 1.12 − 1.0 ) /1.0 = 0.12 = 12% Yeh step kyun? Slowdown cycles per instruction mein fractional increase hai.
Verify: run mein stall cycles = 1000 × 0.12 = 120 = 1000 × 1.12 = 1120 1120/1000 = 1.12 Memory hierarchy and cache ) misses reduce karta hai, lekin is structural hazard ko nahi.
Worked example Example 9 — Cell I: exam twist — kaunse pairs stall karte hain?Har pair ke liye, sirf teen-condition test use karke stall / no stall batao (dekho Pipeline control signals ).
(a) lw $8, 0 ($9) ( b ) lw $8, 0 ($9) (c) lw $0, 0 ($9) (d) add $8, $9, $10 sub $4, $8, $5 sw $8, 0 ($9) add $4, $0, $5 sub $4, $8, $5 Forecast: guess karo charron mein se kitne stall karte hain.
Step 1 (a). Condition (1) load in EX ✓, condition (2) $8 sub ke EX mein use hota hai ✓, condition (3) $8 ≠ $0 ✓. Teeno sach → stall .
Step 2 (b). Condition (1) ✓, lekin consumer ek store hai jo $8 MEM mein chahiye (Cell C), toh EX-stage read nahi → no stall .
Step 3 (c). Destination $0 hai, toh condition (3) fail → no stall .
Step 4 (d). Pehli instr add hai, load nahi → condition (1) (MemRead) fail. Yeh ek ALU-ALU hazard hai jo forwarding se fix hota hai → no stall .
Yeh steps kyun? Har pair teen conditions mein se ek alag condition break karta hai — yehi twist ka point hai.
Verify: stalling pairs = { a } = 1 4
Recall Quick self-testEk load apni value kis stage ke end mein produce karta hai? ::: MEM
Ek store apna data register kis stage mein consume karta hai? ::: MEM
Bubble kya hota hai? ::: ek NOP (do-nothing) slot jo stall se insert hota hai, pipe mein neeche slide karta hai
$0 mein load karna kabhi stall kyun nahi karta? ::: $0 hardwired to 0 hai, toh koi real value produce nahi hoti (condition 3 fail ho jaati hai)
Load jo early-resolved branch feed karta hai, kitne stalls chahiye? ::: 2
Load ke baad do dependents ek saath kitne total stalls cause karte hain? ::: 1
"N + 4 + 4
Mnemonic Har case ke liye ek-line test"Kab chahiye vs kab ready hai?" Load ready hai end of MEM par. Consumer ke need-stage se compare karo: EX → 1 stall, MEM → 0 stalls, ID (early branch) → 2 stalls, $0 target → 0.
