Load-use hazard and stalls: Exercises — Hinglish deep dive

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

Yeh page ek self-testing ladder hai. Har problem apna level batata hai taaki pata chale kitna stretch kar rahe ho. Har solution ek collapsible [!recall]- box ke andar hai — problem padho, socho, phir unfold karo. Har level ke baad ek [!mistake] box hai jo us level ka sabse common trap steel-man karta hai.

Parent: Load-use hazard and stalls. Prerequisites jo open rakhne chahte ho: Five-stage MIPS pipeline, Data hazards and forwarding, Hazard detection unit.

Upar figure dekho: red dot (data ready) cycle 4 ke far edge par hai, jabki coral arrow (data needed) cycle 4 ke near edge par point kar raha hai. Arrow ko time mein left travel karna padta — impossible. Wahi gap is poore subject ka core hai.

Toh "MEM/WB → EX" = load ka result MEM/WB latch se nikalo aur ALU input par daal do. "MEM/WB → MEM" = wahi latched value store ke data port mein MEM stage ke dauran feed karo. Same idea, alag destination. Data hazards and forwarding dekho.

Level 1 — Recognition

Goal: kya tum ek hazard ek nazar mein pakad sakte ho?

Worked example Exercise 1.1

Har pair ke liye, bolo YES (load-use stall chahiye) ya NO.

(a) lw  $2, 0($1)
    add $4, $2, $3
 
(b) lw  $2, 0($1)
    add $4, $5, $3
 
(c) add $2, $1, $3
    add $4, $2, $3
 
(d) lw  $0, 0($1)
    add $4, $0, $3

Recall Solution 1.1

Teen stall conditions apply karo: (1) pehli instruction load hai, (2) uska destination register agli instruction read karti hai, (3) woh register $0 nahi hai.

(a) YES. lw $2 likhta hai; add $2 read karta hai. Teeno conditions hold karti hain.
(b) NO. add $5 aur $3 read karta hai, kabhi $2 nahi. Condition 2 fail.
(c) NO. Pehli instruction add hai, load nahi — ek ALU→ALU dependency jo forwarding se akele solve hoti hai. Condition 1 fail.
(d) NO. Load $0 ko target karta hai, jo MIPS mein hardwired zero hai; $0 read karne wala add zero hi dekhta hai. Condition 3 fail.

Recall Solution 1.2

Freeze hote hain: PC aur IF/ID register. Yeh same instruction ko re-fetch karta hai aur dependent instruction ko ID mein ek extra cycle ke liye hold karta hai.
Zero hote hain: ID/EX control signals, EX stage ko NOP bana dete hain (no write, no memory op) inject kiye gaye bubble ke liye.
Untouched: MEM aur WB normally continue karte hain, toh load schedule ke anusaar finish hota hai. Pipeline control signals dekho.

Level 2 — Application

Goal: sahi pipeline diagram banao aur cycles count karo.

Recall Solution 2.1

Cycle:  1    2    3    4    5    6    7
lw      IF   ID   EX   MEM  WB
add          IF   ID   **   EX   MEM  WB

** bubble hai. add ka EX cycle 5 mein shift ho jaata hai. Load ka data (cycle 4 ke end mein ready, MEM/WB mein baith kar) MEM/WB → EX forward hota hai us cycle-5 EX mein. add row padhte hain: EX = cycle 5, MEM = cycle 6, WB = cycle 7. Toh add WB mein cycle 7 mein pahunchta hai (cycle header ab 7 tak jaata hai yeh dikhane ke liye).

Recall Solution 2.2

Koi stall nahi. Ek store apna store-data register late consume karta hai, apne MEM stage mein.

Cycle:  1    2    3    4    5
lw      IF   ID   EX   MEM  WB
sw           IF   ID   EX   MEM

lw cycle 4 ke end mein MEM finish karta hai. sw apne MEM stage mein memory write karta hai, cycle 5 mein — data exist hone ke baad. Ek MEM/WB → MEM forward $2 time par deliver karta hai. Koi bubble nahi.

Recall Solution 2.3

Koi stall nahi. Independent or load aur use ke beech hai.

Cycle:  1    2    3    4    5    6    7
lw      IF   ID   EX   MEM  WB
or           IF   ID   EX   MEM  WB
add               IF   ID   EX   MEM  WB

add ka EX ab cycle 5 mein hai, aur lw ka data (cycle 4 ke end mein ready) cleanly MEM/WB → EX forward hota hai. Yahi exactly Compiler instruction scheduling exploit karta hai.

Level 3 — Analysis

Goal: performance numbers ke baare mein reason karo.

Recall Solution 3.1

Stall frequency $= 0.25 \times 0.40 = 0.10$ saari instructions ka. $CPI = 1.0 + 0.10 \times 1 = 1.10$ Slowdown $= (1.10 - 1.0) /1.0 = 0.10 = 10%$ ideal se zyada cycles.

Recall Solution 3.2

Pehle, ideal (no-stall) cost. Pipeline "1 cycle each" se zyada kyun cost karta hai? Pehli instruction ko finish hone ke liye saare $5$ stages se guzarna padta hai — pipeline fill hone mein $5$ cycles lagte hain. Uske baad, har additional instruction sirf $1$ cycle baad finish hoti hai, kyunki woh overlap karti hain aur back-to-back aati hain. Toh $n$ instructions ke liye $d$ -stage pipeline mein: $ideal cycles = d + (n - 1)$ Yahan $d = 5$ , $n = 3$ : $5 + (3 - 1) = 5 + 2 = 7$ cycles. (Rows check karo: lw WB cycle 5 par hai, phir har instruction ke liye +1.)

Cycle:  1    2    3    4    5    6    7    8
lw      IF   ID   EX   MEM  WB
add          IF   ID   **   EX   MEM  WB
sub               IF   ID   **   EX   MEM  WB

Ek bubble sab kuch ek cycle push karta hai → sub cycle 8 mein finish hota hai. Ratio $= 8/7 \approx 1.14$ . Note karo sub ko koi extra stall nahi chahiye: jab woh EX tak pahunchta hai, add ka result normally EX/MEM → EX forward hota hai.

Recall Solution 3.3

Stalls per iteration $= 2$ . Instructions per iteration $= 6$ . $CPI = 1.0 + \frac{2 stalls}{6 instructions} = 1.0 + 0.3333 \dots = 1.333$ Yeh ek bada hint hai ki yeh loop Compiler instruction scheduling reordering ka prime candidate hai.

Level 4 — Synthesis

Goal: code aur hardware conditions khud se rebuild karo.

Recall Solution 4.1

Load ke delay slot mein (bilkul lw ke baad) ek independent instruction move karo. or sirf $7,$8 use karta hai — $2 se independent. Toh:

lw   $2, 0($1)
or   $6, $7, $8      ; independent — slot fill karta hai
add  $4, $2, $5      ; ab $2 MEM/WB to EX forwarded dekhta hai, koi stall nahi
and  $9, $10, $11

Results unchanged (koi instruction ne koi register aise nahi likha jise koi aur ab out of order read kare), aur stall chali gayi. Yahi exactly Compiler instruction scheduling technique hai.

Recall Solution 4.2

Pehle symbol key: $\land$ matlab AND (dono true), $\lor$ matlab OR (kam se kam ek true), $\neq =$ matlab not equal. $stall = ID/EX.MemRead \land (ID/EX.Rt = IF/ID.Rs \lor ID/EX.Rt = IF/ID.Rt) \land (ID/EX.Rt \neq = 0)$

ID/EX.MemRead $= 1$ : ek load abhi EX mein hai (sirf loads memory ko register mein read karte hain).
ID/EX.Rt: us load ka destination register (for lw, target Rt field hai).
IF/ID.Rs / IF/ID.Rt: ab ID mein instruction ke do source registers (potential dependent).
$\neq = 0$ : hardwired $0 ko exclude karo, jo kabhi real dependency nahi carry karta.

Recall Solution 4.3

Forwarding ke bina, add ko $2 apne ID stage mein register file se read karna hoga, aur register file lw ke WB (cycle 5) mein likhi jaati hai. Same-cycle-write-then-read register file ke saath, add ka ID cycle 5 mein land karna chahiye.

Cycle:  1    2    3    4    5    6
lw      IF   ID   EX   MEM  WB
add          IF   **   **   ID   EX  ...

Yeh 2 bubbles hain. Forwarding (MEM/WB → EX) hi ise single unavoidable bubble tak shrink karta hai.

Level 5 — Mastery

Goal: sab kuch combine karo, cache latency aur back-to-back loads milake.

Recall Solution 5.1

Do alag load-use hazards chain hote hain.

lw $3 $2 use karta hai apne EX (address computation) mein → pehle load ke baad 1 stall.
add $3 use karta hai apne EX mein → doosre load ke baad 1 stall.

Cycle:  1    2    3    4    5    6    7    8    9
lw $2   IF   ID   EX   MEM  WB
lw $3        IF   ID   **   EX   MEM  WB
add               IF   ID   **   **   EX   MEM  WB

Row-by-row, header se match karte hue:

lw $2: IF1 ID2 EX3 MEM4 WB5.
lw $3: IF2 ID3, ek bubble ** cycle 4 mein, phir EX5 MEM6 WB7.
add: IF3 ID4, phir do bubbles ** cycles 5 aur 6 mein (lw $3 ke data ka wait), phir EX7 MEM8 WB9. add cycle 9 mein write back karta hai. 2 stall cycles total (har load-use hazard ke liye ek).

Recall Solution 5.2

Penalty ko do independent contributions mein todo (saari instructions per):

Load-use stalls: $0.30 \times 0.50 \times 1 = 0.15$ .
Cache-miss penalty: $0.30 \times 0.05 \times 10 = 0.15$ . $CPI = 1.0 + 0.15 + 0.15 = 1.30$ Miss penalty Memory hierarchy and cache se aati hai aur pipeline stall se ek alag effect hai — yeh simply add hote hain.

Recall Solution 5.3

$CPI_{A} = 1.0 + 0.20 \times 1 = 1.20$ .
$CPI_{B} = 1.0 + 0.20 \times 2 = 1.40$ .
Ratio $= 1.40/1.20 = 1.1 \overline{6} \approx 1.17$ . Machine A faster hai: is program par Machine B se lagbhag 17% kam cycles leta hai. Forwarding exactly ek bubble per load-use hazard wapas earn karta hai, aur woh ek saved bubble hi dono machines ke beech ka poora gap hai.

Recall Rapid self-check (cloze)

Ek load data produce karta hai ::: MEM stage ke end mein. Ek dependent ALU instruction use chahiye ::: apne EX stage ke start mein. Load-use hazard ke liye minimum unavoidable bubbles forwarding ke saath hain ::: ek. Forwarding ke bina, load-use gap badh jaata hai ::: do bubbles tak. Zero register par false hazards exclude karne wali condition: ::: ID/EX.Rt ≠ 0.