Deep pipelining trade-offs: Visual walkthrough — Hinglish deep dive

5.2.11 · D2 · Hardware › Processor Datapath & Pipelining › Deep pipelining trade-offs

Step 1 — "Kaam karna" kya cost karta hai: ek lamba job

KYA HAI. Ek single instruction ko ek lambi strip of kaam ki tarah imagine karo — jaise ek plank of wood jo ek machine se guzarne mein time leta hai. Poore travel time ko $T_{0}$ kaho.

YE SHURUAAT KYUN. Kaam ko split karne se pehle, hum agree karte hain ki unsplit cheez kya cost karti hai. Baad ki sab cheez is ek number ke against measure hoti hai.

PICTURE. Figure mein, amber bar poora job hai. Uski length hi time $T_{0}$ hai. Abhi koi dividers nahi hain — machine poora kaam ek hi baar mein karta hai, phir next plank tab start karta hai jab pehla poori tarah exit ho jaata hai.

Agar hum instructions ek-ek karke is un-split machine se guzarein, to har $T_{0}$ seconds mein ek result aata hai. Woh rate — ek per $T_{0}$ — woh baseline hai jise hum beat karna chahte hain.

Step 2 — Plank kaatna: "stage" aur "register" kya hote hain

KYA HAI. Ab hum plank ko dividers se $k$ equal pieces mein kaatate hain. Har piece ek stage hai. $k$ stages ko pipeline karne ke liye aap har do neighbouring pair ke beech ek divider insert karte ho — yeh hain $k - 1$ pipeline registers (ek design jo bahut inputs aur outputs bhi latch karta hai woh $k + 1$ use karta hai; count $k$ ke saath badta hi hai). Har divider clock ke tick par partial result ko latch (freeze aur remember) karta hai.

YEH KYUN KARTE HAIN. Agar chaar workers mein se har ek plank ka ek quarter rakhta hai, to kisi bhi instant par chaar planks machine mein hote hain ek saath — ek per worker. Woh overlap hi pipelining ka poora point hai. Lekin overlap tabhi kaam karta hai jab workers ke beech ek gate ho taaki plank #2 plank #1 ke leftovers se crash na kare. Woh gate hi register hai — aur note karo yeh tab hi appear hota hai jab aapke paas do stages hon alag karne ke liye. $k = 1$ par kuch bhi divide nahi hai, isliye koi registers nahi hain aur koi toll nahi hai.

PICTURE. Single amber bar ab $k$ white segments hai jo cyan divider-gates se alag hain. Har cyan gate thoda sa time $t_{reg}$ cost karta hai — ek value ko freeze karke hand off karna free nahi hota.

Step 3 — Clock sirf utni fast tick kar sakti hai jitna sabse slow slice allow kare

KYA HAI. Agar plank ko $k$ equal pieces mein kaata jaaye, to logic ka har piece $τ = T_{0} / k$ leta hai. Lekin har piece ( $k \geq 2$ ke liye) ek gate ke peeche bhi baitha hai, isliye ek stage ko jo real time chahiye woh hai:

ek clock tick T_{cycle} = sabse slow slice mein logic τ + gate ka fixed toll t_{reg}

YEH PLUS KYUN, AUR SLOWEST KYUN. Clock poori machine ke liye ek single drumbeat hai — har gate same beat par latch karta hai. Isliye drum sirf utni fast beat kar sakta hai jitna sabse loaded worker finish karke hand off kar sake. Us worker ko apna logic karne aur apne gate se guzarne mein time lagta hai: isliye $τ + t_{reg}$ . Clock period $T_{cycle}$ exactly yehi hai.

PICTURE. Figure ek stage mein zoom karta hai: ek white logic block of width $τ$ , uske baad immediately cyan gate of width $t_{reg}$ . Dono ko span karne wala dashed amber bracket clock period hai. Note karo ki toll $t_{reg}$ har stage mein same width ka hai — jab aap thinner slice karte ho tab bhi yeh shrink nahi hota.

Frequency sirf beats-per-second hai: $f = 1/ T_{cycle}$ . Zyada stages $\Rightarrow$ chhota $T_{0} / k$ $\Rightarrow$ chhota period $\Rightarrow$ zyada $f$ . Yahi deep pipelining ka promise hai.

Step 4 — Jahan promise marta hai: toll jeet jaata hai

KYA HAI. Dekho $T_{cycle} (k) = T_{0} / k + t_{reg}$ ( $k \geq 2$ branch) $k$ badhne par kya karta hai.

YEH CRUX KYUN HAI. Shrinking term $T_{0} / k$ zero ki taraf daudti hai, lekin toll $t_{reg}$ wahan baitha rehta hai. Add karo to cycle time $t_{reg}$ ke floor par flatten ho jaati hai. Ek baar floor ke paas pahunchne ke baad, stages add karne par real registers (area, power) cost hote hain aur almost koi speed nahi milti.

PICTURE. Blue curve $k \geq 2$ ke liye $T_{cycle} (k)$ hai; akela amber dot register-free $k = 1$ point $T_{0}$ par mark karta hai. Curve pehle zyada girta hai — 2→5 stages se bade gains — phir bend karke ek horizontal amber dashed line, floor $t_{reg}$ , ke paas aa jaata hai. Curve aur floor ke beech ka gap woh akela speed hai jo aapke paas gain karne ke liye bachi hai. Knee ke baad, woh gap almost kuch bhi nahi.

Ab ideal speedup (abhi bhi koi stalls nahi maan ke). Un-pipelined har $T_{0}$ mein ek instruction karta hai; pipelined har $T_{cycle}$ mein ek stream karta hai, isliye:

Speedup (k) = \frac{T _{0}}{T _{cycle} ( k )} = \frac{T _{0}}{\frac{T _{0}}{k} + t _{reg}} k \to \infty \frac{T _{0}}{t _{reg}}

Numerator $T_{0}$ — baseline job time jo hum beat kar rahe hain
Denominator — streaming period; $k \to \infty$ par yeh $t_{reg}$ tak collapse ho jaata hai
Limit $T_{0} / t_{reg}$ — ek hard ceiling jo purely register overhead se set hoti hai

Toh even infinite stages aur zero hazards ke saath, speedup capped hai. Yehi register wall hai.

Recall

$k = 1$ par speedup formula kyun blow up nahi karta? $k = 1$ par $T_{cycle}$ kya equal hota hai, aur kyun? ::: Exactly $T_{0}$ — koi registers nahi hain, isliye koi $t_{reg}$ toll nahi; speedup $1 \times$ hai jaisa expect tha.

Step 5 — Doosra tax: galat guess pipe ko resolve stage tak flush kar deta hai

KYA HAI. Real code branches leta hai ("agar yeh, to wahan jaao"). Processor pipe full rakhne ke liye branch outcome guess karta hai (dekho Branch Prediction). Galat guess ka matlab hai ki branch ke baad shuru ki gayi har instruction — jab tak branch ka answer nahin aata — garbage hai aur throw away karni padti hai — flush.

DEPTH ISSE WORSE KYUN BANATA HAI. Branch ki true direction tab hi known hoti hai jab woh us stage tak pahunche jo use resolve karta hai — us stage number ko $b$ kaho. Branch ke baad aur resolve hone se pehle jo fetch kiya gaya (roughly $b - 1$ instructions) woh wrong-path kaam hai. Isliye flush penalty actually $b - 1$ hai, na ki full $k - 1$ .

Do honest cases:

Naive / late resolve: agar branch sirf end mein resolve hota hai, $b \approx k$ aur penalty $\approx k - 1$ — worst case, aur jo log darane ke liye quote karte hain.
Real designs: branch ko ek fixed, early stage par resolve karo (ek dedicated branch unit), to $b$ roughly constant rahta hai aur penalty $k$ ke saath one-for-one scale nahi karti. Deeper pipes tab bhi hurt karti hain (fetch-to-resolve distance depth ke saath thodi badhti hai), lekin sub-linearly, lock-step nahi.

PICTURE. Do side-by-side pipe diagrams. Top: ek short pipe — red X branch mark karta hai, shaded bubbles resolve stage tak flush ho jaate hain. Bottom: ek deeper pipe — same red X; agar resolve late hai to crater huge hai ( $k - 1$ ), agar resolve early pin kiya hai to sirf $b - 1$ bubbles flush hote hain. Same galti, penalty set hoti hai jahan aap resolve karo, raw depth se nahi.

Step 6 — Data aur structural hazards: stalls jo bhi badhte hain (lekin gently)

KYA HAI. Control flushes akela tax nahi hain. Do aur:

Data hazards — ek instruction ko ek result chahiye jo usse pehle wali ne abhi produce nahi kiya ("read-after-write" dependence). Deeper pipes producer ke result ko cycles mein aur door push karte hain, isliye forwarding paths lambe ho jaate hain aur kuch stalls appear hote hain. Dekho Pipeline Hazards.
Structural hazards — do instructions same hardware (ek memory port, ek ALU) same cycle mein chahti hain; ek ko wait karna padta hai.

INHE ACKNOWLEDGE KYUN KARNA HAI. Yeh do depth ke saath badhte hain, lekin sub-linearly: forwarding networks zyaadatar data hazards absorb kar lete hain, aur contended units duplicate karne se zyaadatar structural ones remove ho jaate hain. Yeh flush penalty ki tarah rarely scale karte hain, lekin real hain aur optimal depth neeche push karte hain.

PICTURE. CPI budget ka stacked bar: ideal $1$ , control flushes ke liye ek growing amber slab (Step 5), aur data aur structural stalls ke liye do thinner, slowly-growing cyan slabs jo flatten out ho jaate hain jab forwarding aur duplication kick in karti hai.

Step 7 — Fill aur drain: ek finite pipe kabhi fully streaming nahi hoti

KYA HAI. Step 4 ki speedup ek infinite stream assume karti thi — ek result har tick, hamesha ke liye. Ek real program $N$ instructions ek $k$ -stage pipe se run karta hai. Pehla result tab tak nahi aata jab tak pipe fill na ho jaaye ( $k$ ticks pehli instruction ko poori tarah se push karne ke liye), aur end ke paas pipe drain hoti hai jab last instructions exit karti hain aur unke peeche koi nai nahi hoti.

YEH KYUN MATTER KARTA HAI. Woh startup/wind-down ticks pure overhead hain jo poore run pe amortise nahi hote. Short bursts ke liye (ya har flush ke baad, jo pipe empty aur refill karta hai) yeh zyada affect karte hain — aur deeper pipes ka fill/drain zyada lamba hota hai.

PICTURE. Ek timing chart: $k - 1$ idle-ish ticks ka amber "fill" ramp steady state se pehle, ek lamba white steady-state band of one-per-tick, phir end mein $k - 1$ ticks ka amber "drain" ramp. Pipe jitni deeper, dono amber ramps utne wide.

Step 8 — Imbalance: real clock worst stage set karta hai

KYA HAI. Ab tak sab kuch assume karta tha ki logic perfectly equal pieces $τ = T_{0} / k$ mein split hoti hai. Yeh nahi hoti. Kuch operations atomic hote hain (ek cache lookup, ek TLB hit — aap beech mein rok nahi sakte), isliye real stage delays $T_{1}, T_{2}, \dots, T_{k}$ uneven hoti hain.

YEH KYUN MATTER KARTA HAI. Clock ek drumbeat hai, isliye use slowest stage ka wait karna padta hai. Yeh honest cycle time deta hai:

T_{cycle} = i max (T_{i}) + t_{reg}

$T_{i}$ — stage $i$ ki logic delay (zaruri nahi $T_{0} / k$ )
$max_{i} (T_{i})$ — sabse lamba stage; woh akela clock set karta hai, har chhote stage mein slack waste karta hai
$t_{reg}$ — same register toll jaisa pehle tha

Ideal even split mein $max_{i} (T_{i}) = T_{0} / k$ aur hum Step 3 recover karte hain. Reality mein $max_{i} (T_{i}) > T_{0} / k$ , isliye real clock hamesha even-split dream se slower hota hai — aur deeper pipes, thinner slicing karte hue, perfect balance ko mushkil banate hain, gap wider karte hain.

PICTURE. Left panel — imbalance: real stages ki jagged lengths hain; sabse tall bar (amber) clock set karta hai, aur sab chhote stages hatched difference waste karte hain. Right panel — power: $P = C V^{2} f$ , aur zyada stages matlab zyada registers clock karne ke liye; clock network akele Pentium 4 ki 30–40% power burn karta tha. Voltage ko frequency ke against kaise trade kiya jaata hai yeh jaanne ke liye Dynamic Voltage and Frequency Scaling (DVFS) dekho.

Step 9 — Tug-of-war aur real verdict

KYA HAI. Real performance throughput hai = useful instructions per second, upar ke har effect ko combine karke:

Throughput = \frac{f}{CPI} = \frac{1}{( max _{i} ( T _{i} ) + t _{reg} ) \cdot CPI ( k )}

DONO TERMS FIGHT KYUN KARTE HAIN. $k$ badhane se $f$ upar jaata hai (Step 3) lekin CPI bhi upar jaati hai (Steps 5–6) aur fill/drain aur imbalance frequency win ko chip karte hain (Steps 7–8). Throughput unka ratio hai, isliye woh tab tak hi badhta hai jab tak frequency win losses se aage rahe — phir ek optimal depth (likha jaata hai $k_{opt}$ ) par peak karta hai aur girta hai.

PICTURE. $k$ ke upar teen curves: cyan $f (k)$ badhta hua, amber $CPI (k)$ badhta hua, aur white throughput curve $f / CPI$ jo badhti hai, peak par round off hoti hai, phir droop karti hai. Ek vertical dashed line sweet spot $k_{opt} \approx 10 - 15$ mark karta hai.

Ek-picture summary

Upar sab kuch ek single frame mein: shrinking logic slice register floor build karti hai, flush penalty resolve stage se set hoti hai, data/structural stalls aur fill/drain overhead, imbalance real clock utha deta hai, aur throughput hill $k_{opt}$ tak badhti hai phir wall mein roll off ho jaati hai.

Recall Ise Feynman ki tarah retell karo (plain words, no symbols)

Ek assembly line imagine karo. Ise zyada workstations mein kaato aur har worker apna bit jaldi finish karta hai, isliye conveyor belt faster chal sakta hai — yeh zyada clock speed hai. Lekin har workstation ko ek chota sa gate chahiye jo part agle worker ko hand kare, aur woh gate ek fixed sliver of time leta hai chahe kaam kitna bhi tiny ho. Itna thin slice karo aur gates hi sab kuch hain jo tum pay kar rahe ho — belt aur fast nahi ja sakta. Yehi floor hai. (Aur sabse pehli machine, ek worker jo poora part karta hai, ka koi gate hi nahi hai — koi toll nahi.)

Aur bura: jab bhi line galat guess karti hai ki part kidhar route karna hai, woh belt par jo bhi hai use scraps kar deti hai us point tak jahan guess check kiya jaata hai — isliye checkpoint early rakho aur kam scrapping hogi. Uske upar, workers kabhi kabhi ek part ka wait karte hain jo pichle worker ne abhi finish nahi kiya (data), ya ek shared tool ke liye ladte hain (structural), aur har baar belt empty hone par refill hone mein time lagta hai. Yeh sab add karo aur das-se-pandrah stations ke baad line ek saath slower aur hotter ho jaati hai. Pentium 4 ne ek monster 31-station line banai, use blazing fast chalaya, aur end se kuch extra nahi nikla jabki bahut zyada power burn hui. Phir Intel ne ek chhoti, smarter line banai. Woh poora rise-then-fall hi deep-pipeline wall hai.

Recall Quick self-check

$T_{cycle} = T_{0} / k + t_{reg}$ mein kaunsa term speed floor create karta hai? ::: Fixed register toll $t_{reg}$ — yeh $k$ badhne par kabhi shrink nahi hota. $k = 1$ par $t_{reg}$ absent kyun hai? ::: Jab pipe split nahi hoti to koi pipeline registers nahi hote, isliye koi toll pay karna nahi hai. Ek misprediction honestly kitni instructions flush karta hai? ::: Roughly $b - 1$ , jahan $b$ woh stage hai jo branch resolve karta hai — sirf worst case mein $k - 1$ hota hai jab resolve bilkul end mein hota hai. Control flushes ke alawa do stall sources batao. ::: Data hazards (ek not-yet-produced result ka wait karna) aur structural hazards (shared hardware ke liye contention). Ek finite run ideal speedup kyun nahi pahunchta? ::: Fill aur drain $k - 1$ ticks cost karti hain jo amortise nahi hoti, aur har flush pipe empty aur refill karta hai. Stages uneven hone par real clock period kya set karta hai? ::: Sabse slow stage: $T_{cycle} = max_{i} (T_{i}) + t_{reg}$ . Prescott example mein net performance $\times 1.0$ kyun tha? ::: Frequency $\times 1.5$ badhi lekin CPI bhi $\times 1.5$ badhi, isliye $f / CPI$ flat raha.