Worked examples — Pipeline throughput and CPI

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

Yeh page parent topic ka drill ground hai. Kuch bhi compute karne se pehle, aao har tarah ke questions list karein jo yeh topic throw kar sakta hai. Phir hum ek example per cell solve karte hain, taaki koi bhi scenario aapko naya na lage jab tak woh already dekha hua na ho.

---

The scenario matrix

Pipeline performance ke baare mein har exam question in cells mein se ek mein aata hai. Hamara kaam hai inhe sab cover karna.

#	Cell (case class)	Kya tricky banata hai	Hit by
A	Ideal fill-up — $n$ instructions ke liye exact cycles	"$+(k-1)$" fill cost, chhota $n$	Ex 1
B	Limiting value $n\to \infty$	CPI $1$ par kyun collapse hota hai	Ex 1
C	Clock period unbalanced stages se	max lo, register overhead add karo	Ex 2
D	Speedup vs single-cycle	sum-of-stages ÷ pipe period	Ex 2
E	CPI with data + control hazards	do stall sources combine karo	Ex 3
F	Forwarding stalls hatata hai	before/after CPI difference	Ex 4
G	Branch prediction improvement	accuracy → mispredict rate flip	Ex 5
H	Degenerate: 1-stage / perfectly balanced	edge jahan pipelining kuch nahi karta	Ex 6
I	Zero-hazard vs all-hazard extremes	CPI floor aur ek worst case	Ex 6
J	Superscalar: CPI < 1	IPC > 1, real-world word problem	Ex 7
K	Exam twist: kaun sa processor faster hai?	GHz akela ek trap hai	Ex 8

Prerequisite links agar kisi cell ko backup chahiye: 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.

---

Example 1 — Cells A & B: exact cycles aur limit

Forecast: abhi andaza lagao — kya CPI girega ya badhega jaise $n$ badhta hai? Kis number ki taraf?

Figure dekho: har row ek instruction hai jo har cycle mein ek stage right slide karti hai. Staircase sirf pehli instruction ke WB corner tak pahunchne mein $k$ cycles leta hai; uske baad, har single cycle mein ek finish hoti hai.

Step 1 — Fill count karo. Pehli instruction ko saare $k=5$ cycles chahiye IF→ID→EX→MEM→WB travel karne ke liye. Yeh step kyun? Pipe ke full hone se pehle kuch bhi finish nahi ho sakta — yeh unavoidable start-up cost hai.

Step 2 — Steady state count karo. Pehle ke finish hone ke baad, baaki $n-1$ instructions ek per cycle finish hoti hain. $\text{Total cycles}=k+(n-1)=5+(n-1)=n+4$ Kyun? Baad ki har instruction ek cycle peeche hai usse jo aage hai — assembly-line rhythm.

Step 3 — CPI nikalne ke liye divide karo. $\text{CPI}=\frac{n+4}{n}$

$n$	Total cycles	CPI
1	5	5.000
5	9	1.800
100	104	1.040
$10^6$	1000004	1.000004

Step 4 — The limit. Jaise $n\to \infty$, constant $4$ $n$ ke saath negligible ho jaata hai: ${\lim }_{n\to \infty }\frac{n+4}{n}=1.$ Yahan limit kyun? CPI ek per-instruction average hai; fixed fill cost zyada se zyada instructions mein share hoti jaati hai, isliye uska per-instruction hissa vanish ho jaata hai.

Verify: $n=5$ ke liye: $\frac{9}{5}=1.8$ ✓. Single instruction CPI $=5$ deta hai (latency ke barabar — pipelining ek instruction ke liye kuch nahi deta, bilkul expected hai).

---

Example 2 — Cells C & D: clock period aur speedup

Forecast: kaun sa stage clock set karta hai, aur kya speedup ideal $5\times$ tak pahunchega?

Step 1 — Sabse slow stage chuno. Saare stages ek hi clock edge par tick karte hain, isliye clock sirf utni hi fast ho sakti hai jitni slowest stage allow karti hai. $\max (80,70,100,90,60)=100\text{ps (EX)}.$ Max kyun, average nahi? Ek slow worker poori line rok deta hai chahe baaqi fast hon.

Step 2 — Register overhead add karo. $T_{pipe}=100+30=130\text{ps}.$ Kyun? Har stage ka result next edge se pehle pipeline register mein latched hona chahiye.

Step 3 — Single-cycle period = saare stages ka sum. Bina overlap ke ek instruction ek lambe cycle mein har stage se guzarti hai: $T_{single}=80+70+100+90+60=400\text{ps}.$

Step 4 — Speedup. $\text{Speedup}=\frac{T_{single}}{T_{pipe}}=\frac{400}{130}\approx \mathrm{3.08.}$ $5$ se neeche kyun? Stage imbalance (EX clock ko hog karta hai) aur $30$ ps overhead ideal $5\times$ chura lete hain.

Verify: $130\times 3.08\approx 400$ ✓. Ideal (balanced, no overhead) hota $400/80=5$ — hamara $3.08$ correctly usse neeche hai.

---

Example 3 — Cell E: dono hazard types ke saath CPI

Forecast: kya CPI $1.1$ ke kareeb hoga ya $1.4$ ke?

Step 1 — Branch stalls per instruction. Sirf mispredicted branches cycles waste karte hain: $0.25\times 0.10\times 3=\mathrm{0.075.}$ Triple product kyun? Jo branches hain unka fraction × jo mispredict hoti hain unka fraction × har ek kitne cycles waste karta hai.

Step 2 — Data-hazard stalls per instruction. $0.15\times 2=\mathrm{0.30.}$

Step 3 — Ideal floor 1 mein add karo. $\text{CPI}=1+0.075+0.30=\mathrm{1.375.}$

Step 4 — Throughput. $\frac{2\times 10^9}{1.375}\approx 1.4545\times 10^9\text{instr/s}.$ CPI se divide kyun? Har instruction ab $1.375$ cycles khaati hai, isliye har second mein kam finish hoti hain.

Verify: $1.4545\times 10^9\times 1.375\approx 2\times 10^9$ ✓ (raw cycle rate par wapas). Ideal throughput hota $2\times 10^9$; hame uska $1/1.375=72.7\%$ milta hai.

---

Example 4 — Cell F: forwarding stalls mitaa deta hai

Forecast: forwarding kitna CPI wapas kharid leta hai?

Step 1 — CPI without forwarding. ${\text{CPI}}_{no}=1+0.30\times 2=\mathrm{1.60.}$

Step 2 — CPI with forwarding. Stalls $0$ ho jaate hain: ${\text{CPI}}_{fwd}=1+0.30\times 0=\mathrm{1.00.}$ Zero kyun? EX result seedha next EX input ko diya jaata hai, isliye koi writeback ka wait nahi karta.

Step 3 — Cycles saved per instruction. $1.60-1.00=\mathrm{0.60.}$

Verify: speedup $=1.60/1.00=1.60\times$ — forwarding yahan poora hazard penalty recover kar leta hai, parent note ke claim se exactly match karta hai. ✓

---

Example 5 — Cell G: behtar branch prediction

Forecast: $50\%\to 90\%$ accurate jaane se kitne CPI points bachte hain?

Step 1 — Accuracy ko mispredict rate mein convert karo. Mispredict $=1-\text{accuracy}$: toh $0.50$ aur $0.10$. Flip kyun? Penalties un branches se aate hain jinhe hum galat predict karte hain, sahi se nahi.

Step 2 — CPI at 50% accuracy. $1+0.20\times 0.50\times 3=1+0.30=\mathrm{1.30.}$

Step 3 — CPI at 90% accuracy. $1+0.20\times 0.10\times 3=1+0.06=\mathrm{1.06.}$

Step 4 — Improvement. $1.30-1.06=0.24\text{CPI saved}.$

Verify: throughput ratio $=1.30/1.06\approx 1.226$ → ek $\sim 22.6\%$ throughput gain. ✓

---

Example 6 — Cells H & I: degenerate aur extreme inputs

Forecast: (a) ke liye, koi speedup hai bhi kya?

Step 1 — (a) $k=1$. Total cycles $=k+(n-1)=1+(n-1)=n$, toh CPI $=1$ hai lekin koi overlap nahi — yeh hai hi single-cycle machine. Degenerate result kyun? Ek stage ke saath pipeline karne ke liye kuch nahi hai; single-cycle pe speedup $=1\times$.

Step 2 — (b) balanced, no overhead. $T_{single}=4\times 100=400,T_{pipe}=100+0=100,\text{Speedup}=\frac{400}{100}=4=k.$ Exactly $k$ kyun? Perfect balance aur zero overhead ideal limit hai — speedup stage count tak pahunchta hai.

Step 3 — (c) zero-hazard floor. ${\text{CPI}}_{min}=1+0=1.$ CPI scalar pipeline ke liye $1$ se neeche kabhi nahi ja sakta (ek finish per cycle max) — yeh sirf Example 7 mein badalta hai.

Step 4 — (d) all-hazard worst case. $\text{CPI}=1+1.00\times 2=3.$ $1.00$ kyun? "Har" instruction hazard karti hai → hazard rate $=1$. Yeh $2$-cycle-stall wali duniya ka ceiling hai.

Verify: (a) speedup $400/400=1$ agar us single stage ne same $400$ ps sum kiya — pipelining mein kuch change na ho toh kuch nahi badlta ✓. (b) $4=k$ ✓. (d) $3=1+2$ ✓.

---

Example 7 — Cell J: superscalar, CPI 1 se neeche (real-world)

Forecast: kya ek single instruction sach mein cycle ka quarter le sakti hai?

Step 1 — IPC, CPI ka reciprocal hai. $\text{IPC}=\frac{1}{\text{CPI}}=\frac{1}{0.25}=4\text{instructions/cycle}.$ Reciprocal kyun? CPI cycles-per-instruction hai; use flip karo instructions-per-cycle paane ke liye.

Step 2 — Throughput. $4.0\times 10^9\text{cycles/s}\times 4\text{instr/cycle}=16\times 10^9\text{instr/s}.$

Step 3 — CPI < 1 kyun? Koi single instruction faster nahi hai — core sirf ek hi cycle mein 4–6 instructions issue karta hai multiple execution units use karke. Average karne par, har instruction ek cycle share karti hai, isliye per-instruction cycle count $1$ se neeche aa jaata hai.

Verify: $16\times 10^9/4\times 10^9=4$ IPC ✓; aur $1/4=0.25$ CPI ✓.

---

Example 8 — Cell K: exam trap "kaun sa faster hai?"

Forecast: flashy $5$ GHz chip — winner ya bait?

Step 1 — Performance $=$ clock rate ÷ CPI. $P:\frac{5.0\times 10^9}{4.0}=1.25\times 10^9\text{instr/s}.$ $Q:\frac{3.0\times 10^9}{1.0}=3.0\times 10^9\text{instr/s}.$ CPI se divide kyun? Raw GHz sirf cycles count karta hai; cycles-per-instruction se divide karke hi yeh kaam hone mein badalta hai.

Step 2 — Compare karo. $Q$ $3.0\times 10^9$ deliver karta hai $P$ ke $1.25\times 10^9$ ke mukable — Q faster hai.

Step 3 — Kitna zyada. $\frac{3.0\times 10^9}{1.25\times 10^9}=2.4\times .$

Verify: P par $N$ instructions ka time $=N\times 4.0/(5\times 10^9)=8\times 10^{-10}N$ s; Q par $=N\times 1.0/(3\times 10^9)\approx 3.33\times 10^{-10}N$ s. Ratio $=8/3.33\approx 2.4$ ✓ — "slower-clocked" chip $2.4\times$ se jeetta hai. Yeh iron law ek punch mein hai.

---

Recall Self-test

Ideal k-stage pipe mein bahut saari instructions ke limit mein CPI ::: 1 Pipeline clock period formula ::: $\max (t_i)+t_{reg}$ Superscalar CPI < 1 kyun de sakta hai ::: woh ek cycle mein multiple instructions issue karta hai (IPC > 1) Faster kaun: 5 GHz CPI=4 ya 3 GHz CPI=1 ::: 3 GHz wala (performance = rate ÷ CPI) Forwarding se cycles saved per instruction jab 30% hazard, 2-cycle stall ::: 0.60