Pipeline throughput and CPI

Overview

Pipeline throughput measures how many instructions a pipelined processor completes per unit time, while CPI (Cycles Per Instruction) quantifies the average number of clock cycles needed to execute one instruction. These metrics reveal how efficiently our pipeline converts clock speed into actual work.

Fundamental Definitions

Why CPI and not just clock speed? Because a5 GHz processor with CPI=4 is slower than a 3 GHz processor with CPI=1. Real performance = $\frac{\text{Clock Rate}}{\text{CPI}}$.

Deriving Ideal Pipeline Performance

Let's build the performance equations from scratch.

Step 1: Single-Cycle Baseline

For a non-pipelined processor with clock period $T_{single}$:

• Each instruction takes one full cycle
• Time per instruction = $T_{single}$
• Throughput = $\frac{1}{T_{single}}$ instructions/second
• CPI = 1 (by definition)

But: $T_{single}$ must be long enough for the slowest instruction stage. If we have5 stages taking 100ps, 120ps, 150ps, 110ps, 140 then $T_{single} = 150$ ps (the longest stage dominates).

Step 2: Pipelined Clock Period

When we split execution into k stages, each stage has delay $t_i$. The pipeline clock period must accommodate the slowest stage plus register overhead $t_{reg}$:

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

Why the max? All stages advance on the same clock edge. The slowest stage is the bottleneck—like the slowest worker on an assembly line determines the line's speed.

Why add $t_{reg}$? Pipeline registers between stages need time to latch new data (setup time + clock-to-Q delay). Typical $t_{reg}$ is 20-50 ps.

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

Step 2: Add register overhead. $T_{pipe} = 100 + 30 = 130 \text{ ps}$

Why this step? The clock must be slow enough that EX completes and the register captures its output before the next cycle starts.

For comparison, single-cycle would need: $T_{single} = 80+70+100+90+60 = 400$ ps (sum of all stages, no overlap).

Step 3: Ideal Throughput

In a k-stage pipeline, after an initial "fill-up" period, one instruction completes every cycle. This is the key insight:

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

Derivation: Consider executing $n$ instructions (where $n \gg k$):

• First instruction takes $k$ cycles to flow through all stages
• But while it's in stage2, instruction 2 enters stage 1
• After $k$ cycles, instruction 1 finishes; after $k+1$ cycles, instruction 2 finishes
• Total time = $k + (n-1)$ cycles ≈ $n$ cycles for large $n$
• Therefore: CPI = $\frac{k + n - 1}{n} \approx 1$ as $n \to \infty$

In the best case (perfectly balanced stages, negligible $t_{reg}$), speedup ≈ k. In practice, speedup is 3-4× for a 5-stage pipeline due to stage imbalance and register delays.

Real Pipeline Performance: Hazards and Stalls

Real pipelines don't achieve CPI=1 because of hazards that force stalls (idle cycles).

Types of Stalls

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

Actual CPI Formula

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

Since $\text{CPI}_{ideal} = 1$ for pipelines:

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

Breaking down stalls: $\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})$

Calculate stalls from branches: $\text{Branch Stalls/Instr} = 0.25 \times 0.10 \times 3 = 0.075 \text{ cycles/instr}$ Why? 25% are branches, 10% of those mispredict, each costs 3 cycles.

Calculate data hazard stalls: $\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 (if clock = 2GHz): $\text{Throughput} = \frac{2 \times 10^9}{1.375} = 1.45 \text{ billion instructions/second}$

Why does CPI > 1 hurt? Every 0.1 increase in CPI reduces throughput by ~9% (for CPI near 1). That0.375 overhead means we're only getting 73% of ideal throughput.

Optimizing Pipeline Performance

1. Balance Stage Delays

Problem: If one stage takes 150ps and others take 80ps, the entire pipeline runs at 150ps.

Solution: Subdivide the slow stage. If EX takes 150ps, split it into EX1 (75ps) and EX2 (75ps). Now clock period drops from 150ps to 80ps (if ID is next slowest), improving throughput by 1.875×.

Trade-off: More stages = more register overhead. Diminishing returns beyond 10-15 stages.

2. Reduce Stalls via Forwarding

Forwarding (bypassing) passes results directly from one stage to another without waiting for writeback.

Example:

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

Without forwarding: 2-cycle stall (wait for ADD to reach WB). With forwarding: 0 stalls (EX→EX bypass path).

Impact on CPI: If30% of instructions have RAW hazards, forwarding reduces CPI from 1.60 to 1.00(saves 0.6cycles/instr).

3. Improve Branch Prediction

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

Impact: If 20% instructions are branches 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

Improving prediction from 50% to 90% reduces CPI by 0.24 (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}$

How CPI < 1? Superscalar execution: processor has multiple execution units and issues4-6 instructions per cycle. This is beyond simple pipelining—it's instruction-level parallelism.

Common Mistakes

The reality: Each instruction still takes k cycles (latency unchanged). What improves is throughput—instructions complete more frequently, not faster individually.

Example: A 5-stage pipeline with 1ns per stage:

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

Fix: Think "assembly line." A car still takes hours to build, but one rolls off every minute.

The reality: CPI measures cycles per instruction completed, not per stage. In an ideal pipeline, one instruction completes every cycle, so CPI=1 regardless of k.

Correct formulas:

• Latency (cycles for one instruction) = k
• CPI (cycles per completed instruction) = 1 (ideal)

Fix: Don't confuse latency with throughput. CPI measures steady-state throughput, not first-instruction delay.

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

If stages are unbalanced (e.g., one takes 50% of total time), speedup is much less than k. Plus, register overhead erodes gains.

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× (not 5×)

Fix: Speedup depends on balance. Perfectly balanced stages with no overhead approaches k×, but real designs get60-80% of k.

Advanced Considerations

Superscalar and CPI < 1

Modern processors issue multiple instructions per cycle. A 4-way superscalar with perfect conditions can achieve CPI = 0.25 (IPC = 4).

How?

• Multiple execution units (e.g., 2 ALUs, 1 FPU, 2 load/store units)
• Issue logic finds independent instructions in the instruction window
• Each "cycle" completes 4 instructions in parallel

Limitation: Instruction-level parallelism (ILP). Real code has dependencies limiting how many instructions can execute simultaneously. Typical IPC = 2-3even with 6-way superscalar hardware.

Amdahl's Law and Pipeline Efficiency

Even with perfect pipelining, overall speedup is limited by non-pipelined parts (Amdahl's Law). If 20% of execution time is in pipeline fill/drain (prologue/epilogue), maximum speedup is 5×.

Without pipelining: You wash one load, wait for it to dry, fold it, put it away. Then start the next load. Time for4 loads = 4 × (30×4) = 480 minutes (8 hours).

With pipelining: While load 1 is drying, you start washing load 2. While load 1 is being folded, load 2 dries and load 3 washes. After the first2 hours (4 stages), you finish one load every 30 minutes.

Time for 4 loads = 120 (first load) + 3×30 (remaining loads) = 210 minutes (3.5 hours). Speedup = 480/210 = 2.3×.

CPI: In steady state, you complete one load per "cycle" (30 min), so CPI = 1.

Why not 4× speedup? The first load still takes full120 minutes (latency), and we only have 4 loads (small n). With 100loads, speedup approaches 4×.

Stalls: If you forgot to buy detergent (data hazard), washing stops. Now loads2, 3, 4 are delayed. CPI increases because you're not completing one load every30 minutes anymore.

Connections

• 5.2.01-Pipelining-basics: Foundation of how pipelining works
• 5.2.03-Data-hazards: Main cause of CPI > 1
• 5.2.05-Control-hazards: Branch penalties reduce throughput
• 5.2.07-Forwarding-and-bypassing: Key technique to improve CPI
• 5.3.02-Superscalar-architecture: Achieving CPI < 1
• 5.1.05-CPU-performancemetrics: CPI fits into overall performance equation

#flashcards/hardware

What is pipeline throughput? :: The rate at which instructions complete, measured instructions per second. For an ideal pipeline, throughput = 1/T_pipe instructions/second.

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

Concept Map

Hinglish (regional understanding)