# Pipelining — Stages, Speedup, Throughput and Hazards (Structural, Data, Control) with Solved Numericals

Source: https://skills101.in/learn/coa/pipelining-hazards — Skills101 free tutorial (Computer Organisation & Architecture (COA)). Updated 2026-11-09.

Washing clothes: wash (30 min), dry (40 min), fold (20 min). Doing 4 loads one after another takes 6 hours. But you can start washing load 2 while load 1 dries — that's **pipelining**, and it's how every modern CPU executes several instructions at once.

## 1. The 5-stage pipeline

| Stage | Name | Does |
|---|---|---|
| **IF** | Instruction Fetch | read instruction at PC |
| **ID** | Instruction Decode | decode, read registers |
| **EX** | Execute | ALU operation / address calculation |
| **MEM** | Memory | load/store data memory |
| **WB** | Write Back | write the result into a register |

![Pipeline timing diagram: instruction 1 goes through IF, ID, EX, MEM, WB in cycles 1 to 5; instruction 2 starts one cycle later, and so on, so after the pipeline fills one instruction finishes every cycle](https://skills101.in/learn-img/coa/pipeline-stages.svg)

Each instruction still takes 5 cycles (**latency** unchanged), but once the pipeline is full, **one instruction completes every cycle** (**throughput** up to 5×).

## 2. The speedup formula

With **k** stages, **n** instructions, and each stage taking time **t**:

- Non-pipelined: `n × k × t`
- Pipelined: `(k + n − 1) × t` — k cycles for the first instruction, then one more per instruction
- **Speedup = n·k / (k + n − 1)** → approaches **k** as n grows

```python
def speedup(k, n):
    return n * k / (k + n - 1)

for n in [1, 5, 100, 10_000]:
    print(f"k=5, n={n:6}: cycles pipelined = {5 + n - 1:6}, speedup = {speedup(5, n):.3f}")
```

```text
k=5, n=     1: cycles pipelined =      5, speedup = 1.000
k=5, n=     5: cycles pipelined =      9, speedup = 2.778
k=5, n=   100: cycles pipelined =    104, speedup = 4.808
k=5, n= 10000: cycles pipelined =  10004, speedup = 4.998
```

## 3. Unequal stages and latch delay

Real stages don't take equal time. The clock must fit the **slowest stage plus the pipeline register (latch) delay**.

**Example.** Stage delays 150, 120, 160, 140, 130 ps; latch delay 10 ps; 1000 instructions.

```python
stages = [150, 120, 160, 140, 130]
latch = 10
n = 1000

non_pipelined = n * sum(stages)
cycle = max(stages) + latch
pipelined = (len(stages) + n - 1) * cycle

print("clock cycle =", cycle, "ps")
print("non-pipelined:", non_pipelined, "ps | pipelined:", pipelined, "ps")
print(f"speedup = {non_pipelined / pipelined:.2f} (ideal would be {len(stages)})")
```

```text
clock cycle = 170 ps
non-pipelined: 700000 ps | pipelined: 170680 ps
speedup = 4.10 (ideal would be 5)
```

Speedup is well below 5 because the stages are unbalanced and latches add delay — which is why designers try to **balance stages**.

## 4. Hazards: why pipelines stall

A **hazard** prevents the next instruction from running in its slot. Three kinds:

### Structural hazard — fighting over hardware

Two instructions need the same unit in the same cycle — e.g. one memory for both instruction fetch and data access. Fix: duplicate resources (**separate instruction and data caches** — the Harvard idea from lesson 1).

### Data hazard — waiting for a result

```text
ADD R1, R2, R3     ; R1 = R2 + R3      (result written in WB, cycle 5)
SUB R4, R1, R5     ; needs R1 in ID/EX (cycle 3/4) — not ready yet!
```

Types: **RAW** (read after write — the real one in simple pipelines), WAR and WAW (matter in out-of-order CPUs).

Fixes:
- **Stall** (insert bubbles) until the value is written.
- **Forwarding / bypassing** — send the ALU result straight from the EX/MEM pipeline register to the next instruction's EX input. Removes most stalls.
- **Load-use hazard**: a value loaded from memory isn't available until after MEM, so even with forwarding the next instruction stalls **1 cycle**. Compilers reorder instructions to fill that slot.

![Data hazard and forwarding: without forwarding SUB waits for ADD's write-back with two bubble cycles; with forwarding the ALU result goes directly from ADD's execute stage to SUB's execute stage and no stall is needed](https://skills101.in/learn-img/coa/pipeline-hazard.svg)

### Control hazard — branches

After a branch, which instruction comes next isn't known until the branch is resolved (EX stage in our pipeline). Fixes:
- **Stall** until resolved (branch penalty).
- **Branch prediction** — guess (e.g. "loops usually repeat"), fetch along the guess, and flush if wrong. Modern predictors are right well over 90% of the time.
- **Delayed branch** — the instruction after the branch always executes (older RISC designs).

## 5. Effective CPI with stalls

**Speedup = pipeline depth / (1 + stall cycles per instruction)** (ideal CPI 1).

```python
def effective_cpi(branch_freq, mispredict_rate, penalty, load_use_freq=0.0, load_stall=1):
    return 1 + branch_freq * mispredict_rate * penalty + load_use_freq * load_stall

no_pred = effective_cpi(0.20, 1.0, 2)                 # stall on every branch
predictor = effective_cpi(0.20, 0.10, 2)              # 90% accurate predictor
with_loads = effective_cpi(0.20, 0.10, 2, 0.15, 1)    # plus 15% load-use stalls

for name, cpi in [("always stall", no_pred), ("90% predictor", predictor), ("predictor + load-use", with_loads)]:
    print(f"{name:22} CPI = {cpi:.2f}  speedup over non-pipelined 5-stage = {5 / cpi:.2f}")
```

```text
always stall           CPI = 1.40  speedup over non-pipelined 5-stage = 3.57
90% predictor          CPI = 1.04  speedup over non-pipelined 5-stage = 4.81
predictor + load-use   CPI = 1.19  speedup over non-pipelined 5-stage = 4.20
```

## 6. Beyond the basic pipeline

- **Superscalar** — multiple pipelines; issue 2–8 instructions per cycle.
- **Out-of-order execution** — run later independent instructions while earlier ones wait.
- **Deeper pipelines** allow higher clocks but bigger branch penalties.
- **Multicore** — several complete CPUs on one chip (parallelism at the thread level).

## Common mistakes

- Using `n·k` cycles for the pipelined case (it's `k + n − 1`).
- Forgetting latch delay or using the average stage delay instead of the **maximum**.
- Assuming forwarding removes the load-use stall (it leaves 1 cycle).
- Saying pipelining reduces the latency of one instruction (it improves **throughput**).

## Quick recap

- 5 stages: IF, ID, EX, MEM, WB; pipelining raises throughput, not single-instruction latency.
- Pipelined time = (k + n − 1) × cycle; speedup = nk/(k+n−1) → k.
- Cycle = slowest stage + latch delay.
- Hazards: **structural** (duplicate resources), **data** (stall, forwarding; load-use costs 1), **control** (stall, prediction, delayed branch).
- CPI = 1 + stall cycles per instruction.


Practice quiz and free certificate: https://skills101.in/learn/coa/pipelining-hazards