Hazard detection units: Exercises — Hinglish deep dive

5.2.10 · D4 · Hardware › Processor Datapath & Pipelining › Hazard detection units

Shuru karne se pehle, reference diagram dhyan se dekho — baad ke har solution mein isi ki taraf point kiya gaya hai, isliye ise samne rakho.

Hazard detection unit (HDU) ID mein rehta hai — figure mein yeh woh box hai jo "HDU (ID)" label kiya gaya hai, cyan color mein dashed border ke saath. Yeh us instruction ke register numbers padhta hai jo decode ho rahi hai aur unhe EX mein present instruction se compare karta hai.
Forwarding unit EX ke paas rehta hai — woh box jo "FWD (EX)" label kiya gaya hai, amber color mein solid double border ke saath. Yeh already-computed results ko seedha ALU inputs mein steer karta hai, register file ko bypass karke. Do amber arrows text-labelled hain "EX/MEM → ALU" aur "MEM/WB → ALU" — yeh forwarding paths hain jo baad ke har "forwarding handles it" claim ko carry karte hain.
Stall woh arrow hai jis par text label hai "STALL: PCWrite=0, IF/ID_Write=0" (white, dotted draw kiya gaya) jo HDU se PC aur IF/ID register ki taraf jaata hai.

Level 1 — Recognition

Exercise 1.1

Har situation ko data, control, ya structural hazard mein classify karo.

(a) beq $1,$2,L ke baad agla sequential instruction branch resolve hone se pehle fetch ho jaata hai.
(b) add $1,$2,$3 ke turant baad sub $4,$1,$5.
(c) Ek single-port memory jo ek hi cycle mein instruction fetch (IF) aur lw memory access (MEM) dono serve karne ki koshish kare.

Recall Solution 1.1

(a) Control hazard — pipeline ne ek instruction fetch kar li thi branch taken hai ya nahi yeh jaanne se pehle.
(b) Data hazard (RAW: sub $1 read karta hai, jo add write karta hai). Reference figure mein, yahi woh cheez hai jo "EX/MEM → ALU" label wala arrow bina kisi stall ke resolve karta hai.
(c) Structural hazard — do instructions ek hi cycle mein ek hardware resource (memory port) ke liye compete kar rahe hain.

Exercise 1.2

HDU ko combinational logic describe kiya gaya hai. Yeh property kya guarantee karta hai?

Yeh cycles ke across state store karta hai.
Iske outputs usi clock cycle ke andar settle ho jaate hain, next clock edge se pehle.
Yeh apne private clock par chalta hai.

Recall Solution 1.2

Jawab: 2. Combinational logic ki koi memory nahi hoti; inputs diye jaane par (wo register fields jo pipeline registers mein already latched hain) yeh stall/flush outputs cycle ke andar produce karta hai, toh correct control decision next clock edge se pehle ready hota hai jo koi bhi value commit kare.

Level 2 — Application

Exercise 2.1

Load-use detection formula apply karo. Diya gaya hai:

ID/EX.MemRead = 1
ID/EX.RegisterRd = 2
IF/ID.RegisterRs = 5
IF/ID.RegisterRt = 2

Kya HDU stall assert karta hai? Dikhao kaun sa clause fire hota hai.

Recall Solution 2.1

Detection condition hai $MemRead \land ((RegisterRd = RegisterRs) \lor (RegisterRd = RegisterRt)) .$ Substitute karke: $MemRead = 1$ (true). Phir $RegisterRd = 2$ , $RegisterRs = 5$ → $2 = 5$ false; $RegisterRd = 2$ , $RegisterRt = 2$ → $2 = 2$ true. OR true hai, AND true hai. Result: STALL assert hua. RegisterRt clause fire hua. Reference figure mein yeh cyan arrow (ID/EX → HDU) hai jo MemRead read karta hai aur white "STALL" arrow trigger karta hai.

Exercise 2.2

Usi instruction ke liye HDU ek stall assert karta hai. Woh teen exact values list karo jo yeh teen control signals par drive karta hai, aur ek line mein batao ki har ek kya freeze karta hai.

Recall Solution 2.2

PCWrite = 0 — PC ko freeze karta hai, toh koi naya instruction fetch nahi hota.
IF/ID_Write = 0 — IF/ID register ko freeze karta hai, toh dependent instruction ID mein rukti hai retry ke liye.
Control_Mux = 0 — jaisa upar define kiya, ID/EX mein all-zeros input select karta hai, ek NOP bubble insert karta hai taaki frozen instruction EX ko corrupt na kare.

Exercise 2.3

2.1 jaise hi lekin ab ID/EX.RegisterRd = 0 hai. Ek real MIPS HDU RegisterRd ≠ 0 bhi check karta hai. Kya yeh stall karega?

Recall Solution 2.3

Register $0 hardwired zero hai — "$0 mein load" koi usable value produce nahi karta aur koi sach mein uspar depend nahi karta. Isliye guard RegisterRd ≠ 0 add kiya jaata hai. Yahan $RegisterRd = 0$ hai, toh guard false hai, poora condition false hai, aur koi stall assert nahi hota. Normal aage badho.

Level 3 — Analysis

Exercise 3.1

Load-use sequence ko cycle-by-cycle walk karo aur total cycles count karo.

lw   $2, 20($1)   ; I1
add  $4, $2, $5   ; I2

Pipeline 5 stages ka hai; ek stall exactly ek bubble insert karta hai. Assume karo ki MEM/WB se forwarding available hai. add WB finish hone tak kitne cycles lagte hain, aur kitne bubbles insert hue?

Recall Solution 3.1

Stall ke saath, schedule yeh hai (parent note se match karta hua). Program mein sirf yeh do instructions hain, toh cycle 4 ke baad kuch naya fetch nahi hota — IF column simply empty hai kyunki program khatam ho gaya, stall ki wajah se nahi:

Cycle	IF	ID	EX	MEM	WB
1	lw
2	add	lw
3	add	NOP	lw
4	(none)	add	NOP	lw
5	(none)		add	NOP	lw
6	(none)			add	NOP
7	(none)				add

IF mein cycle 3 mein add dobara kyun dikh raha hai khali hone ki bajaye? Stall ke dauran HDU PCWrite = 0 set karta hai, toh PC advance nahi hota — yeh abhi bhi add ka address hold kiye hua hai. IF stage ki apni koi memory nahi hoti; har cycle mein yeh simply woh address fetch karta hai jis par PC currently point kar raha hai. PC add ke address par frozen hone ki wajah se, IF cycle 3 mein usi add ko dobara fetch karta hai. Saath hi IF/ID_Write = 0 IF/ID register ko freeze kar deta hai, toh ID mein already rakhi add ki copy retry ke liye hold hoti hai. Dobara fetched add harmless hai: yeh agli cycle mein IF/ID mein land karta hai aur simply identical value overwrite kar deta hai. Toh ek frozen PC repeated fetch produce karta hai, na ki empty slot.

add cycle 7 mein WB reach karta hai. Ek bubble insert hua (cycle 3 ka NOP). Cycle 5 mein, lw ka data MEM/WB mein hai aur forwarding unit ise add ke EX ke liye feed karta hai — yeh reference figure mein "MEM/WB → ALU" label wala arrow apna kaam kar raha hai.

Exercise 3.2

ID mein ek instruction ke liye combined decision tree follow karo jo RegisterRs = 3 read kar raha hai. Batao:

(a) EX/MEM.RegisterRd = 3, EX/MEM.RegWrite = 1, ID/EX.MemRead = 0.
(b) EX/MEM.RegisterRd = 7, MEM/WB.RegisterRd = 3, MEM/WB.RegWrite = 1, ID/EX.MemRead = 0.
(c) ID/EX.RegisterRd = 3, ID/EX.MemRead = 1.

Har ek ke liye batao ki forwarding resolve karta hai ya HDU (stall).

Recall Solution 3.2

(a) EX-hazard match RegWrite ke saath → EX/MEM se forward (reference figure mein "EX/MEM → ALU" label wala arrow). Koi stall nahi.
(b) EX match nahi, lekin MEM-hazard match RegWrite ke saath → MEM/WB se forward ("MEM/WB → ALU" wala arrow). Koi stall nahi.
(c) Ek load ka source abhi EX mein hai → data ready nahi → HDU ek cycle stall karta hai ("STALL" arrow), phir forwarding kaam sambhal leta hai.

Exercise 3.3

Ek naive 5-stage design branches ko EX mein resolve karta hai. Ek taken branch ko branch ke baad se fetch hue har instruction ko flush karna hota hai. Kitne wrong-path instructions flush hote hain (yani branch penalty)? Phir batao penalty kya hogi agar branch ID mein resolve ho.

Recall Solution 3.3

Is page par counting convention yeh hai: branch penalty un wrong-path instructions ki sankhya hai jo fetch ho chuke hain aur discard karne padte hain. Count depend karta hai is baat par ki kaun sa stage pehle branch outcome jaanta hai, kyunki pipeline tab tak har cycle mein ek naya instruction fetch karta rehta hai.

EX mein resolve karo: branch IF→ID→EX travel karta hai, aur yeh apna outcome sirf EX ke end mein jaanta hai. Tab tak do younger instructions fetch ho chuke hain (ek branch ke ID cycle mein, ek uske EX cycle mein), dono wrong → penalty = 2. (Kabhi kabhi "3" quote hota hai — woh convention bhi us cycle ko count karta hai jismein correct target finally fetch hota hai as lost, yaani woh lost cycles measure karta hai na ki discarded instructions. Same pipeline, alag cheez count ho rahi hai. Is page par hum discarded instructions count karte hain, isliye 2 use karte hain.)
ID mein resolve karo: ID mein ek comparator aur target adder rakhe jaane par, outcome ek stage pehle pata chal jaata hai, toh sirf ek younger instruction (branch ke ID cycle mein PC+4 fetch) fetch hua hoga → penalty = 1.

Yahi woh "penalty 2→1" (ya lost-cycle convention mein "3→1") improvement hai jo parent note describe karta hai. Dekho 5.2.11-Branch-prediction ki prediction ise 0 ki taraf kaise push karti hai.

Level 4 — Synthesis

Exercise 4.1

Ek minimal HDU ka complete output interface design karo. Inputs: ID/EX.MemRead, aur register-number fields ID/EX.RegisterRd, IF/ID.RegisterRs, IF/ID.RegisterRt, saath mein RegisterRd ≠ 0 guard bhi. Internal Stall signal ke liye boolean do aur woh teen control outputs bhi jo HDU stall hone par drive karta hai.

Recall Solution 4.1

Pehle internal detection signal: $Stall = MemRead \land (RegisterRd \neq = 0) \land ((RegisterRd = RegisterRs) \lor (RegisterRd = RegisterRt)) .$ Phir HDU us ek signal se poora output interface drive karta hai:

$PCWrite = \neg Stall$ — toh PCWrite = 0 exactly tab jab Stall = 1 (PC freeze karo).
$IF/ID_Write = \neg Stall$ — toh IF/ID_Write = 0 exactly tab jab Stall = 1 (dependent instruction ko ID mein hold karo).
$Control_Mux = \neg Stall$ — toh Control_Mux = 0 exactly tab jab Stall = 1 (ID/EX mein NOP bubble inject karo).

Jab Stall = 0 toh teeno 1 hain aur pipeline normally aage badhti hai. Yeh parent note ke Verilog sketch ko mirror karta hai, RegisterRd != 0 guard add karke aur do write-enables plus bubble mux spell out karke. Yeh purely combinational hai: koi clocked storage nahi, outputs cycle ke andar valid.

Exercise 4.2

Back-to-back loads consider karo:

lw  $2, 0($1)     ; I1
lw  $3, 0($2)     ; I2  (address uses $2!)
add $4, $3, $2    ; I3

Har woh stall identify karo jo HDU insert karta hai aur har ek ko justify karo.

Recall Solution 4.2

I1→I2: I2 apna address $2 se compute karta hai, jo I1 load karta hai. Jab I1 EX mein hai (MemRead=1, RegisterRd=2) aur I2 ID mein RegisterRs=2 read kar raha hai → 1 cycle stall. Address computation un-arrived load data use nahi kar sakta, aur address ALU ko forwarding MEM se pehle nahi aa sakti.
I2→I3: I3 $3 (I2 ne load kiya) aur $2 read karta hai. Jab I2 EX mein hai MemRead=1, RegisterRd=3 ke saath, aur I3 ID mein $3 read kar raha hai → 1 cycle stall. Bubble ke baad, $3 MEM/WB se forward hota hai; $2 (I1 se, jo kaafi pehle done ho chuka hai) normally forward hota hai ya read hota hai.
Total: 2 stalls (2 bubbles).

Level 5 — Mastery

Exercise 5.1

Ek program branch-resolved-in-ID pipeline par run karta hai. 1000 instructions mein se:

200 loads hain, aur unka aadha immediately baad mein ek dependent use se follow hota hai (har aise case = 1 stall).
150 branches hain; 40% taken hain (har taken branch = 1 flush = 1 lost cycle).
Base CPI (cycles per instruction) bina kisi hazard ke = 1.

Effective CPI aur total cycle count compute karo. (CPI = total cycles ÷ instructions.)

Recall Solution 5.1

Load-use stalls: $200 \times \frac{1}{2} = 100$ stall cycles.
Branch flushes: $150 \times 0.40 = 60$ flush cycles.
Total penalty cycles $= 100 + 60 = 160$ .
Total cycles $= 1000 (base) + 160 = 1160$ .
Effective CPI $= 1160/1000 = 1.16$ .

Interpretation: hazards ne 16% overhead add kiya. Branch resolution pehle move karna (ya prediction add karna) 60-cycle branch term ko attack karta hai; har load ke baad ek independent instruction schedule karna 100-cycle stall term ko attack karta hai.

Exercise 5.2

Neeche wale code ko reorder karo (ek legal instruction schedule) taaki HDU zero stalls insert kare, program ka result change kiye bina. $6,$7,$8 load se independent hain.

lw   $2, 0($1)    ; I1
add  $4, $2, $5   ; I2  (uses $2 -> load-use stall)
sub  $6, $7, $8   ; I3  (independent)

Recall Solution 5.2

Independent sub ko load aur uske use ke beech move karo:

lw   $2, 0($1)    ; I1
sub  $6, $7, $8   ; I3 (independent - fills the delay slot)
add  $4, $2, $5   ; I2 ($2's data is now ready via forwarding)

Jab add ID reach karta hai, lw already MEM mein hai (EX mein nahi), toh compare ke liye ID/EX mein MemRead 0 hai — koi stall condition nahi — aur $2 MEM/WB se forward hota hai (reference figure mein "MEM/WB → ALU" label wala arrow). Stalls: 0. Yeh compiler scheduling hai: wahi kaam jo otherwise HDU ek bubble se karta, wo free mein reordering se ho gaya.

Recall Self-test recap

Load-use hi woh single data hazard hai jo stall force karta hai ::: kyunki ek load ka data MEM ke baad tak exist nahi karta, isliye koi earlier stage isse next instruction ke liye time par forward nahi kar sakta. Stall vs flush ::: stall ek still-valid instruction ko baad mein retry karne ke liye hold karta hai jabki kuch discard nahi hota; flush ek wrong-path instruction ko cancel karta hai jo kabhi execute nahi hona chahiye. HDU ID mein kyun hota hai ::: registers ID mein read hote hain, toh source dependencies EX ke stale data use karne se pehle known ho jaati hain. Teen stall signals ::: PCWrite=0 PC freeze karta hai, IF/ID_Write=0 instruction ko ID mein hold karta hai, Control_Mux=0 ID/EX mein ek NOP bubble inject karta hai. Frozen PC IF ko same instruction dobara fetch karne par kyun majboor karta hai ::: IF ki apni koi memory nahi hoti aur yeh simply woh address fetch karta hai jo PC hold kiye hua hai, isliye frozen PC repeated fetch produce karta hai na ki empty slot.

Dekho bhi: 5.2.9-Forwarding-unit, 5.2.7-Pipeline-control-signals, 5.1.3-Control-unit, 5.2.11-Branch-prediction.