Exercises — Structural hazards

$\text{CPI}=1+fs$ ke edge cases (Level 5 se pehle padho)

• $f=0$ ya $s=0$ → $\text{CPI}=1$: koi real hazard nahi, ideal pipeline.
• $f=1,s=1$ → $\text{CPI}=2$: har instruction ek baar stall karta hai, throughput half.
• Agar $f\cdot s>1$ ho toh? Bilkul allowed — iska matlab sirf yeh hai ki average instruction ek se zyada bubble khata hai (e.g. $f=1,s=4$ gives $\text{CPI}=5$). CPI pipeline depth tak grow kar sakta hai (full serialisation); yeh kabhi $1$ se neeche nahi jaata kyunki $f,s\ge 0$.
• Negative stalls impossible hain: $f\ge 0$ aur $s\ge 0$ definition se hain (tum un-stall nahi kar sakte), isliye $\text{CPI}\ge 1$ hamesha. Agar koi formula tumhe $\text{CPI}<1$ de toh sign error ki hai.

Chart ko column by column padho (har column ek clock cycle hai). Structural hazard tab hota hai jab do stages same column mein same physical unit maangti hain — woh exactly Figure 1 mein red boxes ki pair hai.

• Cycle 4: I1 MEM mein hai (data ke liye memory touch kar raha hai) aur I4 IF mein hai (apni instruction fetch karne ke liye memory touch kar raha hai).
• Single memory port unme se sirf ek ko serve kar sakta hai.

Answer: Hazard cycle 4 mein hai; conflict I1 ke MEM stage aur I4 ke IF stage ke beech hai, dono single memory port maang rahe hain.

• (a) Data hazard — yeh information/order ke baare mein hai (ek value produce hoti phir consume hoti), shared hardware ka box nahi.
• (b) Structural hazard — do stages ek hi physical adder ek cycle mein chahte hain.
• (c) Control hazard — decision ki aage kya fetch karna hai woh resolve nahi hua.

Rule of thumb: agar tum ise hardware unit ka ek aur copy khareed kar fix kar sako, toh structural tha.

Page ke upar wala boxed model use karo, ${\text{CPI}}_{\text{actual}}={\text{CPI}}_{\text{ideal}}+fs$. Pehle har symbol:

• $f=f_{\text{mem}}=0.30$ woh fraction of instructions hai jo hazard trigger karte hain.
• $s=1$ cycle stall penalty per hazard hai.

$\text{Stalls per instruction}=f\times s=0.30\times 1=0.30$ ${\text{CPI}}_{\text{actual}}={\text{CPI}}_{\text{ideal}}+fs=1.0+0.30=1.30$

Ab page ke upar se derive kiya "$\text{Performance}\propto 1/\text{CPI}$ at equal clock" result use karo. Same machine, same clock, isliye hazarded pipeline ka ideal se ratio hai: $\frac{{\text{Perf}}_{\text{hazard}}}{{\text{Perf}}_{\text{ideal}}}=\frac{{\text{CPI}}_{\text{ideal}}}{{\text{CPI}}_{\text{actual}}}=\frac{1.0}{1.30}\approx 0.769$

Answer: ${\text{CPI}}_{\text{actual}}=1.30$; performance lost $=1-0.769=0.231\approx 23\%$ slower.

Boxed model mein, memory hazard eliminate karna uska $f$ ko $0$ set karta hai, toh woh term disappear ho jaati hai. Sirf ALU term bachi hai: ${\text{CPI}}_{\text{actual}}=1.0+f_{\text{alu}}\times 1=1.0+0.05=1.05$

Purane $1.30$ se compare karo. Same clock phir, toh $\text{Perf}\propto 1/\text{CPI}$ use karo; new design ka old se speedup unke CPIs ka ratio hai: $\frac{{\text{Perf}}_{\text{new}}}{{\text{Perf}}_{\text{old}}}=\frac{{\text{CPI}}_{\text{old}}}{{\text{CPI}}_{\text{new}}}=\frac{1.30}{1.05}\approx 1.238$

Answer: ${\text{CPI}}_{\text{actual}}=1.05$; redesign machine ko lagbhag 24% faster banata hai. Haan, help ki.

Ideal issue mein "8" kyun aata hai. Ek pipeline mein, ek naya instruction har clock pe IF mein enter karta hai aur, bina hazards ke, exactly ek instruction har clock pe finish hota hai. Isliye 8 instructions issue karna ideally 8 issue slots leta hai — ek cycle each. Yahan se woh bare $8$ aata hai (yeh ideal-issue count hai, kisi bhi bubble se pehle; start-up fill exclude hai jaise problem ne kaha).

Har stall ka cause: jab ek load MEM pe pahunchta hai (Figure 2 mein ek red box), us instruction ko jo us same cycle mein IF enter karna chahti hai wait karna padta hai. Pehla load (L1) cycle 4 mein MEM pe pahunchta hai jab L4 IF chahta hai — toh L4 stall karta hai. Baad ke har load similarly ek stall push karta hai apne peeche wale instruction pe.

Window ke andar counting: Loads L1…L8 mein se har ek chahta hai ek MEM/IF collision generate kare apne follower ke saath. Last load L8 ka in 8 ke andar koi follower nahi hai — uska induced stall ek aisi instruction pe padega jo is window ke bahar hai — isliye woh yahan koi stall contribute nahi karta. Bacha collision L1…L7 se → 7 stall cycles.

$\text{cycles}=\underset{\text{ideal issue}}{\underbrace{8}}+\underset{\text{stalls}}{\underbrace{7}}=15,\text{CPI}=\frac{15}{8}=1.875$

Answer: Window ke andar 7 stall cycles; $\text{CPI}=15/8=1.875$.

Model se sanity check: steady state mein (infinite stream) har load stalls karta hai, toh $f=1.0,s=1$ gives $\text{CPI}\to 1+1.0\times 1=2.0$. Humara windowed $1.875$ $2.0$ se thoda neeche hai kyunki L8 ka stall window ke bahar spill ho gaya — exactly wahi jo hum expect karte hain. ✓

I1, I3, I5, I7 pe loads → 4 loads, har ek apne peeche wale instruction (I2, I4, I6, I8 respectively — sab window ke andar) pe 1 stall induce karta hai. Toh 4 stall cycles.

$\text{cycles}=8+4=12,\text{CPI}=\frac{12}{8}=1.5$

Boxed model se cross-check, $f=4/8=0.5$, $s=1$: $\text{CPI}=1+0.5\times 1=1.5✓$

Answer: 4 stalls; $\text{CPI}=1.5$.

Baseline CPI — kyunki teeno hazards kabhi same instruction ko hit nahi karte, unke per-instruction stall contributions $f_i{s}_i$ simply ideal ke upar add ho jaate hain (yeh boxed model hai kaafi saare terms ke saath): $\text{CPI}=1+{\sum }_i{f}_i{s}_i=1+(0.30\cdot 1+0.05\cdot 1+0.02\cdot 1)=1+0.37=1.37$

"Benefit = $fs$" kyun. Kisi hazard ko remove karna CPI sum se exactly uska term $f_i{s}_i$ delete karta hai — toh CPI jo tum save karte ho hazard $i$ fix karke woh precisely $f_i{s}_i$ hai. Yahi fix ka benefit hai. Yahan har $s_i=1$ hai, isliye benefit $=f_i$.

"Benefit per area" sahi metric kyun hai. Ek hard area budget ke saath tum chahte ho spend ki gayi har area unit pe maximum CPI remove ho — classic bang-for-buck ratio $\frac{\text{CPI removed}}{\text{area}}$. Fixes ko usse rank karo:

Budget = 5. Memory fix (area 10) seedha unaffordable hai. 5 units ke andar ALU (1) + write port (4) = exactly 5 units le sakte ho:

• CPI removed $=0.05+0.02=0.07$ → new $\text{CPI}=1.37-0.07=1.30$.

Alternative: sirf ALU (1 unit) 0.05 remove karta hai → $\text{CPI}=1.32$, 4 units unused chhod ke. ALU + write port dono lena pura budget spend karta hai aur $\text{CPI}=1.30$ tak pahunchta hai, 5 units mein best achievable.

Answer: ALU adder + register write port kharido (total area 5), $\text{CPI}=1.30$ tak pahunchte hain. Memory fix, though woh sabse bada single stall remove karta hai, budget mein fit nahi hota.

A: ${\text{CPI}}_A=1.0$. B: ${\text{CPI}}_B=1+f\cdot 1=1+f$. Same clock, isliye (page ke upar ke result se) equal performance matlab equal CPI: $1+f_{\text{eq}}=1.0\Rightarrow f_{\text{eq}}=0.$

Interpretation: nonzero hazard frequency ke saath, B hamesha hazard-free Harvard machine se slower rahega. B sirf A se tab tie karta hai jab $f_{\text{eq}}=0$ ho — yaani practically kabhi nahi. Toh choice purely performance (A) vs area/power (B) hai: B tabhi justified hai jab 10 extra area units aur power guaranteed $\approx 23\%$ slowdown (at $f=0.30$) se zyada matter kare.

Answer: $f_{\text{eq}}=0$; B kabhi A se speed mein match nahi kar sakta, toh B strictly area/power reasons ke liye chuno.

Ek cycle mein demand do 2-source, 1-destination instructions ke liye jo saath issue ki gayi hain:

• Reads needed: har op 2 source registers read karta hai, do ops → $2\times 2=4$ register reads ek cycle mein.
• Writes needed: har op 1 destination write karta hai, do ops → $2\times 1=2$ register writes jab dono saath WB pe pahunchte hain.

(a) Read-port hazard? File mein 3 read ports hain lekin cycle 4 demand karta hai. $4>3$, toh haan, read-port structural hazard hai — file physically 4 source operands ek saath deliver nahi kar sakta, toh ek instruction stall karna padega (ya issue ek op tak narrow karna padega us cycle mein).

(b) Write-port hazard? File mein 1 write port hai lekin do destinations same WB cycle mein commit karna chahte hain. $2>1$, toh haan, write-port structural hazard hai — do writes serialise karne padte hain, ek ko stall karte hue.

(c) Kabhi stall na karne ke liye minimum ports dual 2-source/1-dest issue ke liye: sab sources ke liye enough read ports ($2\times 2=4$) aur sab destinations ke liye enough write ports ($2\times 1=2$). Toh register file ko 4 read ports aur 2 write ports chahiye (generally, $2n$ read aur $n$ write ports $n$-wide issue of 2-source/1-dest ops ke liye).

Answer: (a) haan — 4 reads chahiye, 3 hain; (b) haan — 2 writes chahiye, 1 hai; (c) 4 read ports, 2 write ports. Yahi reason hai ki wider Superscalar Processors itna zyada pay karte hain — port count issue width ke saath scale karta hai, aur har extra port area aur power add karta hai.

• (a) $f=0\Rightarrow \text{CPI}=1$: kabhi koi hazard nahi, ideal pipeline, ek instruction har cycle mein finish hota hai. Yeh Harvard/split-cache dream hai.
• (b) $f=1,s=1\Rightarrow \text{CPI}=2$: har instruction exactly ek cycle stall karta hai. Diagram har instruction ke baad ek bubble hai — throughput half (Ex 3.1 ke steady-state limit 2.0 se match karta hai ✓).
• (c) $s=0\Rightarrow \text{CPI}=1$: ek "hazard" jo zero cycles cost kare woh hazard hai hi nahi — resource conflict for free resolve ho gaya (e.g. ek cheap duplicated unit). Frequency $f$ irrelevant ho jaati hai.
• (d) $f=1,s=4$ ek 5-stage pipe pe $\Rightarrow \text{CPI}=5$: har instruction 4 cycles wait karta hai, toh instruction $k+1$ tabhi start hoti hai jab instruction $k$ fully drain ho jaaye. Yeh serial execution hai — pipelining ka overlap completely destroy ho gaya. CPI pipeline depth ke equal hai, worst case. Note $f\cdot s=4>1$ yahan, jo bilkul valid hai: average instruction ek se zyada bubble khata hai.

Answer: (a) ideal, CPI 1; (b) CPI 2, har instruction ke baad ek bubble; (c) real hazard nahi, CPI 1; (d) CPI 5 = fully serialised, pipeline ka koi benefit nahi baca.

Structural hazard define hota hai sharing se … ::: same cycle mein physical hardware resource share karna. Hazards ke saath CPI formula ::: $\text{CPI}=1+fs$. Performance $\propto 1/\text{CPI}$ kyun hai ::: time per instruction $=\text{CPI}\times$ cycle time; performance uska reciprocal hai, isliye equal clock pe bada CPI = slower. Ex 2.1 answer ::: CPI = 1.30, lagbhag 23% slower. Ex 3.2 answer ::: CPI = 1.5. Ex 4.1 best-within-budget CPI ::: 1.30 (ALU + write-port fixes). Dual 2-source/1-dest issue ke liye kitne ports chahiye ::: 4 read, 2 write. $f=1,s=4$ on 5 stages pe limiting CPI ::: 5 (fully serial).