Structural hazards: Worked examples — Hinglish deep dive

5.2.5 · D3 · Hardware › Processor Datapath & Pipelining › Structural hazards

Yeh page Structural hazards ka exhaustive worked-example companion hai. Parent note ne resource conflict ka idea build kiya tha — do pipeline stages ek hi clock tick mein same piece of hardware ke liye haath badhate hain. Yahan hum har tarah ke scenario ko dhundhte hain jo yeh idea produce kar sakta hai aur arithmetic grind karte hain, taaki exam mein koi bhi case surprise na kare.

Agar neeche koi word unfamiliar lage (stage, cycle, stall, CPI), toh parent note aur Pipelining Fundamentals unhe zero se define karte hain. Hum sirf wahi reuse karte hain.

The scenario matrix

Har structural-hazard problem jo tumhe milega, woh neeche ke cells mein se ek hoga. Ek "cell" ek class of situation hai — kaunsa resource conflict hai, numbers kaise behave karte hain, aur question actually kya test kar raha hai — in teenon ka combination.

#	Cell (case class)	Kya ise distinct banata hai	Covered by
A	Single unified memory (IF vs MEM)	Classic 2-way port conflict, non-zero load fraction	Example 1
B	Zero-hazard / degenerate input	Hazard probability $p = 0$ → koi stall nahi	Example 2
C	Every-instruction hazard (limiting value)	Conflict har cycle par, $p = 1$	Example 3
D	Multi-cycle resource (penalty $s > 1$ )	Stall penalty ek cycle se bada	Example 4
E	Do independent hazard sources add hue	Memory hazard aur functional-unit hazard saath mein	Example 5
F	Fix-by-hardware comparison	Same program, resource add karne se pehle vs baad mein	Example 6
G	Real-world word problem	Embedded chip, throughput in MIPS	Example 7
H	Exam twist: "reorder to remove stall"	Arithmetic ki jagah scheduling	Example 8
I	Superscalar / port-count degenerate	Ports vs ek cycle mein demanded accesses	Example 9

Numbers se pehle, ek master formula jo har cell use karta hai.

Formula Har cell ke peeche yahi ek equation hai

$CPI_{actual} = CPI_{ideal} + \sum_{i} (p_{i} \times s_{i})$ Doosre term ko "stall cycles per instruction" padho. Ab har symbol ka plain-words meaning:

$CPI$ matlab clocks per instruction — average number of clock cycles jo ek typical instruction ko "cost" hoti hai. Kam ho toh faster.
$CPI_{ideal} = 1$ ek simple single-issue pipeline ke liye (jab kuch galat nahi hota, har cycle mein ek instruction finish hoti hai).
$p$ hazard hit hone ki probability per instruction hai — $0$ aur $1$ ke beech ka fraction. Jab hazard ka rate kisi instruction-type fraction ke barabar ho, toh hum likh sakte hain, jaise $p = f_{mem}$ — letter $f$ sirf batata hai woh probability kahan se aa rahi hai, yeh wahi $p$ hai.
$s$ stall penalty hai — har hazard kitne bubble cycles force karta hai.
$\sum_{i}$ ("sum over $i$ ") har distinct hazard source $i$ ke liye ek term $p_{i} \times s_{i}$ add karta hai. Yahan $i$ hazard types ki list par range karta hai, jaise $i \in {memory, divider, register-port}$ . Example 1 mein sirf ek source hai ( $i$ ek value leta hai), toh sum ek single term hai; Example 5 mein do hain, toh do terms add hoti hain.

Throughput fraction vs ideal $= \frac{CPI _{ideal}}{CPI _{actual}}$ (ek number $\leq 1$ : ideal speed ka woh hissa jo tumhare paas hai). Percentage slowdown $= 1 - \frac{CPI _{ideal}}{CPI _{actual}}$ (woh hissa jo tumne khoya). Hum yeh donon phrasings neeche strictly alag rakhenge.

Example 1 — Cell A: single unified memory

Forecast: andaza lagao — kya CPI $1.1$ , $1.3$ , ya $2.0$ ke paas aayega? (Apna guess rokho; is example ke end mein confirm karenge.)

Neeche ki figure ek pipeline timeline hai: har row ek instruction hai, har column ek clock cycle hai, aur har rounded box dikhata hai ki woh instruction us cycle mein kaun sa stage occupy kar raha hai. Column 4 dekho — wahan collision hoti hai.

$p$ aur $s$ identify karo. Har load/store, jab MEM mein hota hai, memory chahta hai usi tick par jab ek baad waali instruction IF chahti hai. Toh $p = f_{mem} = 0.30$ aur $s = 1$ . Yeh step kyun? Formula ko ek hazard probability aur ek penalty chahiye — aur kuch nahi. Hume English (" $30%$ loads hain") ko $p$ mein translate karna hai.
Equation apply karo. $CPI = 1 + (0.30) (1) = 1.30$ . Yeh step kyun? Master formula mein direct substitution — ise build karne ka poora point yahi hai.
Percentage slowdown. Throughput fraction $= \frac{1.0}{1.30} = 0.769 \dots$ , toh pipeline ideal speed ka $76.9%$ rakhta hai. Percentage slowdown $= 1 - 0.769 = 0.231$ → $23.1%$ slower. Yeh step kyun? Performance CPI ke inversely proportional hai; slowdown woh lost share hai, yaani throughput fraction se ek minus karo.

Forecast check: answer $1.30$ middle guess hai — agar tumne " $1.3$ ke paas" chuna tha, sahi tha.

Verify: Figure dekho — cycle 4 mein, I1 MEM (coral) mein baitha hai aur I4 IF (lavender) chahta hai: ek memory, do demands → exactly ek bubble, $s = 1$ se match karta hai. Units: CPI cycles/instruction hai; throughput fraction $0.769$ aur slowdown $0.231$ dimensionless hain. ✓

Example 2 — Cell B: degenerate zero case

Forecast: kya saare memory instructions hataane se hazard poora khatam ho jaata hai, ya koi residual stall hamesha rehta hai? (Abhi decide karo; answer neeche aata hai.)

$p = 0$ set karo. Koi instruction kabhi MEM tak data memory maangne nahi pahunchi, toh IF kabhi block nahi hoti. Yeh step kyun? Yeh model ki boundary hai — hume confirm karna hai ki jab hazard ho hi nahi sakta toh formula sensibly behave karta hai.
Formula apply karo. $CPI = 1 + (0) (1) = 1.0$ . Yeh step kyun? Dikhata hai ki structural-hazard term vanish ho jaata hai; pipeline ideal par wapas aa jaati hai.

Forecast check: hazard poora khatam ho jaata hai — CPI ideal $1.0$ par aa jaata hai zero residual stall ke saath. Agar tumne "no residual stall" predict kiya tha, sahi.

Verify: $1 + 0 = 1$ . Ek pipeline jo kabhi conflict nahi karti, uska CPI ideal hona chahiye — number hamare intuition ko confirm karta hai, toh model apni lower edge par trustworthy hai. ✓

Example 3 — Cell C: limiting value $p = 1$

Forecast: agar har instruction ek baar stall karti hai, toh kya CPI double ho jaata hai, ya kam badhta hai? (Guess karo, phir padho.)

$p = 1$ , $s = 1$ set karo. Har instruction exactly ek bubble leta hai. Yeh step kyun? Upper extreme test karna $0 \leq p \leq 1$ range ko complete karta hai — kisi bhi reader ko yeh wonder nahi karna chahiye "agar hamesha ho toh kya?"
Formula apply karo. $CPI = 1 + (1) (1) = 2.0$ . Yeh step kyun? Confirm karta hai ki 1-cycle penalty ka worst case doubling hai, kuch wilder nahi.
Percentage slowdown. Throughput fraction $= \frac{1.0}{2.0} = 0.5$ ; slowdown $= 1 - 0.5 = 0.5$ → pipeline half speed par chalti hai ( $50%$ slower).

Forecast check: CPI exactly double hokar $2.0$ — agar tumne "double" guess kiya tha, bilkul sahi.

Verify: Har instruction ke saath ek bubble, effectively do cycles per completed instruction → CPI $= 2$ . Half throughput. Numbers agree. ✓

Example 4 — Cell D: ek multi-cycle resource ( $s > 1$ )

Forecast: ek rare event lekin costly — kya Example 1 ke frequent-but-cheap hazard se bada ya chhota effect? (Predict karo, phir step 3 check karo.)

$p$ aur $s$ padhlo. $p = 0.08$ , $s = 3$ (teen bubble cycles per divide). Yeh step kyun? Penalty ab $1$ nahi hai; hume $s = 1$ blindly assume nahi karna chahiye.
Formula apply karo. $CPI = 1 + (0.08) (3) = 1 + 0.24 = 1.24$ . Yeh step kyun? Dikhata hai ki product $p \times s$ matter karta hai, na sirf koi ek factor.
Example 1 se compare karo. Divider stall term $0.24 <$ memory stall term $0.30$ , toh CPI $1.24 < 1.30$ : rare-but-costly divider frequent memory clash se thoda kam hurt karta hai. Yeh step kyun? Exams mein "kaunsa hazard zyada costly hai?" yeh often poochha jaata hai — answer hamesha woh hoga jiska $p \times s$ bada ho.

Forecast check: smaller effect — divider ( $1.24$ ) memory hazard ( $1.30$ ) se kam hurt karta hai. Agar tumne "smaller" guess kiya tha, sahi.

Verify: $0.08 \times 3 = 0.24$ ; $1 + 0.24 = 1.24$ . Aur $0.24 < 0.30$ , toh $1.24 < 1.30$ , comparison confirm karta hai. ✓

Example 5 — Cell E: do hazards stacked

Forecast: kya CPI increases sirf add hoti hain, ya multiply hoti hain? (Ek chuno; answer step 1 mein hai.)

Stall terms add hote hain. Total stalls per instruction $= \sum_{i} p_{i} s_{i} = p_{1} s_{1} + p_{2} s_{2} = 0.30 + 0.24 = 0.54$ . Yahan index $i$ do sources ${memory, divider}$ par range karta hai. Yeh step kyun? Independent bubble sources independent extra cycles contribute karte hain — bubbles count hote hain, toh sum hote hain (yahi master formula ka $\sum_{i}$ hai).
Formula ek baar apply karo. $CPI = 1 + 0.54 = 1.54$ . Yeh step kyun? Master formula ka doosra term saare stall sources ka sum hai.

Forecast check: woh add hoti hain (multiply nahi) — do stall terms $0.30$ aur $0.24$ sum hokar $0.54$ bante hain.

Verify: $0.30 + 0.24 = 0.54$ ; $1 + 0.54 = 1.54$ . Notice karo yeh Example 1 ka CPI ( $1.30$ ) plus Example 4 ka extra ( $0.24$ ) ke barabar hai — additivity holds karta hai. ✓

Example 6 — Cell F: hardware fix se pehle vs baad mein

Forecast: kya speedup exactly $1.30 \times$ hai, ya kuch chhota? (Guess karo, phir step 2 dekho.)

Neeche ki figure dono designs side by side contrast karti hai: left par, ek shared memory box IF aur MEM ko fight karne deta hai; right par, do alag cache boxes har ek stage ko serve karte hain, toh kuch collide nahi karta.

New CPI. Alag caches ke saath, IF aur MEM alag ports use karte hain → $p_{mem} = 0$ , toh $CPI_{new} = 1 + 0 = 1.0$ . Yeh step kyun? Hardware add karna resource conflict khatam karta hai, us hazard ka $p$ zero par la deta hai.
Speedup factor. Performance $\propto 1/ CPI$ , toh speedup $= \frac{CPI _{old}}{CPI _{new}} = \frac{1.30}{1.0} = 1.30$ . Yeh step kyun? Ek hi program par do designs compare karna matlab CPI directly compare karna (clock period unchanged). Yahan speedup $1$ se zyada hai kyunki nayi machine faster hai.

Forecast check: exactly $1.30 \times$ — speedup old CPI ke barabar hai kyunki new CPI $1.0$ hai.

Verify: $1.30/1.0 = 1.30 \times$ faster. Figure Harvard split dikhati hai: do alag memory boxes, toh cycle 4 mein koi clash nahi. Yeh construction se Pipeline Stalls ka cure hai. ✓

Example 7 — Cell G: real-world word problem

Forecast: kya throughput 200, 160, ya 100 MIPS ke paas hoga? (Guess karo; end mein confirm hoga.)

CPI. $CPI = 1 + 0.25 \times 1 = 1.25$ . Yeh step kyun? Throughput ke liye pehle cycles-per-instruction chahiye.
MIPS = clock / (CPI $\times 1 0^{6}$ ). Instructions per second $= \frac{cycles/second}{cycles/instruction} = \frac{200 \times 1 0 ^{6}}{1.25}$ . Yeh instructions per second deta hai; $1 0^{6}$ se divide karna "instructions per second" ko "millions of instructions per second" mein convert karta hai (yahi MIPS mein M ka matlab hai). Toh $\frac{200 \times 1 0 ^{6}}{1.25 \times 1 0 ^{6}} = 160$ MIPS. Yeh step kyun? Hum pehle raw instructions/second nikalte hain, phir $1 0^{6}$ se rescale karte hain purely as a unit change taaki answer millions mein padhe.
Ideal MIPS. CPI $= 1$ ke saath: $\frac{200 \times 1 0 ^{6}}{1.0 \times 1 0 ^{6}} = 200$ MIPS. Hazard cost $= 200 - 160 = 40$ MIPS. Yeh step kyun? "Cost" ideal aur actual throughput ka gap hai.

Forecast check: answer 160 MIPS hai — middle option. Agar tumne "160 ke paas" guess kiya tha, sahi.

Verify: $200/1.25 = 160$ ; $200 - 160 = 40$ MIPS lost. Units: (cycles/s)/(cycles/instr) = instr/s ✓. Sanity: $40/200 = 20%$ loss, $1 - 1/1.25 = 0.20$ se match karta hai. ✓

Example 8 — Cell H: exam twist (reorder karo, arithmetic nahi)

Worked example Statement

Is classic single-adder microarchitecture mein PC $+ 4$ increment IF stage mein compute hota hai (fetch stage program counter ko next instruction par bump karta hai), aur wahi single adder EX-stage arithmetic unit bhi hai. Compiler hardware add nahi kar sakta lekin independent instructions ko reorder kar sakta hai. Neeche diye schedule ko dekho — kya cycle 3 ka structural stall reordering se avoid kiya ja sakta hai, aur asli fix kya hai?

Cycle 3:  ADD in EX  (wants the adder)
Cycle 3:  next instr in IF (wants the adder for PC+4)

Forecast: kya clever ordering yeh dodge kar sakti hai, ya yeh fundamentally ek hardware shortage hai? (Decide karo, phir step 2 check karo.)

Check karo ki conflict order-dependent hai ya nahi. IF (jo PC $+ 4$ compute karta hai) har instruction ke liye har cycle hota hai. EX arithmetic instructions ke liye hota hai. Reordering change karta hai ki EX mein kaunsi instruction hai, na yeh fact ki koi instruction hamesha IF mein hai. Yeh step kyun? Instruction-Level Parallelism scheduling sirf un hazards mein help karta hai jo depend karte hain ki kaunsi instructions adjacent hain; yeh wala nahi.
Conclusion: reordering se avoid nahi hoga. Kyunki IF har cycle adder demand karta hai, EX mein koi bhi instruction collide karegi. $p$ structural hai, schedule-dependent nahi. Yeh step kyun? Structural hazards (physical shortage) ko Data Hazards / Control Hazards (jinhe reordering soften kar sakti hai) se distinguish karta hai.
Asli fix: ek dedicated PC incrementer. IF stage mein sirf PC $+ 4$ ke liye ek alag sasta 32-bit adder sharing khatam karta hai, is hazard ka $p$ $0$ par la deta hai. Yeh step kyun? Parent note ke "add a cheap adder" resolution se match karta hai — ek adder ki cost ≪ endless stalls ki cost.

Forecast check: yeh fundamentally ek hardware shortage hai — reordering ise dodge nahi kar sakta; sirf dedicated adder kaam karta hai. Agar tumne "hardware shortage" guess kiya tha, sahi.

Verify: Logical claim: agar koi resource har cycle ek stage se demand kiya jaata hai, toh koi bhi instruction permutation clash nahi hatati → reordering fail; sirf extra hardware kaam karta hai. Parent ki structural (resource) hazard ki definition se consistent. ✓ (Koi numeric check nahi — yeh cell by design conceptual hai.)

Example 9 — Cell I: superscalar port-count degenerate case

Forecast: sirf 3 read ports hain lekin 4 reads demand hain — kya stall hoga, aur kitna? (Guess karo, phir count follow karo.)

Demanded vs available reads count karo. Demand $= 4$ reads this cycle; supply $= 3$ read ports. Shortfall $= 1$ read jo serve nahi ho sakta. Yeh step kyun? Port hazard purely "demand $>$ supply" hai — dono sides count karo.
Extra access serialize karne ke liye stall karo. Unserved read wait karega, toh register access $1$ cycle ki jagah $2$ cycles mein spread ho jaata hai: penalty $s = 1$ bubble. Yeh step kyun? Teen ports ek cycle mein maximum $3$ reads serve kar sakte hain; $4$ tha read ke liye is cycle mein koi port nahi, toh by definition woh next cycle mein slip karta hai — woh slip hi single stall cycle hai.
Write check. Writes demanded $= 1$ , write ports $= 1$ → supply meets demand, is cycle mein koi write conflict nahi. Yeh step kyun? Hume har port type cover karna hai; reader ko kabhi assume nahi karna chahiye ki writes theek hain bina supply vs demand check kiye.
Master formula mein daalo. Maano $p_{rd}$ un cycles ka fraction hai jahan yeh read-port shortage hoti hai, $s = 1$ ke saath. Read-port hazard sum $\sum_{i} p_{i} s_{i}$ mein ek term $p_{rd} \times 1$ contribute karta hai (yahan index $i = register-port$ ). Worst case lete hain jahan har issue clash kare, $p_{rd} = 1$ , toh $CPI = 1 + (1) (1) = 2.0$ . Yeh step kyun? Page ne promise kiya tha ki har cell $CPI = 1 + \sum_{i} p_{i} s_{i}$ se route karta hai; port hazard simply ek aur $p_{i} s_{i}$ term hai, aur $p = 1$ uska worst case deta hai.

Forecast check: haan stall hoga — exactly 1 cycle ka, worst-case CPI 2.0 push ho jaata hai. Agar tumne "1 cycle stall" guess kiya tha, sahi.

Verify: Reads $4 > 3$ ports → hazard, minimum $1$ stall cycle. Writes $1 \leq 1$ → OK. Worst-case CPI $= 1 + 1 = 2$ . Fix (4th read port add karo) demand $\leq$ supply set karta hai, $p_{rd}$ ko $0$ par le jaata hai, aur stall khatam karta hai — parent ki "more ports" strategy se match karta hai. ✓

Recall Cells par quick self-test

Kaun sa cell bada CPI deta hai, "frequent-cheap" ( $p = 0.3, s = 1$ ) ya "rare-costly" ( $p = 0.08, s = 3$ )? ::: Frequent-cheap: $0.30 > 0.24$ , toh CPI $1.30 > 1.24$ . Products $p \times s$ compare karo. Kya instruction reordering ek structural hazard ko remove kar sakta hai jo har cycle hit karta ho? ::: Nahi — yeh hardware shortage hai, ordering problem nahi; sirf extra hardware (ya stall accept karna) help karta hai. $p = 0$ wale program ka single-port memory par memory-hazard CPI kya hoga? ::: Exactly $1.0$ — stall term vanish ho jaata hai.