Deep pipelining trade-offs: Exercises — Hinglish deep dive

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

Yeh page ek self-test ladder hai. Har problem apna difficulty level batata hai (L1 → L5). Pehle Solution callout collapse karke try karo, phir open karke har step check karo. Saare numbers machine-verified hain.

Shuru karne se pehle, yeh pakka kar lete hain ki neeche use hone wale har symbol ka matlab pehle se clear ho — yahan kuch bhi bina plain-words meaning ke nahi aata.

Definition Is page par use hone wale symbols

$k$ = number of pipeline stages (kitne slices mein hum instruction ka kaam kaatte hain). Zyada slices = chota slice = tez clock. $k$ ek positive integer hai, $k \geq 1$ — "aadha stage" nahi ban sakta. Hum aksar pehle continuous formula solve karenge aur phir poore number tak round karenge, kyunki maths real numbers deta hai lekin hardware sirf integers accept karta hai.
$T_{0}$ = total combinational logic delay agar hum bilkul pipeline na karein (ek bada slice), nanoseconds (ns) mein measure hota hai.
$τ = T_{0} / k$ = logic delay of one stage jab $T_{0}$ ko $k$ equal pieces mein kaata jaata hai.
$t_{reg}$ = pipeline-register overhead per stage: stages ke beech latch ka fixed time cost (setup + clock-to-Q + skew). Jab stages badhate hain to yeh shrink nahi hota.
$T_{cycle} = τ + t_{reg}$ = clock period, ek tick kitna time leta hai. Sabse slow stage set karta hai.
$f = 1/ T_{cycle}$ = clock frequency (ticks per second). Agar $T_{cycle}$ ns mein hai, to $f = 1000/ T_{cycle}$ MHz mein.
CPI = cycles per instruction = average clock ticks jo har instruction consume karta hai. Ideal pipeline = 1; hazards ise 1 se upar push karte hain.
Throughput = useful work per second $= f / CPI$ . Yahi woh number hai jo actually matter karta hai.

Poori derivations ke liye Deep pipelining trade-offs dekho jinhe yeh problems drill karti hain.

Level 1 — Recognition

Problem 1.1

$k$ , $τ$ , $t_{reg}$ , aur $T_{cycle}$ ka matlab ek-ek sentence mein batao, aur woh formula likho jo inhe link karta hai.

Recall Solution 1.1

$k$ = number of pipeline stages (ek positive integer, $k \geq 1$ ).
$τ = T_{0} / k$ = ek stage ki combinational logic delay.
$t_{reg}$ = fixed per-stage pipeline-register overhead ( $k$ ke saath shrink nahi hota).
$T_{cycle}$ = clock period = ek tick ka time.
Link: $T_{cycle} = τ + t_{reg} = \frac{T _{0}}{k} + t_{reg} .$ Yeh kya kehta hai: jab hum stages badhate hain, pehla term shrink hota hai lekin doosra kabhi nahi hota.

Problem 1.2

Ek pipeline mein $T_{0} = 12$ ns logic hai jise $k = 6$ stages mein split kiya gaya hai, $t_{reg} = 0.3$ ns ke saath. $τ$ , $T_{cycle}$ , aur $f$ (MHz mein) nikalo.

Recall Solution 1.2

$τ = 12/6 = 2$ ns.
$T_{cycle} = 2 + 0.3 = 2.3$ ns.
$f = 1000/2.3 \approx 434.8$ MHz. 1000 kyun? 1 ns $= 1 0^{- 9}$ s, isliye $1/ T_{cycle} [ns] = 1 0^{9} / T_{cycle}$ Hz $= 1000/ T_{cycle}$ MHz.

Problem 1.3

Sahi hai ya galat: "Zyada pipeline stages add karne se hamesha $T_{cycle}$ kam hota hai." Formula use karke explain karo.

Recall Solution 1.3

Galat (practice mein), sirf idealised logic-only model mein sahi. Pure model mein $T_{cycle} = T_{0} / k + t_{reg}$ , $k$ badhane se $T_{0} / k$ shrink hota hai, isliye $T_{cycle}$ girta rehta hai — lekin sirf asymptotically $t_{reg}$ ki taraf, kabhi usse neeche nahi. Reality mein logic infinitely divisible nahi hai (atomic stages hain), isliye kisi depth ke baad slowest stage shrink hona band ho jaata hai aur $T_{cycle}$ flat ho jaata hai. Toh honest answer hai: ideal model mein yeh kabhi $T_{cycle}$ nahi badhata, lekin benefit khatam ho jaata hai.

Level 2 — Application

Problem 2.1

Unpipelined logic $T_{0} = 10$ ns, register overhead $t_{reg} = 0.2$ ns, perfect balance. $k = 5$ , $k = 10$ , aur $k = 20$ stages ke liye ideal speedup $\frac{T _{0}}{T _{cycle}}$ compute karo. Do decimals tak round karo.

Recall Solution 2.1

Yeh formula kyun? Unpipelined mein, ek instruction poora $T_{0}$ finish karne mein leta hai. Ek full $k$ -stage pipeline, jab uske saare stages busy ho jaate hain, har clock tick mein ek instruction retire karta hai — yaani har $T_{cycle}$ mein ek. Toh per instruction time $T_{0}$ se $T_{cycle}$ tak girta hai, aur speedup un dono per-instruction times ka ratio hai: $Speedup = \frac{T _{0}}{T _{cycle}} = \frac{T _{0}}{T _{0} / k + t _{reg}} .$ Isliye $T_{0}$ upar hai aur ek cycle neeche — hum "seconds per instruction, before vs after" compare kar rahe hain.

$k = 5$ : $T_{cycle} = 2 + 0.2 = 2.2$ ; speedup $= 10/2.2 = 4.55 \times$ .
$k = 10$ : $T_{cycle} = 1 + 0.2 = 1.2$ ; speedup $= 10/1.2 = 8.33 \times$ .
$k = 20$ : $T_{cycle} = 0.5 + 0.2 = 0.7$ ; speedup $= 10/0.7 = 14.29 \times$ . Kaisa dikhta hai — Figure s01 padho: blue curve yahi speedup vs $k$ hai. Teen coloured dots hamare answers mark karte hain (orange $k = 5$ , green $k = 10$ , gray $k = 20$ ). Notice karo ki green aur gray dots ke beech gap double nahi hai orange aur green ke beech ke gap se — curve dashed red ceiling ki taraf bend ho raha hai. Woh bend IS diminishing returns, visible bana hua.

Problem 2.2

Upar ke $k = 5 \to k = 20$ result se, "diminishing returns" quantify karo: humne pipeline $4 \times$ deeper ki — ideal speedup actually kis factor se bada?

Recall Solution 2.2

Depth $20/5 = 4 \times$ bada. Speedup $14.29/4.55 = 3.14 \times$ bada. Toh $4 \times$ hardware depth sirf $3.14 \times$ speed deta hai. Missing $0.86 \times$ $t_{reg}$ ne kha liya, jo ab har cycle ka $0.2/0.7 = 28.6%$ hai (vs $k = 5$ par $0.2/2.2 = 9.1%$ ). Figure par: yeh exactly woh vertical distance hai gray dot se neeche wahan tak jahan ek straight $4 \times$ line orange dot se land hoti — shortfall hai red ceiling jo curve ko flat kheench rahi hai.

Problem 2.3

Ek design mein $T_{0} = 15$ ns aur $t_{reg} = 0.5$ ns hai. Maximum possible clock frequency kya hai (asymptotic limit jab $k \to \infty$ ), MHz mein?

Recall Solution 2.3

Jab $k \to \infty$ , $T_{0} / k \to 0$ , isliye $T_{cycle} \to t_{reg} = 0.5$ ns. $f_{m a x} = 1000/0.5 = 2000 MHz = 2 GHz .$ Ceiling kyun hai: tum kabhi ek cycle ko register handoff se chota nahi bana sakte. Yahi woh wall hai jisme deep pipelining run karti hai. (Yeh limit mathematical $k \to \infty$ hai; real $k$ finite integer hai, isliye tum 2 GHz ko sirf approach kar sakte ho.)

Level 3 — Analysis

Problem 3.1

Branches har 5 instructions mein aate hain; prediction accuracy 90% hai; misprediction penalty $k - 1$ cycles hai. 5-stage aur 20-stage pipeline ke liye effective CPI compute karo (data hazards ignore karo).

Recall Solution 3.1

Fraction of instructions jo branches hain $= 1/5 = 0.2$ . Mispredicted fraction $= 0.2 \times (1 - 0.90) = 0.2 \times 0.10 = 0.02$ per instruction. Stall CPI $= 0.02 \times (k - 1)$ .

5-stage: $0.02 \times 4 = 0.08$ ⇒ CPI $= 1.08$ .
20-stage: $0.02 \times 19 = 0.38$ ⇒ CPI $= 1.38$ . Kya hota hai: har mispredict poori pipeline flush kar deta hai; lambi pipe mein zyada in-flight kaam barbaad hota hai. Branch Prediction aur Pipeline Hazards dekho.

Problem 3.2

20-stage pipeline ka clock 5-stage se $4 \times$ tez hai. Problem 3.1 ke CPIs use karte hue, effective speedup (throughput ratio) nikalo. Kya $4 \times$ frequency pay off hui?

Recall Solution 3.2

Throughput $\propto f / CPI$ . $Speedup = \frac{f _{20}}{f _{5}} \cdot \frac{CPI _{5}}{CPI _{20}} = 4 \times \frac{1.08}{1.38} = 4 \times 0.7826 = 3.13 \times .$ Verdict: $4 \times$ clock sirf $3.13 \times$ throughput deta hai. CPI 1.08 se 1.38 ( $1.28 \times$ worse) tak badha, frequency win ka karib ek chauthai mita diya. Complementary lever ke liye Superscalar Architectures dekho ( $f$ ki jagah IPC badhana).

Problem 3.3

Kis branch prediction accuracy $p$ par 20-stage pipeline ki control-stall CPI, problem 3.1 ki 5-stage pipeline ki control-stall CPI (jo 0.08 thi) ke barabar hogi? Branch frequency $0.2$ aur penalty $19$ rakho.

Recall Solution 3.3

$0.2 \times (1 - p) \times 19 = 0.08$ set karo. $1 - p = \frac{0.08}{0.2 \times 19} = \frac{0.08}{3.8} = 0.02105.$ $p = 1 - 0.02105 = 0.97895 \approx 97.9%.$ Matlab: 20-stage pipe ke control stalls ko 5-stage pipe jitna kam rakhne ke liye, prediction ko 90% se ~97.9% tak jaana hoga. Isi liye deep pipelines ko excellent branch prediction chahiye — accuracy ki requirement depth ke saath badhti hai.

Level 4 — Synthesis

Problem 4.1

Dynamic power $P = C V^{2} f$ hai. Deeper pipeline $f$ ko $1.5 \times$ badhata hai. Agar voltage $V$ aur capacitance $C$ constant rakhen, to dynamic power kis factor se badhega? Phir, agar designer $V$ ko 10% kam kar de ( $0.9 V$ pe), to net power factor kya hoga?

Recall Solution 4.1

Constant $V$ pe: $P \propto f$ , isliye power $1.5 \times$ badhega. $V \to 0.9 V$ ke saath: power $V^{2} f$ ke saath scale hota hai, isliye factor $= (0.9)^{2} \times 1.5 = 0.81 \times 1.5 = 1.215 \times$ . Interpretation: 10% voltage cut ke baad bhi, power 21.5% badhta hai. Voltage reduction (Dynamic Voltage and Frequency Scaling (DVFS) ke peeche lever) tez jaane ki power cost ko soft karta hai lekin mita nahi sakta, kyunki power $V$ ke square par depend karta hai lekin $f$ par sirf linearly.

Problem 4.2 — Pentium 4 Prescott reconstruction

Northwood (20 stages) vs Prescott (31 stages): Prescott ne frequency $1.5 \times$ badhayi lekin uska CPI bhi $1.5 \times$ badh gaya. (a) Net performance factor compute karo. (b) Agar power bhi $1.5 \times$ badhi, to Northwood ke relative performance-per-watt compute karo.

Recall Solution 4.2

(a) Performance $\propto f / CPI$ : $\frac{1.5 f}{1.5 CPI} = 1.0 \times .$ Koi net gain nahi — frequency win exactly CPI loss se cancel ho gayi. Yahi "deep-pipeline wall" hai. (b) Performance-per-watt $= \frac{performance}{power} = \frac{1.0}{1.5} = 0.667 \times$ . Verdict: same speed, $1.5 \times$ power ⇒ efficiency do-tihai reh gayi. Isi liye Intel ne Core microarchitecture ke liye deep-pipeline path abandon kiya. Pentium 4 vs Core Microarchitecture dekho.

Problem 4.3

Do effects combine karo. $T_{0} = 10$ ns, $t_{reg} = 0.2$ ns lo. Throughput index $Θ (k) = \frac{f ( k )}{CPI ( k )}$ define karo jahan $f (k) = 1000/ (10/ k + 0.2)$ MHz aur $CPI (k) = 1 + 0.02 (k - 1)$ hai (problem 3.1 ke branch model se). $k = 5, 10, 15, 20$ ke liye $Θ$ compute karo aur identify karo ki kaun sa $k$ throughput maximize karta hai.

Recall Solution 4.3

Yeh index kyun? $f$ ticks-per-second batata hai, $CPI$ ticks-per-instruction batata hai, isliye $f / CPI$ = instructions-per-second — actual useful-work rate. Divide karne se "cycle" unit cancel hoti hai aur work-per-time bachta hai, jo exactly woh hai jo hum maximize karna chahte hain. Hum ise sirf whole-number $k$ par evaluate karte hain kyunki stages integers hain. Har ek compute karo (frequency MHz mein, CPI dimensionless, $Θ$ MHz-per-instruction-cycle mein):

$k = 5$ : $f = 1000/2.2 = 454.55$ , CPI $= 1.08$ , $Θ = 420.9$ .
$k = 10$ : $f = 1000/1.2 = 833.33$ , CPI $= 1.18$ , $Θ = 706.2$ .
$k = 15$ : $f = 1000/0.8667 = 1153.85$ , CPI $= 1.28$ , $Θ = 901.4$ .
$k = 20$ : $f = 1000/0.7 = 1428.57$ , CPI $= 1.38$ , $Θ = 1035.2$ . Result: is range ke andar $Θ$ $k$ ke saath badhta hi rahta hai ( $k = 20$ par peak) — kyunki 90% prediction CPI growth ko mild rakhti hai. Peak chote $k$ ki taraf move karta hai jab data hazards aur worse prediction add karo. Lesson: optimal depth poori tarah is par depend karta hai ki CPI kitni tezi se badhta hai. Figure s02 padho: blue curve yahi $Θ (k)$ hai bina atomic floor ke — yeh poori range mein chadhta rahta hai, isi liye naive model tumhe kabhi rokne ko nahi kehta.

Level 5 — Mastery

Problem 5.1 — Imbalance ke saath true optimum derive karo

Suppose logic ko ek atomic floor se neeche split nahi kiya ja sakta: slowest stage $τ_{m i n} = max (T_{0} / k, a)$ hai jahan $a = 0.6$ ns ek unsplittable operation hai (jaise cache access, Instruction Pipelining Basics dekho). $T_{0} = 10$ ns aur $t_{reg} = 0.2$ ns ke saath, woh smallest $k$ nikalo jiske baad stages add karne se zero frequency benefit milta hai.

Recall Solution 5.1

Frequency tab improve hona band karti hai jab $T_{0} / k$ atomic floor $a$ tak girta hai, yaani jab $T_{0} / k \leq a$ : $k \geq \frac{T _{0}}{a} = \frac{10}{0.6} = 16.67.$ Integer-stage step: $16.67$ ek legal stage count nahi hai — $k$ ek whole number hona chahiye. Hum round up karte hain agla integer $k = 17$ tak, kyunki woh pehla integer hai jis par $T_{0} / k = 10/17 = 0.588 \leq 0.6$ actually hold karta hai ( $k = 16$ par, $10/16 = 0.625 > 0.6$ , toh floor abhi tak reach nahi hua). $k \geq 17$ ke liye, slowest stage $0.6$ ns par stuck hai, isliye $T_{cycle} = 0.6 + 0.2 = 0.8$ ns aur $f$ $1000/0.8 = 1250$ MHz par freeze ho jaata hai chahe kitne bhi zyada stages add karo — lekin CPI $k$ ke saath badhta rehta hai. Toh $k = 17$ ke baad, deeper strictly worse hai. Yahi stage imbalance "harmless" se "harmful" ban jaata hai.

Problem 5.2 — Full throughput optimisation

$T_{cycle} (k) = max (10/ k, 0.6) + 0.2$ aur $CPI (k) = 1 + 0.02 (k - 1)$ use karo. $k = 15, 17, 20, 25$ par throughput index $Θ (k) = f (k) / CPI (k)$ compute karo aur true optimal depth batao.

Recall Solution 5.2

$max$ ab kyun aata hai: clock slowest stage set karta hai, aur koi bhi stage atomic floor $a = 0.6$ ns se tez nahi ho sakta. Isliye cycle ka logic part $max (10/ k, 0.6)$ hai: yeh $10/ k$ follow karta hai jab tak woh $0.6$ se upar hai, phir $0.6$ par clamp hota hai. Sirf integer $k$ par evaluate karo:

$k = 15$ : $10/15 = 0.667 > 0.6$ , floor abhi active nahi, isliye $T_{cycle} = 0.667 + 0.2 = 0.867$ ns, $f = 1000/0.867 = 1153.85$ MHz; CPI $= 1 + 0.02 (14) = 1.28$ ; $Θ = 1153.85/1.28 = 901.4$ .
$k = 17$ : $10/17 = 0.588 < 0.6$ , floor ab active hai, isliye $T_{cycle} = 0.6 + 0.2 = 0.8$ ns, $f = 1000/0.8 = 1250$ MHz; CPI $= 1 + 0.02 (16) = 1.32$ ; $Θ = 1250/1.32 = 946.97$ .
$k = 20$ : floor active, $f = 1250$ MHz (frozen); CPI $= 1 + 0.02 (19) = 1.38$ ; $Θ = 1250/1.38 = 905.80$ .
$k = 25$ : floor active, $f = 1250$ MHz (frozen); CPI $= 1 + 0.02 (24) = 1.48$ ; $Θ = 1250/1.48 = 844.59$ . True optimal depth $k^{*} = 17$ . List neeche padhte hue, $Θ$ $901.4 \to 946.97$ tak chadhta hai jab hum floor reach karte hain, phir frequency freeze hone par lekin CPI badhte rehne par girta hai $946.97 \to 905.80 \to 844.59$ . Maximum exactly $k = 17$ par hai — pehla integer jahan atomic floor clock cap karta hai. Uske baad, tum zyada registers aur zyada hazard stalls pay karte ho zero extra frequency ke liye, isliye throughput sirf gir sakta hai. Yahi honest sweet spot hai: depth ko floor tak push karo, phir ruko.

Problem 5.3 — Design judgement

Ek rival team depth ko 17 se 34 stages tak double karne ka proposal deta hai, "double the frequency" ka vaada karke. Problem 5.2 ke model ko dekhte hue, numbers ke saath do-line rebuttal likho.

Recall Solution 5.3

Rebuttal: Frequency double nahi hoti — slowest atomic stage already $0.6$ ns floor par hai, isliye $f$ $k = 17$ se aage $1250$ MHz par pinned rehti hai; 34 tak double karne se $f$ mein $0%$ change hota hai. Lekin CPI $1.32$ se $1 + 0.02 (33) = 1.66$ tak badhta hai, isliye throughput $Θ = 947$ se $1250/1.66 = 753$ tak girta hai — ek 20% loss — plus roughly double register power. Yahan depth double karna sirf cost hai, koi benefit nahi.

Recall Self-check summary (cloze)

Clock period hai $T_{cycle} =$ ::: $τ + t_{reg} = T_{0} / k + t_{reg}$ Woh quantity jo actually performance measure karti hai woh hai ::: throughput $= f / CPI$ Ideal model mein $k \to \infty$ par, $f$ bounded hai ::: $1/ t_{reg}$ se $k$ -stage pipe mein branch misprediction penalty hai ::: $k - 1$ cycles True depth limit tab aata hai jab $T_{0} / k$ hit karta hai ::: atomic (unsplittable) stage floor $a$ ko, yaani $k = ⌈ T_{0} / a ⌉$