Pipeline throughput and CPI: Exercises — Hinglish deep dive

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

Yeh page ek ladder hai. Har rung pichle se harder hai. Problem ko pehle khud try karo, uske baad solution kholo — collapsible callout answer tab tak hide karta hai jab tak tum click nahi karte. Yahan sab kuch Pipeline throughput and CPI pe based hai; agar koi symbol unfamiliar lage, toh parent note ne usse define kiya hai, aur yeh page usse use karta hai.

Shuru karne se pehle, un chaar symbols ko dobara anchor karte hain jinpe hum sabse zyada rely karenge, taaki koi bhi symbol bina wajah use na ho.

Definition Chaar symbols jo hum baar baar reuse karenge

$T$ — the clock period: ek tick ki length, seconds (ya picoseconds, ps) mein. Ek tick = $1 0^{- 12} s$ agar $T = 1$ ps ho.
$t_{r e g}$ — the pipeline-register overhead: woh extra time jo har tick mein include hona chahiye taaki do stages ke beech ka chhota storage register pichle stage ka result safely latch kar sake (setup time + clock-to-Q). Yeh ek baar per tick charge hota hai, slowest stage ke upar, kyunki register data tabhi capture kar sakta hai jab stage ne apna computation finish kar liya ho. Typical values 15–50 ps hoti hain.
$CPI$ — cycles per instruction: use hue total ticks $\div$ finish hue instructions. Ideal pipeline target = $1$ .
$Throughput$ — finished instructions per second $= \frac{1}{CPI \times T} = \frac{clock rate}{CPI}$ , kyunki clock rate $= 1/ T$ .

Toh master clock-period rule jo hum baar baar invoke karenge woh hai: $T_{p i p e} = max (t_{1}, t_{2}, \dots, t_{k}) + t_{r e g} .$

Figure 1 (niche) is poore page ka mental model hai. Pehle uska legend padho:

Level 1 — Recognition

Goal: ek definition padho aur ek number plug in karo.

Recall Solution L1.1

KYA karna hai: slowest stage dhundho, phir register overhead add karo. KYUN: har stage usi same edge pe clock karta hai, isliye tick itni lambi honi chahiye ki worst stage finish ho sake aur uska output register latch ho sake. $max (90, 60, 110, 100, 70) = 110 ps (EX bottleneck hai)$ $T_{p i p e} = 110 + 20 = 130 ps$

Recall Solution L1.2

KYA: throughput $= 1/ (CPI \times T)$ . KYUN: $CPI = 1$ ke saath, har tick mein ek instruction exit karti hai, aur ek tick $T$ seconds ka hota hai. $Throughput = \frac{1}{1 \times 130 \times 1 0 ^{- 12}} = 7.69 \times 1 0^{9} instr/s \approx 7.69 billion/s$

Recall Solution L1.3

KYA: CPI = total cycles $\div$ instructions. KYUN: CPI ek per-instruction average hai, isliye hum poore bill ko count se divide karte hain. $CPI = \frac{520}{400} = 1.30$

Level 2 — Application

Goal: do ya teen formulas ko chain karo.

Recall Solution L2.1

KYA: speedup = (time per instruction, single) $\div$ (time per instruction, pipe). KYUN: ideal CPI steady state mein dono ke liye $1$ hai, isliye per-instruction comparison mein ratio sirf clock periods ka ratio hai. $T_{s in g l e} = 90 + 60 + 110 + 100 + 70 = 430 ps$ $Speedup = \frac{430}{130} = 3.31 \times$ $5 \times$ nahi — kyunki EX ek bottleneck hai (unbalanced stages) aur hum har tick $t_{r e g}$ pay karte hain.

Recall Solution L2.2

KYA: har stall source ka expected cost ideal CPI of 1 pe add karo. KYUN: expected stalls = (fraction of instructions affected) $\times$ (penalty each). Independent sources add hote hain. $Branch stalls = 0.20 \times 0.10 \times 4 = 0.08$ $Data stalls = 0.30 \times 1 = 0.30$ $CPI = 1 + 0.08 + 0.30 = 1.38$

Recall Solution L2.3

KYA: throughput = clock rate / CPI. KYUN: clock rate ticks per second hai; cycles-per-instruction se divide karne par ticks finished instructions mein convert hoti hain. $Throughput = \frac{2.5 \times 1 0 ^{9}}{1.38} = 1.812 \times 1 0^{9} \approx 1.81 billion instr/s$

Level 3 — Analysis

Goal: designs compare karo, reason karo "kaun better hai aur kyun."

Figure 2 dikhata hai ki "split the bottleneck" move clock ke saath exactly kya karta hai: lamba EX bar aadha ho jaata hai, aur ceiling (dashed red line = clock period) gir jaati hai jahan tak agle sabse uncha bar pahunchta hai.

Recall Solution L3.1

(a) Naya clock period. KYA: EX ab do 55-ps stages ho gaya hai, toh $max (stage delays) + t_{r e g}$ dobara run karo. KYUN: clock hamesha ek sabse bure stage se set hoti hai; jab EX (110) chala jaata hai, toh naya worst stage MEM hai 100 ps pe (Figure 2 mein nayi red ceiling dekho). $T_{n e w} = max (90, 60, 55, 55, 100, 70) + 20 = 100 + 20 = 120 ps$ Purana $T = 110 + 20 = 130$ ps tha. (b) Naya CPI. KYA: deeper pipe jo extra stall introduce karti hai usse purane CPI 1.20 pe add karo. KYUN: CPI $= 1 + stalls/instr$ ; purane 0.20 data-hazard stalls rehte hain, aur lambi forwarding distance 0.05 aur badhati hai, isliye stall term 0.20 se badh ke 0.25 ho jaata hai. $CPI_{n e w} = 1.20 + 0.05 = 1.25$ (c) Throughput ratio. KYA: dono throughputs ka ratio banao, har ek $= 1/ (CPI \times T)$ hai. KYUN sirf CPI se compare nahi karte: time per instruction $CPI \times T$ hai — dono factors yahaan badle (CPI badha, $T$ gira), isliye sirf CPI se judge karna galat taur pe kaheha ki naya design worse hai. Sirf product hi real speed capture karta hai. $\frac{new}{old} = \frac{1/ ( 1.25 \times 120 )}{1/ ( 1.20 \times 130 )} = \frac{1.20 \times 130}{1.25 \times 120} = \frac{156}{150} = 1.04 \times$ Verdict: ek namoonaai 4% gain. KYUN itna kam? EX split karne se bottleneck sirf MEM pe shift hua — clock barely giri (130→120), aur extra stall ne us fayade ka kuch hissa kha liya. Yeh pipelines ko deeper karne ka law of diminishing returns hai. Compare karo 5.3.02-Superscalar-architecture se, jo $T$ ki jagah CPI pe attack karta hai.

Recall Solution L3.2

Forwarding se pehle: $CPI_{b e f or e} = 1 + 0.35 \times 2 = 1.70$ Forwarding ke baad: sirf load-use subset stall karta hai, 1 cycle pe. $load-use fraction = 0.35 \times 0.20 = 0.07$ $CPI_{a f t er} = 1 + 0.07 \times 1 = 1.07$ Improvement: $1.70 - 1.07 = 0.63$ cycles/instr saved. Dekho 5.2.07-Forwarding-and-bypassing un bypass wires ke liye jo 0-cycle path ko physical banate hain, aur 5.2.03-Data-hazards yeh jaanne ke liye ki load-use ko fully forward kyun nahi kiya ja sakta (data MEM tak ready nahi hota).

Level 4 — Synthesis

Goal: kaafi saari moving parts combine karo aur ek target ki taraf design karo.

Recall Solution L4.1

(a) Max CPI. KYA: throughput = clock/CPI ko invert karo taaki CPI = clock/throughput solve ho sake. KYUN: throughput is baat se set hota hai ki har second mein kitne finished instructions milte hain; target aur clock fix karne ke baad sirf CPI unknown rehta hai. $CPI_{ma x} = \frac{3.0 \times 1 0 ^{9}}{3.0 \times 1 0 ^{9}} = 1.00$ Yeh kisi bhi stall ke saath impossible hai — ek ideal pipeline already CPI 1 pe baith jaati hai aur yeh hazards use usse upar push karte hain. Toh jaise stated hai target sirf prediction se meet nahi ho sakta; dekho hum kitne close hain aur kya chahiye. (b) Mispredict rate $m$ solve karo. KYA: CPI ko $1 + branch stalls (m) + data stalls$ likho, required 1.00 ke barabar set karo, aur $m$ solve karo. KYUN: sirf $m$ adjustable hai; equation ko target pe force karna exactly woh $m$ batata hai jo target demand karta hai. $1 + branch 0.25 \cdot m \cdot 3 + data 0.30 \cdot 2 = 1.00$ $0.75 m + 0.60 = 0.00 \Rightarrow m = - 0.80$ Ek negative mispredict rate impossible hai. Conclusion: akela 0.60 data-stall term hi CPI $\geq 1.60$ force kar deta hai, toh is clock pe 3 Ginstr/s unreachable hai. Design ko data stalls pe attack karna chahiye (forwarding) — branches pe nahi. Full forwarding ke saath dobara karo (data stalls → 0): $1 + 0.25 \cdot m \cdot 3 = 1.00 \Rightarrow m = 0,$ yaani tab bhi tumhe perfect prediction chahiye. Practically clock raise karna padega. Exactly yahi dead-end designers ko 5.3.02-Superscalar-architecture ki taraf push karta hai (CPI below 1).

Recall Solution L4.2

KYA: har choice ke liye, us stall term ko current CPI se minus karo, phir throughputs compare karo. KYUN: ek stall category eliminate karna CPI sum se exactly uska contribution remove karta hai; clock fixed hone par throughput $\propto 1/ CPI$ hai, toh throughput ratio simply $CPI_{o l d} / CPI_{n e w}$ hai. Option A — branch stalls khatam karo: naya CPI $= 1.50 - 0.20 = 1.30$ . Option B — data stalls khatam karo: naya CPI $= 1.50 - 0.30 = 1.20$ . Current se throughput ratio (clock fixed) $= CPI_{o l d} / CPI_{n e w}$ : $A: \frac{1.50}{1.30} = 1.154, B: \frac{1.50}{1.20} = 1.250$ Data stalls khatam karo (Option B): $25%$ throughput gain $15.4%$ ke mukable. KYUN: bada stall term (0.30) bada lever hai — jo dominate karta hai usse speed up karo. Yeh Amdahl's Law disguise mein hai.

Level 5 — Mastery

Goal: limits ke baare mein reason karo, degenerate cases, aur jahan simple model toot jaata hai.

Problems se pehle, hum fill-and-drain picture explicit karte hain, kyunki har Level-5 answer isi pe lean karta hai.

Figure 3 yeh literally dikhata hai: har column mein red exit-boxes ki count 0 se start hoti hai (pipe filling), 1 pe rise karti hai (full), aur busy boxes ki count wapas taper ho jaati hai jab last instructions drain hoti hain.

Recall Solution L5.1

(a) Exact CPI. KYA: total cycles ko instruction count se divide karo. KYUN: CPI by definition total-cycles-per-instruction hai; hum sirf approximating ki jagah exact fill-and-drain count carry karte hain. $CPI (n) = \frac{total cycles}{instructions} = \frac{k + n - 1}{n} = 1 + \frac{k - 1}{n} .$ Term $\frac{k - 1}{n}$ fill-and-drain tax hai: $k - 1$ "wasted" edge cycles, sab $n$ instructions pe amortise ki gayi. Bada pipe (large $k$ ) ya short program (small $n$ ) → bada tax. (b) $k = 5$ ke liye values (toh $k - 1 = 4$ ). $n = 1 : 1 + \frac{4}{1} = 5.00, n = 5 : 1 + \frac{4}{5} = 1.80,$ $n = 100 : 1 + \frac{4}{100} = 1.04, n \to \infty : 1 + \frac{4}{n} \to 1.$ (c) 1 ke 5% ke andar. KYA: tax term $\leq 0.05$ demand karo aur $n$ solve karo. KYUN: "5% ke andar" matlab CPI $\leq 1.05$ hai, yaani extra $\frac{k - 1}{n}$ 0.05 se zyada nahi hona chahiye. $\frac{k - 1}{n} \leq 0.05 \Rightarrow n \geq \frac{4}{0.05} = 80 \Rightarrow n \geq 80 .$ (d) Do edge cases, physically.

$n = 1$ (single instruction, $n < k$ ): pipe kabhi fill nahi hoti. Woh ek instruction sab 5 stages se akele chalti hai; baaki 4 stages har cycle idle baithte hain. CPI $= 5 = k$ — tumhe zero pipelining benefit milta hai, exactly wahi jaisa single-cycle machine ki latency hai. Yeh degenerate "short program" limit hai: pipe depth se chota program har instruction ke liye almost full latency pay karta hai.
$n = k = 5$ : pipe bahut mushkil se fill hoti hai, bilkul last instruction ke enter karne par, phir immediately drain shuru ho jaata hai. CPI $= 1.80$ — phir bhi ideal se 80% upar, kyunki half run filling/draining mein guzar jaata hai. Sirf jab $n ≫ k$ ho tabhi steady-state "har tick mein ek exit" dominate karta hai aur CPI 1 ki taraf settle hota hai.

Recall Solution L5.2

Pehle, woh symbol jo humhe chahiye — IPC. IPC (Instructions Per Cycle) woh average number of instructions hai jo har clock tick mein finish hoti hain — yeh CPI ka plain reciprocal hai: $IPC = 1/ CPI$ , aur equivalently $CPI = 1/ IPC$ . Jahaan CPI "ticks per instruction" count karta hai, IPC "instructions per tick" count karta hai. Ek scalar pipeline IPC $= 1$ pe top out karta hai; ek superscalar isse exceed kar sakta hai. (a) Yahaan sustained IPC directly 2.8 diya gaya hai (instructions finished per tick). Toh $CPI = \frac{1}{IPC} = \frac{1}{2.8} = 0.357.$ (b) $Throughput = \frac{clock}{CPI} = \frac{4.0 \times 1 0 ^{9}}{0.357} = 1.12 \times 1 0^{10} = 11.2 billion instr/s$ (Equivalently $4.0 \times 1 0^{9} \times 2.8$ .) (c) Ek scalar pipeline har tick mein at most ek instruction finish karta hai (CPI $\geq 1$ ). Ek superscalar har tick mein kaafi saari finish karta hai, isliye CPI 1 se neeche ja sakta hai — dekho 5.3.02-Superscalar-architecture.

Recall Solution L5.3

(a) Clock period. KYA: $max (delays) + t_{r e g}$ apply karo. KYUN: zero-delay stage $max$ mein 0 contribute karta hai, isliye woh clock ke liye invisible hai — tick 100-ps stages se set hoti hai. $T_{p i p e} = max (100, 0, 100, 100, 100) + 15 = 100 + 15 = 115 ps$ (b) Do designs compare karo. KYA: stage remove karne ke baad time-per-instruction ( $CPI \times T$ ) ke dono factors check karo. KYUN: stage remove karna $T$ ya CPI dono badal sakta hai; yahaan worst stage unchanged hai isliye $T$ 115 ps pe rehta hai, jabki CPI 0.02 se girta hai (ek kam register jo forward karna padta hai). $T_{4} = 115 ps (unchanged), CPI_{4} = 1.30 - 0.02 = 1.28$ Kyunki $T$ identical hai aur CPI gira, time per instruction $CPI \times T$ $1.30 \times 115 = 149.5$ se $1.28 \times 115 = 147.2$ (ps) pe aa jaata hai. 4-stage version strictly faster hai. Lesson: jo stage na $max$ raise kare na kisi aur stage ko shorten kare woh pure overhead hai — use delete karo.

Recall Self-check clozes

Pipeline clock period equals == $max$ of stage delays $+ t_{r e g}$ , sum nahi. Actual CPI equals $1 +$ stalls per instruction ek scalar pipeline ke liye. Throughput equals clock rate $\div$ CPI. CPI below 1 ke liye superscalar (multiple-issue)== execution chahiye. Total cycles to run $n$ instructions in a $k$ -stage pipe ::: $k + (n - 1)$ . Fill-and-drain tax per instruction for $n$ instructions in a $k$ -stage pipe ::: $\frac{k - 1}{n}$ extra cycles. Ek $k$ -stage pipe pe $n = 1$ instruction wale program ka CPI ::: exactly $k$ (koi overlap nahi, pipe kabhi fill nahi hoti).