Pipeline throughput and CPI: Visual walkthrough — Hinglish deep dive

5.2.9 · D2 · Hardware › Processor Datapath & Pipelining › Pipeline throughput and CPI

Yeh page parent result — Pipeline throughput and CPI — ko bilkul scratch se rebuild karta hai. Koi formula tab tak nahi aata jab tak aapne use ek picture ki tarah dekha na ho. End tak aap poori story ek napkin par draw kar paoge.

Hum poore page ek hi sawaal ka jawab de rahe hain:

Step 1 — "Stage" kya hota hai? Assembly line draw karo

KYA HAI. Ek instruction karne wala processor ko kaafi chote-chote kaam ek order mein karne padte hain: instruction fetch karo, decode karo, arithmetic karo, memory access karo, answer wapas write karo. Hum us kaam ko boxes mein kaatte hain jise stages kehte hain. Classic count hai $k = 5$ stages jinka naam hai IF, ID, EX, MEM, WB.

BOXES KYO? Kyunki agar har box ka apna khud ka hardware ho, toh jab box 2 instruction #1 par kaam kar raha ho, box 1 pehle se instruction #2 start kar sakta hai. Koi idle nahi baithta. Woh overlap hi poora point hai — aur jab tak hum boxes nahi dekh sakte, tab tak cycles ke baare mein soch bhi nahi sakte.

PICTURE. Paanch labelled boxes ek row mein, ek instruction left se enter karti hai aur finished result right se nikalti hai.

Step 2 — Clock SABSE SLOW box ki speed par kyun tick karta hai

KYA HAI. Har box apna result agle box ko usi shared heartbeat par deta hai — clock. Ek tick = ek clock cycle. Ab hum dekhte hain ki ek tick kitni lambi honi chahiye.

MAXIMUM KYO, average nahi? Saare boxes ek saath aage badhte hain, same edge par. Agar clock tab tick kare jab slow box abhi khatam nahi hua, toh woh box garbage pass kar deta hai. Isliye tick ko slow box ka wait karna padega. Ek marching band ka picture lo: sab ek hi beat par step karte hain, isliye beat itni slow honi chahiye ki sabse slow marcher bhi chal sake.

PICTURE. Paanch stage delays alag-alag height ke bars ki tarah draw kiye; ek horizontal dashed line sabse unche bar ke upar baithi hai — woh height hi clock period hai.

$max$ naam ka tool yahan kyun aata hai, average nahi? Kyunki hume worst box ke liye safe rehna hai, aur sirf worst wala matter karta hai. $max$ exactly woh operation hai jo "mujhe inme se sabse bada do" karta hai — sahi sawaal hai "kaun sabse slow hai?", aur $max$ uska jawab deta hai.

Step 3 — Pipeline FILL hote dekho: pehli instructions slow hoti hain

KYA HAI. Instruction $I_{1}$ bhejo. Tick 1 par woh IF box mein hai. Tick 2 par woh ID mein move hoti hai aur $I_{2}$ IF mein enter karti hai. Aur aise hi aage. Hum diagonal wave ko sweep karte dekhte hain.

YEH KYUN DEKHO? Kyunki bilkul start mein pipeline half-empty hoti hai — har box busy nahi hota. Woh early ticks "fill-up" cost hain, aur "ek instruction per tick" claim karne se pehle hume unhe honestly count karna hoga.

PICTURE. Standard pipeline space-time chart: rows = instructions, columns = clock cycles, har cell us stage ke colour se bhari jisme woh hai. Staircase fill dikhata hai.

Chart padho: $I_{1}$ cycle 5 ke end par khatam hoti hai (WB chodti hai) — usse $k = 5$ saare ticks chahiye the. Lekin $I_{2}$ ek tick baad khatam hoti hai, cycle 6 par. $I_{3}$ cycle 7 par. Staircase ban jaane ke baad, har single tick mein ek instruction pop out hoti hai.

Step 4 — $n$ instructions ke liye total ticks count karo

KYA HAI. $k$ -stage pipeline se $n$ instructions run karne ke liye needed ticks add karo.

KYO. Total cycles ÷ instructions hi CPI hai, by definition. Isliye agar hum total cycles count kar sakein, toh kaam ho gaya.

PICTURE. Wohi chart do coloured zones mein split: teal fill triangle (pehli instruction $k$ stages cross karti hai) aur orange steady zone (uske baad ek completion per tick).

Picture se count karo:

$Total Cycles = ticks for I_{1} to cross all boxes k + one extra tick for each of the other n - 1 (n - 1)$

$k$ — fill cost, ek baar pay hoti hai, chahe kitni bhi instructions hon.
$(n - 1)$ — pipe full hone ke baad, har baaki instruction exactly ek tick add karti hai.

Step 5 — Divide karo, phir $n$ badhao: CPI 1 ki taraf jata hai

KYA HAI. "Total cycles" ko $n$ se divide karke "cycles per instruction" banao.

KYO DIVIDE? Kyunki CPI define hi hota hai total cycles over instructions se. Yeh step literally Step 4 ki count par definition apply karna hai.

$CPI_{ideal} = \frac{Total Cycles}{n} = \frac{k + ( n - 1 )}{n} = 1 + \frac{k - 1}{n}$

$1$ — steady-state cost: full hone ke baad ek tick per instruction.
$\frac{k - 1}{n}$ — fill cost thinly spread saari $n$ instructions par.

LIMIT YAHAN KYO AATI HAI? Hum pooch rahe hain "ek lambe program ke liye fill penalty ka kya hoga?" Penalty $\frac{k - 1}{n}$ jaise $n$ badhta hai shrink hoti hai — woh shrinking-toward-a-value exactly wahi hai jo ek limit describe karta hai. "Huge $n$ ke liye yeh kahaan settle hoga?" ka sahi tool hai limit $n \to \infty$ .

$lim_{n \to \infty} (1 + \frac{k - 1}{n}) = 1 ⟹ CPI_{ideal} = 1$

PICTURE. CPI versus $n$ ka ek curve, upar se start (chote programs fill feel karte hain), neeche slide karta hua aur dashed line $CPI = 1$ ko hug karta hua.

Step 6 — Degenerate case: agar $n = 1$ ho?

KYA HAI. Ek single instruction run karo, $n = 1$ .

YEH KYO DIKHAO? Ek contract ko har input cover karna chahiye, including sabse chota. Yeh ek famous misconception bhi kill karta hai.

$CPI = \frac{k + ( 1 - 1 )}{1} = \frac{k}{1} = k$

Ek instruction ko $k$ ticks cost hoti hai — wohi $k$ boxes jinhe use cross karna hai. Pipelining ne use zero help di. Yeh visual proof hai ki pipelining ek instruction ko faster nahi banata (uski latency unchanged rehti hai); yeh sirf completions zyada frequent karta hai jab kaafi instructions in flight hoon.

PICTURE. Left: ek akela instruction 5 ticks mein 5 boxes cross karta hua (latency $= k$ ). Right: ek dense stream jahan har tick ek pop out hota hai (throughput $= 1/ T_{p i p e}$ ). Same boxes, bilkul alag feeling.

Dekho 5.1.05-CPU-performancemetrics jahan latency aur throughput poori performance equation ke andar kahan baithte hain.

Step 7 — Reality bite karti hai: hazards ideal ke upar extra ticks add karte hain

KYA HAI. Real streams hazards se takraati hain — woh moments jab ek instruction ko wait karna padta hai. Pipeline ek bubble (ek do-nothing NOP) insert karti hai, jo ek wasted tick hai. Har wasted tick CPI mein add hoti hai.

ADD KYO, MULTIPLY NAHI? Kyunki ek stall literally extra cycles hain jo ideal count par chipke hain. Extra cycles per instruction simply baseline 1 mein add hote hain.

$CPI_{actual} = ideal, Step 5 1 + wasted ticks, averaged Stalls per Instruction$

Stall term khud independent troublemakers ka sum hai:

$Stalls/Instr = data hazards (f_{D} \cdot s_{D}) + branch mispredicts (f_{B} \cdot m_{B} \cdot p_{B})$

$f_{D}$ — fraction of instructions jo data hazard hit karti hain (5.2.03-Data-hazards).
$s_{D}$ — average bubbles jo har aisi hazard cost karti hai (forwarding se kam hoti hai).
$f_{B}$ — fraction jo branches hain; $m_{B}$ — unme se fraction jo mispredict karti hain; $p_{B}$ — penalty ticks per mispredict (5.2.05-Control-hazards).

PICTURE. Ek bar height 1 se start (ideal), teal segment data stalls ke liye aur orange segment branch stalls ke liye upar stacked — total height $CPI_{actual}$ hai.

Ek-picture summary

Upar sab kuch, compressed: boxes → slowest box tick set karta hai → fill triangle → $k + (n - 1)$ count karo → divide karo → limit 1 tak pahunchti hai → hazards extra ticks upar stack karte hain.

Recall Feynman retelling — plain words mein wapas bolo

Ek car factory imagine karo jisme paanch stations hain. Ek akeli car phir bhi paanch station-times mein bankar nikti hai — pipelining ne ek car kabhi rush nahi kiya. Lekin jab line full ho jaati hai, har single beat par ek finished car roll out hoti hai. Real cost per car nikalne ke liye, main saare beats count karta hoon aur cars ki ginti se divide karta hoon: maine line ek baar fill karne ke liye paanch beats diye, aur pehli car ke baad har car ke liye ek beat, toh total beats $= k + (n - 1)$ . $n$ se divide karo aur "line ek baar fill karo" ki cost jitni zyada cars banaoge utni thin hoti jaati hai — ek bade batch ke liye woh vanish ho jaati hai aur har car ek beat cost karti hai: CPI = 1. Lekin factory kabhi kabhi jam hoti hai: ek station pehle wale ka result wait karta hai (data hazard) ya line ne galat turn guess kar li (branch mispredict), aur har jam ek wasted beat hai jo us clean 1 par chipki hai. Isliye honest number hai $1$ aur upar saare average wasted beats — isliye real CPI 1 se thoda upar rehta hai, aur sirf ek fancier multi-line factory (superscalar) use 1 se neeche push kar sakti hai.

Recall Quick self-check

$k$ -stage pipe mein $n$ instructions ke liye total cycles ::: $k + (n - 1)$ Clock period stage delays ka $max$ kyun use karta hai ::: saare stages ek saath tick karte hain, isliye slowest wala sabko gate karta hai Ek single instruction ( $n = 1$ ) ke liye CPI ::: $k$ — pipelining ek akele instruction ko koi help nahi deta Har stall CPI mein kya add karta hai, aur hum add kyun karte hain ::: wasted (bubble) cycles per instruction; woh extra ticks hain jo ideal 1 par chipke hain $f_{B} = 0.25, m_{B} = 0.10, p_{B} = 3, f_{D} = 0.15, s_{D} = 2$ hone par CPI ::: $1.375$

Parent: Pipeline throughput and CPI · Related: 5.2.03-Data-hazards · 5.2.05-Control-hazards · 5.2.07-Forwarding-and-bypassing · 5.3.02-Superscalar-architecture · 5.1.05-CPU-performancemetrics