Visual walkthrough — Structural hazards

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

Prerequisites jo hum use karenge lekin zaroorat padne par dobara explain karenge: Pipelining Fundamentals, Pipeline Stalls.

---

Step 1 — Grid banao: "pipeline" actually kya hoti hai

KYA. Kisi bhi formula se pehle, humein time ki ek picture chahiye. Hum time ko barabar tukdon mein kaatte hain jise clock cycles kehte hain — sochो yeh ek metronome ki identical ticks hain. Inhe left-se-right line karo. Instructions ko top-se-bottom stack karo. Har instruction paanch stages se guzarti hai, ek stage per cycle:

• IF — Instruction Fetch: memory mein jao, instruction uthao.
• ID — Instruction Decode: pata karo yeh kya keh rahi hai, registers padho.
• EX — Execute: ALU mein arithmetic karo.
• MEM — Memory access: memory mein data padho ya likho (sirf loads/stores yeh actually use karte hain).
• WB — Write Back: result ko ek register mein store karo.

YEH PAANCH HI KYUN, KOI AUR COUNT KYUN NAHI. Paanch ek classic textbook split hai kyunki har stage hardware ka ek alag tukda use karta hai, toh ideally sab paanch ek saath busy ho sakte hain — jaise ek assembly line par paanch workers. Woh "sab ek saath busy" hi pipelining ka poora point hai, aur exactly yahi ek hazard torega.

PICTURE. Diagonal staircase dekho: har instruction upar wali ke ek cycle baad shuru hoti hai. Kisi bhi single vertical column (ek cycle) mein tum paanch alag-alag instructions dekhte ho, har ek alag stage mein.

---

Step 2 — Perfect case: ideal CPI exactly 1 kyun hota hai

KYA. Ek lambe program ke liye staircase dekho. Instruction 1 cycle 5 par finish hoti hai. Instruction 2 cycle 6 par. Instruction 3 cycle 7 par. Pehle chaar "fill-up" cycles ke baad, har single cycle mein ek instruction right edge se bahar aati hai.

YEH CPI $=1$ KYUN DETA HAI. Agar $N$ instructions finish hoti hain aur (bade $N$ ke liye) har ek net ek cycle leti hai jab pipe bhar jaaye, toh total cycles $\approx N$, isliye

${\text{CPI}}_{\text{ideal}}=\frac{\text{total cycles}}{\text{instructions}}=\frac{N}{N}=1.0$

• ${\text{CPI}}_{\text{ideal}}$ — best jo hum kabhi kar sakte hain.
• $\frac{\text{total cycles}}{\text{instructions}}$ — average cost ki definition: har finished kaam par kitni ticks.
• $=1.0$ — har tick par ek finished instruction. Yeh woh number hai jise har hazard kharaab karne ki koshish karta hai.

PICTURE. Green arrows completions ko right edge se jaate dikhate hain — har column mein ek, perfectly regular.

Recall

Ek full, hazard-free pipeline mein, har clock cycle mein kitni instructions finish hoti hain? ::: Exactly ek — isliye ideal CPI $=1.0$ hota hai.

---

Step 3 — Collision: do stages EK memory ke liye haath badhate hain

KYA. Ab maano machine mein ek single unified memory hai — memory mein ek hi darwaza, jo dono kamon ke liye use hota hai: instructions fetch karna (IF stage) aur data padhna/likhna (MEM stage). Staircase dobara overlay karo aur cycle 4 ko ghauro:

• Instruction 1 MEM mein hai — woh data ke liye memory touch karna chahti hai.
• Instruction 4 IF mein hai — woh apni instruction ke liye memory touch karna chahti hai.

Ek hi darwaze par same cycle mein do haath.

YEH STRUCTURAL HAZARD KYUN HAI AUR KOI AUR CHEEZ KYUN NAHI. Instructions mein khud kuch galat nahi hai — woh ek doosre ke data par depend nahi karti (woh data hazard hota) aur koi branch future decide nahi kar raha (woh control hazard hota). Problem purely hardware ki kami hai: ek memory port, do customers, same cycle. Yahi structural hazard ki definition hai.

PICTURE. Red burst I1 ke MEM cell aur I4 ke IF cell ke crossing par hai — dono single grey memory box ko point karte hain.

---

Step 4 — Fix: ek bubble (stall) daalo

KYA. Dono mein se sirf ek memory use kar sakta hai. Hum purani instruction (I1, MEM mein) ko jeetnay dete hain, aur nyi wali (I4) ko ek cycle ke liye freeze karte hain. Woh frozen khaali slot ek bubble hai.

BUBBLE KYUN KAAM KARTA HAI. I4 ki fetch ko ek cycle delay karke, I1 pehle apna memory access finish karta hai; darwaza phir free ho jaata hai aur I4 saaf fetch karta hai. Kuch skip nahi hota, kuch corrupt nahi hota — humne simply wait kiya. Cost ek cycle hai jisme koi nayi instruction pipe mein nahi gayi.

PICTURE. Plum-coloured bubble cell wasted cycle dikhata hai; I4 ke peeche har instruction ek column right shift ho jaati hai (puri tail shift hoti hai).

---

Step 5 — Counting: "kitni baar" ko ek number $p$ mein badlo

KYA. Formula paane ke liye humein poochhna hoga: yeh collision kitni baar hoti hai? MEM stage actually sirf loads aur stores (instructions jo data memory touch karti hain) use karta hai. Maano saari instructions ka ek fraction $f_{\text{mem}}$ loads/stores hain. Aisi har instruction, jab MEM tak pahunchi, jo bhi fetch ho raha hota hai usse collide karti hai — ek collision, ek bubble.

FRACTION KYUN, COUNT KYUN NAHI. Hum poore program par average kar rahe hain, toh hum probabilities ke saath kaam karte hain. Maano

$p=f_{\text{mem}}$

• $p$ — probability (chance, 0 aur 1 ke beech) ki ek given instruction stall trigger karegi.
• $f_{\text{mem}}$ — memory operations wali instructions ka fraction, e.g. $0.30$ matlab 10 mein se 3.

PICTURE. 10 instruction-tokens ki ek bar: colored 3 memory ops hain (har ek ek bubble cause karta hai), pale 7 bina rukhe guzar jaate hain.

---

Step 6 — Counting: har collision kitne cycles karti hai, $s$

KYA. Step 4 mein humne dekha ki ek collision fix karne ki cost exactly ek wasted cycle thi. Collision per cost ko stall penalty $s$ kehte hain. Single-memory hazard ke liye, $s=1$.

ISSE ALAG KYUN NAME KAREIN. Doosre structural hazards ek se zyada cycles cost kar sakte hain (ek slow shared multiplier do ya teen cycles block kar sakta hai). $s$ ko apna symbol rakhne se, wahi formula har structural hazard cover karta hai — hum sirf sahi penalty plug in karte hain.

PICTURE. Ek collision par magnifying glass exactly ek plum bubble cell dikhata hai = $s=1$; ek side sketch dikhata hai $s=2$ kaisa lagega (do bubbles) ek heavier resource ke liye.

---

Step 7 — Result assemble karo: effective CPI

KYA. Har instruction ideal 1 cycle karti hai plus uska bubbles ka average share. Add karo:

${\text{CPI}}_{\text{actual}}=\underset{=1.0}{\underbrace{{\text{CPI}}_{\text{ideal}}}}+\underset{\text{wasted cycles}}{\underbrace{p\times s}}=1+ps$

• ${\text{CPI}}_{\text{ideal}}=1.0$ — Step 2 se perfect one-per-cycle base.
• $ps$ — Step 6 se average bubble tax.
• inका sum — hazards count hone ke baad instruction per real average cost.

Memory example mein plug karo, $p=f_{\text{mem}}=0.30$, $s=1$:

${\text{CPI}}_{\text{actual}}=1+0.30\times 1=1.30$

YEH PLAIN SUM KYUN HAI. Bubbles extra cycles hain jo ideal schedule par chipke hain — yeh naa useful kaam hatate hain naa overlap karte hain, toh hum simply inhe add karte hain. Koi hidden multiplication nahi, koi fancy correction nahi.

PICTURE. Ek stacked bar: useful kaam ka tall $1.0$ block upar stall ka short $0.30$ plum block — total height $1.30$.

---

Step 8 — CPI ko lost speed mein badlo, aur edge cases cover karo

KYA. Speed CPI ke inversely proportional hai (har instruction ki zyada cost = slower machine). Perfect aur actual compare karo:

$\text{Relative speed}=\frac{{\text{CPI}}_{\text{ideal}}}{{\text{CPI}}_{\text{actual}}}=\frac{1.0}{1.30}\approx 0.77$

Toh machine apni ideal rate ke $\approx 77\%$ par chalti hai — $\approx 23\%$ slowdown.

• numerator ${\text{CPI}}_{\text{ideal}}$ — cycles jo perfect machine ko chahiye.
• denominator ${\text{CPI}}_{\text{actual}}$ — cycles jo real machine ko chahiye.
• ratio $<1$ — real machine slower hai; $1-0.77=0.23$ woh fraction hai jo speed lost hua.

Ab edge cases — reader ko koi aisa scenario nahi milna chahiye jo humne skip kiya ho:

• $p=0$ (koi memory ops nahi, ya alag I/D caches): $\text{CPI}=1+0=1.0$. Kabhi collision nahi — yeh Harvard-style split-cache cure hai. Hazard gayab ho jaata hai, sirf shrink nahi hota.
• $p=1$ (har instruction resource hit karti hai): $\text{CPI}=1+s$. Worst case; $s=1$ ke saath pipe half-wasted hai.
• $s=0$ (hardware ne ek port/adder add karke fix kiya): $\text{CPI}=1+p\times 0=1.0$ regardless of $p$. Hardware throw karne se penalty zero ho jaati hai — parent note ka Solution 1.
• Non-memory hazards (bada $s$): ek shared 3-cycle multiplier jo 20% instructions use karta hai deta hai $\text{CPI}=1+0.20\times 3=1.60$ — same formula, naye numbers. Isliye $s$ ko symbolic rakhna zaroori tha.

PICTURE. $s=1,2,3$ ke liye $p$ ke against $\text{CPI}=1+ps$ ka ek curve, teeno edge points ($p=0$, $p=1$, $s=0$) circled ke saath.

---

Ek-picture summary

Upar sab kuch, compressed: staircase single memory par collide karta hai (Step 3), hum ek bubble insert karte hain (Step 4), uski chance $p$ aur cost $s$ count karte hain (Steps 5–6), aur tax ko ideal 1 par add karke $\text{CPI}=1+ps$ paate hain (Step 7), jo lost speed mein convert hota hai (Step 8).

Recall Feynman retelling — plain words mein wapas bolo

Paanch workers ko ek assembly line par imagine karo, har ek ek kaam karta hai, toh har tick ek product finish hota hai — yeh "cost 1" hai. Lekin do workers ek single tool share karte hain (memory door). Jab bhi koi instruction galat moment par woh shared tool chahti hai, ek worker ko ek tick ke liye freeze karna padta hai — ek "bubble" — aur us tick mein koi product nahi aata. Agar har 10 mein se 3 instructions aisi freeze cause karti hain (woh hai $p=0.3$), aur har freeze exactly 1 tick waste karta hai ($s=1$), toh average par har instruction $0.3$ extra ticks ka dead time carry karti hai. Use base 1 mein add karo aur tumhe milta hai $1.3$ ticks per instruction — machine $1/1.3\approx 77\%$ full speed par chalti hai. Workers ko ek doosra tool do (split caches, ek extra port) aur freeze cost $s$ zero ho jaati hai, toh tax gayab ho jaata hai aur hum perfect 1 par wapas aa jaate hain. Woh ek line, $\text{CPI}=1+ps$, poori kahani hai — yeh bhi dekho ki yeh ek real machine mein Data Hazards aur Control Hazards ke tax ke saath kaise stack karta hai, aur kyun Superscalar Processors jo high Instruction-Level Parallelism chase karte hain unhe $s$ ko near zero rakhne ke liye bahut saare ports add karne padte hain.