Pipeline throughput and CPI

5.2.9 · Hardware › Processor Datapath & Pipelining

Overview

Pipeline throughput measure karta hai ki ek pipelined processor kitne instructions complete karta hai per unit time, jabki CPI (Cycles Per Instruction) quantify karta hai average number of clock cycles jo ek instruction execute karne mein lagte hain. Ye metrics reveal karte hain kitni efficiently hamara pipeline clock speed ko actual work mein convert karta hai.

Fundamental Definitions

CPI kyun, sirf clock speed kyun nahi? Kyunki ek 5 GHz processor jiska CPI=4 hai wo slower hai ek 3 GHz processor se jiska CPI=1 hai. Real performance = $\frac{\text{Clock Rate}}{\text{CPI}}$.

Ideal Pipeline Performance Derive Karna

Chalte hain performance equations ko scratch se build karte hain.

Step 1: Single-Cycle Baseline

Ek non-pipelined processor ke liye jiska clock period $T_{single}$ hai:

• Har instruction ek full cycle leti hai
• Time per instruction = $T_{single}$
• Throughput = $\frac{1}{T_{single}}$ instructions/second
• CPI = 1 (by definition)

Lekin: $T_{single}$ itna lamba hona chahiye ki slowest instruction stage ke liye fit ho. Agar hamare paas 5 stages hain jo 100ps, 120ps, 150ps, 110ps, 140ps lete hain toh $T_{single}=150$ ps (longest stage dominate karta hai).

Step 2: Pipelined Clock Period

Jab hum execution ko k stages mein split karte hain, har stage ka delay $t_i$ hota hai. Pipeline clock period ko slowest stage plus register overhead $t_{reg}$ accommodate karna chahiye:

$T_{pipe}=\max (t_1,t_2,\dots ,t_k)+t_{reg}$

Max kyun? Saare stages same clock edge par advance karte hain. Slowest stage bottleneck hota hai — jaise assembly line par sabse slow worker line ki speed determine karta hai.

$t_{reg}$ kyun add karte hain? Stages ke beech pipeline registers ko new data latch karne ke liye time chahiye (setup time + clock-to-Q delay). Typical $t_{reg}$ 20-50 ps hota hai.

Step 1: Slowest stage dhundho. $\max (80,70,100,90,60)=100\text{ ps (EX stage)}$

Step 2: Register overhead add karo. $T_{pipe}=100+30=130\text{ ps}$

Ye step kyun? Clock itna slow hona chahiye ki EX complete ho aur register apna output capture kare next cycle shuru hone se pehle.

Comparison ke liye, single-cycle ko chahiye hoga: $T_{single}=80+70+100+90+60=400$ ps (sabhi stages ka sum, koi overlap nahi).

Step 3: Ideal Throughput

Ek k-stage pipeline mein, initial "fill-up" period ke baad, har cycle mein ek instruction complete hoti hai. Ye key insight hai:

${\text{Throughput}}_{ideal}=\frac{1}{T_{pipe}}\text{ instructions/second}$ ${\text{CPI}}_{ideal}=1$

Derivation: $n$ instructions execute karne ko consider karo (jahan $n\gg k$):

• Pehli instruction $k$ cycles leti hai sabhi stages se flow through karne mein
• Lekin jab wo stage 2 mein hai, instruction 2 stage 1 mein enter karti hai
• $k$ cycles ke baad, instruction 1 finish hoti hai; $k+1$ cycles ke baad, instruction 2 finish hoti hai
• Total time = $k+(n-1)$ cycles ≈ $n$ cycles large $n$ ke liye
• Isliye: CPI = $\frac{k+n-1}{n}\approx 1$ as $n\to \infty$

Best case mein (perfectly balanced stages, negligible $t_{reg}$), speedup ≈ k hota hai. Practice mein, ek 5-stage pipeline ke liye speedup 3-4× hota hai stage imbalance aur register delays ki wajah se.

Real Pipeline Performance: Hazards aur Stalls

Real pipelines CPI=1 achieve nahi karti kyunki hazards hote hain jo stalls (idle cycles) force karte hain.

Types of Stalls

1. Data hazards: RAW (Read After Write) dependencies
2. Control hazards: Branch mispredictions
3. Structural hazards: Resource conflicts (modern designs mein rare)

Actual CPI Formula

${\text{CPI}}_{actual}={\text{CPI}}_{ideal}+\text{Stalls per Instruction}$

Kyunki pipelines ke liye ${\text{CPI}}_{ideal}=1$ hota hai:

${\text{CPI}}_{actual}=1+\text{Stalls per Instruction}$

Stalls ko break down karna: $\text{Stalls per Instruction}=(\text{Data Hazard Rate}\times \text{Avg Data Stalls})+(\text{Branch Rate}\times \text{Branch Mispredict Rate}\times \text{Branch Penalty})$

Branches se stalls calculate karo: $\text{Branch Stalls/Instr}=0.25\times 0.10\times 3=0.075\text{ cycles/instr}$ Kyun? 25% branches hain, unme se 10% mispredict hote hain, har ek 3 cycles cost karta hai.

Data hazard stalls calculate karo: $\text{Data Stalls/Instr}=0.15\times 2=0.30\text{ cycles/instr}$

Total CPI: $\text{CPI}=1+0.075+0.30=1.375$

Actual throughput (agar clock = 2GHz hai): $\text{Throughput}=\frac{2\times 10^9}{1.375}=1.45\text{ billion instructions/second}$

CPI > 1 kyun hurt karta hai? CPI mein har 0.1 ka increase throughput ko ~9% reduce kar deta hai (CPI ke liye near 1). Wo 0.375 overhead ka matlab hai ki hum sirf 73% ideal throughput pa rahe hain.

Pipeline Performance Optimize Karna

1. Stage Delays Balance Karo

Problem: Agar ek stage 150ps leta hai aur baaki 80ps lete hain, toh poora pipeline 150ps par chalta hai.

Solution: Slow stage ko subdivide karo. Agar EX 150ps leta hai, toh ise EX1 (75ps) aur EX2 (75ps) mein split karo. Ab clock period 150ps se 80ps par drop ho jaata hai (agar ID next slowest hai), throughput 1.875× improve hoti hai.

Trade-off: Zyada stages = zyada register overhead. 10-15 stages se aage diminishing returns milte hain.

2. Forwarding se Stalls Reduce Karo

Forwarding (bypassing) results ko directly ek stage se doosre mein pass karta hai bina writeback ka wait kiye.

Example:

ADD R1, R2, R3  # R1 = R2 + R3 (EX stage produces result)
SUB R4, R1, R5  # Needs R1 (ID stage reads it)

Forwarding ke bina: 2-cycle stall (ADD ke WB tak pahunchne ka wait karo). Forwarding ke saath: 0 stalls (EX→EX bypass path).

CPI par impact: Agar 30% instructions mein RAW hazards hain, forwarding CPI ko 1.60 se 1.00 tak reduce karta hai (0.6 cycles/instr bachata hai).

3. Branch Prediction Improve Karo

Static prediction (always predict not-taken): ~60% accuracy. Dynamic prediction (branch history table): ~90-95% accuracy.

Impact: Agar 20% instructions branches hain with 3-cycle penalty:

• 50% mispredict: CPI = 1 + 0.20×0.50×3 = 1.30
• 10% mispredict: CPI = 1 + 0.20×0.10×3 = 1.06

Prediction ko 50% se 90% tak improve karne se CPI 0.24 reduce hoti hai (18% throughput gain).

Effective IPC = 1/0.25 = 4 instructions per cycle.

Throughput: $\text{Throughput}=4.0\times 10^9\times 4=16\text{ billion instructions/second}$

CPI < 1 kaise? Superscalar execution: processor ke paas multiple execution units hain aur wo 4-6 instructions per cycle issue karta hai. Ye simple pipelining se aage hai — ye instruction-level parallelism hai.

Common Mistakes

Reality ye hai: Har instruction abhi bhi k cycles leti hai (latency unchanged). Jo improve hota hai wo hai throughput — instructions zyada frequently complete hoti hain, individually faster nahi.

Example: Ek 5-stage pipeline jisme har stage 1ns leti hai:

• Latency per instruction = 5ns (same as non-pipelined agar $T_{single}=5$ ns ho)
• Lekin throughput = 1 instruction per ns (vs. 1 per 5ns non-pipelined)

Fix: "Assembly line" socho. Ek car banane mein abhi bhi ghante lagte hain, lekin har minute ek car bahar nikalti hai.

Reality ye hai: CPI measure karta hai cycles per instruction completed, na per stage. Ek ideal pipeline mein, ek instruction har cycle complete hoti hai, toh CPI=1 hota hai regardless of k.

Correct formulas:

• Latency (ek instruction ke liye cycles) = k
• CPI (cycles per completed instruction) = 1 (ideal)

Fix: Latency aur throughput ko confuse mat karo. CPI steady-state throughput measure karta hai, na first-instruction delay.

Reality ye hai: $\text{Speedup}=\frac{T_{single}}{T_{pipe}}=\frac{\sum t_i}{\max (t_i)+t_{reg}}$

Agar stages unbalanced hain (jaise ek total time ka 50% leta hai), toh speedup k se kaafi kam hogi. Plus, register overhead gains ko erode karta hai.

Example: 5 stages (100, 50, 50, 50 ps), $t_{reg}=20$ ps:

• $T_{single}=300$ ps
• $T_{pipe}=100+20=120$ ps
• Speedup = 300/120 = 2.5× (5× nahi)

Fix: Speedup balance par depend karta hai. Perfectly balanced stages bina overhead ke k× ke kareeb pahuncha sakti hain, lekin real designs 60-80% of k achieve karti hain.

Advanced Considerations

Superscalar aur CPI < 1

Modern processors multiple instructions per cycle issue karte hain. Ek 4-way superscalar perfect conditions mein CPI = 0.25 (IPC = 4) achieve kar sakta hai.

Kaise?

• Multiple execution units (jaise 2 ALUs, 1 FPU, 2 load/store units)
• Issue logic instruction window mein independent instructions dhundta hai
• Har "cycle" mein 4 instructions parallel mein complete hoti hain

Limitation: Instruction-level parallelism (ILP). Real code mein dependencies hoti hain jo limit karti hain kitni instructions simultaneously execute ho sakti hain. Typical IPC = 2-3 even with 6-way superscalar hardware.

Amdahl's Law aur Pipeline Efficiency

Perfect pipelining ke saath bhi, overall speedup non-pipelined parts se limited hoti hai (Amdahl's Law). Agar execution time ka 20% pipeline fill/drain (prologue/epilogue) mein hai, toh maximum speedup 5× hai.

Pipelining ke bina: Tum ek load wash karte ho, use dry hone ka wait karte ho, fold karte ho, rakh dete ho. Phir next load start karte ho. 4 loads ka time = 4 × (30×4) = 480 minutes (8 ghante).

Pipelining ke saath: Jab load 1 dry ho raha hai, tum load 2 wash karna shuru kar dete ho. Jab load 1 fold ho raha hai, load 2 dry hota hai aur load 3 wash hota hai. Pehle 2 ghante (4 stages) ke baad, tum har 30 minutes mein ek load finish karte ho.

4 loads ka time = 120 (pehla load) + 3×30 (baaki loads) = 210 minutes (3.5 ghante). Speedup = 480/210 = 2.3×.

CPI: Steady state mein, tum har "cycle" (30 min) mein ek load complete karte ho, toh CPI = 1.

4× speedup kyun nahi? Pehla load abhi bhi full 120 minutes leta hai (latency), aur hamare paas sirf 4 loads hain (small n). 100 loads ke saath, speedup 4× ke kareeb pahuncha jaata.

Stalls: Agar tum detergent khareedna bhool gaye (data hazard), washing ruk jaati hai. Ab loads 2, 3, 4 delay ho jaate hain. CPI increase hoti hai kyunki ab tum har 30 minutes mein ek load complete nahi kar rahe.

Connections

• 5.2.01-Pipelining-basics: Pipelining kaise kaam karta hai uska foundation
• 5.2.03-Data-hazards: CPI > 1 ka main cause
• 5.2.05-Control-hazards: Branch penalties throughput reduce karte hain
• 5.2.07-Forwarding-and-bypassing: CPI improve karne ki key technique
• 5.3.02-Superscalar-architecture: CPI < 1 achieve karna
• 5.1.05-CPU-performancemetrics: CPI overall performance equation mein kaise fit hota hai

#flashcards/hardware

What is pipeline throughput? :: Wo rate jis par instructions complete hoti hain, measured in instructions per second. Ek ideal pipeline ke liye, throughput = 1/T_pipe instructions/second.

What is IPC and how does it relate to CPI? :: IPC (Instructions Per Cycle) = 1/CPI. IPC throughput directly measure karta hai (higher is better), jabki CPI cycle cost per instruction measure karta hai (lower is better).

Concept Map