Classic 5-stage pipeline (IF - ID - EX - MEM - WB): Worked examples

5.2.3 · D3 · Hardware › Processor Datapath & Pipelining › Classic 5-stage pipeline (IF - ID - EX - MEM - WB)

Yeh deep dive Classic 5-stage pipeline ke timing formulas ko itna drill karta hai ki koi bhi case aapko surprise na kar sake. Hum har symbol ko zero se build karte hain, phir scenario matrix ke har cell ka ek worked example walk karte hain.

Symbols ko zero se banana

Koi bhi arithmetic se pehle, yahan har woh letter hai jo hum use karenge. Koi bhi symbol jo abhi tak aapne nahi dekha, use kabhi allow nahi kiya jaayega.

Scenario matrix

Is topic ke har timing question ko inhi cells mein se kisi ek mein daala ja sakta hai. Neeche ke worked examples mein har ek ke saath [Cell X] tag hai taaki aap dekh sako ki coverage total hai.

Cell	Scenario class	Jis twist ko test karta hai
A	Bada $N$ , balanced stages	Speedup → $k$ (ideal limit)
B	Chhota $N$	Fill cost dominate karta hai; speedup $k$ se bahut neeche
C	$N = 1$ (degenerate)	Pure latency; pipelining yahan haarta hai
D	Unbalanced stage delays	Ek slow stage baaki sab ke slots waste karta hai
E	Deeper pipeline, same kaam	Latch overhead $d$ gain kha jaata hai (diminishing returns)
F	Limiting case $N \to \infty$	Prove karo ki cap exactly $k$ hai
G	Real-world word problem	English → teen equations mein translate karo
H	Exam twist: superpipeline vs. cost	Jab zyada stages hurt karte hain

Worked examples

Cell A — bada stream, balanced stages

Worked example Example 1 — near-ideal speedup

[Cell A] Ek balanced 5-stage pipeline. Har stage ki logic delay $t_{i} = 2$ ns hai aur latch overhead $d$ yahan negligible hai, toh $T_{c l k} = 2$ ns. $N = 1000$ instructions chalao, koi stalls nahi. Ek single-cycle machine se compare karo jiska ek bada cycle saare paanch stages ki logic plus uska single latch karta hai: $5 \times 2 + d \approx 10$ ns (jab $d \approx 0$ ).

Forecast: speedup guess karo — kya yeh 4, 5, ya 6 ke zyada paas hai?

Cycles $= k + (N - 1) = 5 + 999 = 1004$ . Yeh step kyun? $k = 5$ ticks pipe fill karte hain (pehla result cycle 5 par aata hai), phir baaki $999$ instructions har agli tick mein finish hote hain — ek per cycle.
Pipelined time $= 1004 \times 2 = 2008$ ns. Kyun? har cycle exactly $T_{c l k} = 2$ ns chalti hai.
Single-cycle time $= N \times (5 t_{i} + d) = 1000 \times (10 + 0) = 10000$ ns. Kyun? non-pipelined machine saare paanch stages ki logic ek sweep mein karti hai (10 ns) plus ek latch $d$ ; yahan $d \approx 0$ liya hai, toh $10$ ns per instruction. (Yeh wahi " $\sum t_{i} + d$ " rule hai jo Example 3 use karta hai — yahan $d$ bas negligibly small hai.)
Speedup $= 10000/2008 \approx 4.98 \times$ . Kyun? bada $N$ 4-cycle fill cost ko negligible bana deta hai, toh hum ideal $k = 5$ ke paas pahunch jaate hain.

Verify: formula limit $\frac{N k}{k + N - 1} = \frac{5000}{1004} = 4.98$ ✓ — match karta hai, aur jaise expect tha, 5 se thoda neeche hai.

Cell B — ek chhota stream

Worked example Example 2 — jab pipe barely fill ho

[Cell B] Wahi balanced 5-stage pipeline ( $T_{c l k} = 2$ ns, single-cycle $\approx 10$ ns per instruction jaise Example 1 mein), lekin sirf $N = 3$ instructions.

Forecast: sirf 3 instructions ke saath, kya hum phir bhi $5 \times$ ke paas pahunchenge?

Cycles $= k + (N - 1) = 5 + (3 - 1) = 7$ . Kyun? pipeline apni zyaadatar life half-empty guzarti hai — sirf cycles 5, 6, 7 result produce karte hain.
Pipelined time $= 7 \times 2 = 14$ ns. Kyun? 7 cycles mein se har ek $T_{c l k} = 2$ ns chalti hai.
Single-cycle time $= N \times 10 = 3 \times 10 = 30$ ns. Kyun? teen instructions, har ek $\approx 10$ ns sweep (Example 1 jaisa hi single-cycle cost).
Speedup $= 30/14 = \frac{15}{7} \approx 2.14 \times$ . Itna kam kyun? 4-cycle fill overhead sirf 7 cycles ka ek bada fraction hai. Fill cost abhi amortise nahi hui hai.

Verify: formula se cross-check $\frac{N k}{k + N - 1} = \frac{15}{7} = 2.142 \dots$ ✓; $1$ aur $k = 5$ ke beech ✓.

Cell C — degenerate single instruction

Worked example Example 3 — sirf ek instruction (

$N = 1$ ) [Cell C] Ek akela instruction chalao. Balanced stages, $t_{i} = 2$ ns each, latch $d = 0.2$ ns, toh $T_{c l k} = 2.2$ ns. Pipelined latency ko single-cycle machine se compare karo.

Forecast: pipeline ek instruction ke liye jeetta hai, tie karta hai, ya haarta hai?

Pipelined cycles $= k + (N - 1) = 5 + 0 = 5$ . Kyun? akele instruction ko phir bhi saare 5 stages se guzarna padta hai; koi baad wala instruction nahi hai jiske saath overlap ho sake.
Pipelined latency $= 5 \times 2.2 = 11.0$ ns. Kyun? paanch clock ticks, har ek latch overhead $d$ se padded — pipe paanch baar latch karti hai.
Single-cycle latency $= 5 \times t_{i} + d = 10 + 0.2 = 10.2$ ns. Kyun? saari logic ka ek combinational sweep, ek baar latch kiya — wahi $\sum t_{i} + d$ rule jaise Examples 1–2 mein, ab $d$ visible hai.
Result: pipelining yahan slower hai: $11.0 > 10.2$ ns. Kyun? pipelining latch overhead $d$ ko paanch baar pay karti hai ( $5 d = 1.0$ ns) ek baar ki jagah — dekho Single-cycle vs Multicycle Datapath.

Verify: $11.0 - 10.2 = 0.8$ ns extra $= 4 d = 4 \times 0.2$ ✓ (single wale se chaar extra latches). Yeh parent note ke "latency slightly worsens" claim ka concrete proof hai.

Cell D — unbalanced stages

Worked example Example 4 — ek slow stage poora clock poison kar deta hai

[Cell D] Stage delays: IF = 200, ID = 100, EX = 150, MEM = 200, WB = 100 (ps). Latch $d = 20$ ps. $T_{c l k}$ find karo, aur large $N$ ke liye realistic speedup.

Forecast: total logic $750$ ps hai jo 5 mein split hai — kya speedup 5 ke paas hoga?

$max_{i} (t_{i}) = 200$ ps (IF aur MEM tie karte hain sabse slow ke liye). Max kyun? saare stages ek clock share karte hain; clock itni lambi honi chahiye ki sabse slow logic settle ho sake, warna us stage ka result galat hoga. Figure mein sabse oonche bars dekho.
$T_{c l k} = 200 + 20 = 220$ ps. $+ d$ kyun? har stage ko apna result apne pipeline register mein latch bhi karna hota hai.
Single-cycle machine ko $750 + 20 = 770$ ps per instruction chahiye (ek sweep mein saari logic, ek baar latch kiya). $750$ kyun? $200 + 100 + 150 + 200 + 100$ = poori combinational chain, plus uska single $d = 20$ .
Large- $N$ speedup $= 770/220 \approx 3.5 \times$ , $5 \times$ nahi. Shortfall kyun? WB apne 220 ps slot mein sirf 100 ps use karta hai — figure mein grey wasted area. Imbalance fast stages mein clock time waste karta hai.

Verify: $770/220 = 3.5$ exactly ✓. WB mein wasted time $= 220 - 20 - 100 = 100$ ps ✓ (grey gap se match karta hai).

Cell E — deeper pipe, same total kaam

Worked example Example 5 — zyada stages se diminishing returns

[Cell E] Context switch: ab hum picoseconds mein kaam kar rahe hain, total combinational workload $\sum_{i} t_{i} = 750$ ps hai (wahi 750 ps chain jo Example 4 mein thi, Examples 1–3 ka 2 ns/stage balanced case nahi). Hum us same 750 ps ko slice karne ke do tarike compare karte hain: $k = 5$ balanced stages mein, aur $k = 10$ balanced stages mein. Latch $d = 20$ ps.

Forecast: stages ko 10 tak double karna — kya throughput double hogi?

5-stage (balanced) $T_{c l k}$ $= 750/5 + 20 = 150 + 20 = 170$ ps. Kyun? 750 ps ko 5 equal stages mein split karne se har ek mein $150$ ps logic aati hai, plus ek latch $d$ .
10-stage $T_{c l k}$ $= 750/10 + 20 = 75 + 20 = 95$ ps. Kyun? ab har stage mein sirf $75$ ps logic hai, lekin $20$ ps latch phir bhi deni padti hai.
Throughput ratio $= 170/95 \approx 1.79 \times$ , $2 \times$ nahi. Double kyun nahi? latch $d = 20$ ps ab har 95 ps period ka $21%$ hai. Overhead stage ke saath nahi shrinkta — dekho Clocking & Latch Overhead.

Verify: $170/95 = 1.789 \dots$ ✓ — strictly us naive $2 \times$ se kam jo aap umeed karte.

Cell F — limit, proven

Worked example Example 6 — speedup exactly

$k$ par kyun cap hoti hai [Cell F] Prove karo $N \to \infty lim \frac{N k}{k + N - 1} = k$ .

Forecast: jab $N$ bahut bada hota jaata hai, speedup kisi ceiling ki taraf badhti hai — woh exactly kya hai?

Upar aur neeche ko $N$ se divide karo: $\frac{N k}{k + N - 1} = \frac{k}{\frac{k - 1}{N} + 1}$ . $N$ se divide kyun? yeh un parts ko isolate karta hai jo $N$ badhne par vanish ho jaate hain. Constant $k - 1$ (fill cost) ek fraction $\frac{k - 1}{N}$ ban jaata hai.
Jab $N \to \infty$ , $\frac{k - 1}{N} \to 0$ . Kyun? ek fixed number ko ever-growing number se divide karne par woh kuch nahi reh jaata — fill cost infinitely many instructions par amortise ho jaata hai.
Toh expression $\to \frac{k}{0 + 1} = k$ ho jaata hai. $k$ kyun? fill negligible hone par, aapke paas exactly $k$ instructions in-flight overlap ho rahi hain — ek $k$ -fold throughput gain. Figure mein curve dashed line $y = k$ ko hug karta hai.

Verify: $N = 100$ , $k = 5$ par: $\frac{500}{104} = 4.808$ ; $N = 10000$ par: $\frac{50000}{10004} = 4.9975$ — 5 ki taraf badhte hue ✓.

Cell G — real-world word problem

Worked example Example 7 — video encoder

[Cell G] Ek CPU pipeline $2 GHz$ par run karti hai (toh $T_{c l k} = 0.5$ ns) jisme $k = 5$ stages hain aur koi stalls nahi. Ek video codec loop har frame mein $8, 000, 000$ instructions execute karta hai. Ek frame kitne time mein complete hota hai, aur throughput ideal se kitni door hai?

Forecast: 8 million instructions ke saath, kya speedup essentially 5 hogi?

$T_{c l k} = 1/ (2 \times 1 0^{9} Hz) = 0.5$ ns. Kyun? period frequency ka reciprocal hota hai; $2$ GHz matlab do billion ticks per second.
Cycles $= k + (N - 1) = 5 + 7, 999, 999 = 8, 000, 004$ . Kyun? 4-extra fill cycles 8 million ke aage bilkul dab jaate hain.
Frame time $= 8, 000, 004 \times 0.5 ns = 4, 000, 002 ns \approx 4.0$ ms. ns→ms kyun? $4, 000, 002$ ns $= 4.000002 \times 1 0^{6}$ ns $= 4.0$ ms ( $1$ ms $= 1 0^{6}$ ns).
Speedup $= \frac{N k}{k + N - 1} = \frac{40 , 000 , 000}{8 , 000 , 004} \approx 4.9999975 \times$ . 5 ke itna paas kyun? enormous $N$ → fill cost invisible (Cell A extreme tak le jaaya gaya).

Verify: frame time $8000004 \times 0.5 = 4000002$ ns ✓; speedup $\approx 4.99999$ ✓ — throughput ideal ka $99.99995%$ hai.

Cell H — exam twist: jab zyada stages hurt karte hain

Worked example Example 8 — superpipeline trap

[Cell H] Wahi $750$ ps logic. Ek vendor $k = 30$ stages of $25$ ps each propose karta hai, latch $d = 20$ ps. Iske clock period ko 5-stage balanced design ( $T_{c l k} = 170$ ps from Example 5) se compare karo aur comment karo.

Forecast: 30 stages — zaroor bahut tez clock hogi?

30-stage $T_{c l k}$ $= 25 + 20 = 45$ ps. Kyun? ab sirf $25$ ps logic har stage mein hai, lekin $20$ ps latch unavoidable hai.
Latch fraction $= 20/45 \approx 44.4%$ har cycle pure overhead hai. Alarming kyun? almost aadha clock koi useful computation nahi karta — bas re-latch karta hai. Example 5 ka $21%$ se compare karo.
5-stage se throughput $= 170/45 \approx 3.78 \times$ faster clock. Clean win kyun nahi? yeh ignore karta hai ki deeper pipes bahut worse hazard penalties face karte hain (longer branch mispredict flush) — dekho Pipeline Hazards (structural, data, control) aur Branch Prediction — toh real speedup is raw clock ratio se neeche aa jaata hai.
Judgement: raw throughput badhti hai, lekin efficiency-per-transistor collapse ho jaati hai aur stalls ke saath real speedup gir sakta hai. Parent note ka "speedup saturates and can even fall" exactly yahi cell hai.

Verify: $170/45 = 3.777 \dots$ ✓; overhead fraction $20/45 = 0.4444 \dots$ ✓.

Recall Coverage self-check

Ex 1 → A · Ex 2 → B · Ex 3 → C · Ex 4 → D · Ex 5 → E · Ex 6 → F · Ex 7 → G · Ex 8 → H. Matrix ke har cell ka ek worked example hai.

Active recall

For a k-stage pipeline running N instructions with no stalls, how many cycles?

k + (N - 1)

— k cycles pipe fill karne ke liye, phir har cycle mein ek complete hoti hai.

Why does a single instruction (N=1) run slower pipelined?

Use phir bhi saare k stages traverse karne padte hain, aur latch overhead d har stage mein ek baar pay hoti hai (k·d), sirf ek baar ki jagah.

In Example 4, why is speedup 3.5× and not 5×?

Stages unbalanced hain; clock sabse slow stage ke hisaab se set hoti hai (200 ps + 20), jisse WB jaise fast stages mein slots waste hote hain.

Why doesn't doubling the number of stages double throughput?

Latch overhead d har stage ke liye fixed hai; jab stages chhoti hoti hain, d,

T_{c l k}

ka ek bada fraction ban jaata hai.

What is the large-N speedup limit and why?

k× — fill cost (k−1) N ke relative negligible ho jaata hai, sirf k overlapped instructions bachti hain.

Which formula must you use for small N instead of the k-limit?

Speedup = \frac{N k}{k + N - 1}

How many times does a single-cycle machine latch per instruction, versus a k-stage pipeline?

Single-cycle sirf ek baar latch karta hai (ek d); pipeline k baar latch karti hai (k·d).