Lesson 4: CPU Pipelining & Data Hazards

Opening: overlap, instead of forcing every instruction to the slowest one's pace

Lesson 3 ended on a thorny pitfall: a single-cycle datapath forces ALL instructions — even a simple ADD — to run at the pace of the SLOWEST one (LW). The fix is not "slow ADD down to be fair" but the opposite: split each instruction into 5 steps (stages) and let several instructions OVERLAP — the next instruction starts step 1 the moment the previous one finishes step 1. This is pipelining, and the price of overlapping is that instructions "running in parallel" sometimes need each other's DATA — a data hazard.

1. How a 5-stage pipeline works

Every RV32I instruction passes through exactly 5 steps: IF (Instruction Fetch — read the instruction), ID (Instruction Decode — decode and read registers), EX (Execute — compute through the ALU), MEM (Memory access — only LW/SW really use it), WB (Write Back — write the result into a register). A pipeline gives each stage its OWN hardware block, joined by pipeline registers — so while instruction A is in EX, instruction B (fetched exactly 1 cycle after A) can already be in ID, and instruction C can be in IF — all three instructions are "alive" inside the CPU AT THE SAME TIME.

Cycle:       1    2    3    4    5    6    7
Instr A:     IF   ID   EX   MEM  WB
Instr B:          IF   ID   EX   MEM  WB
Instr C:               IF   ID   EX   MEM  WB

# At cycle 3: A is in EX, B is in ID, C is in IF - ALL THREE instructions
# are "alive" inside the CPU at once, each in a DIFFERENT stage.

2. Computing pipeline performance

This section leans on two words constantly, so let us define both. First, a stall (also called a bubble) is a cycle in which the pipeline gets NO useful work done: the hardware has to wait, usually because a later instruction needs data an earlier one has not produced yet. It is an empty slot travelling down the assembly line — still costing a clock tick, but yielding no product.

Second, CPI stands for Cycles Per Instruction — the average number of cycles the CPU spends on ONE instruction. It is the central measure of this whole lesson, so it helps to see both ends of it:

• CPI = 1 is the ideal for a 5-stage pipeline: exactly one instruction completes every cycle, with no stalls. It cannot go lower — there is only one WB port per cycle to write a result through.
• CPI = 1.2 means each instruction costs 1.2 cycles on average — i.e. every 5 instructions lose one extra cycle to stalls. Higher is worse; $CPI = 2$ means the pipeline is running at half its capacity.

The time to run $N$ instructions on an $S$-stage pipeline with clock period $t_{clk}$ and $stallCycles$ extra stall cycles caused by hazards:

$$T = (N + S - 1 + stallCycles) \times t_{clk}$$

The $(S-1)$ term is the "fill" latency at start-up — the first 4 cycles (with $S=5$) do not yet have all 5 instructions overlapping. Verified with real numbers: 1 million instructions, a 5-stage pipeline, a 2GHz clock ($t_{clk}=0.5$ns) — with NO stalls it takes exactly 500,002 ns; the SAME program with 200,000 stall cycles (from hazards, say) takes 600,002 ns — a difference of exactly $200{,}000 \times 0.5\text{ns} = 100{,}000\text{ns}$.

function pipelineTime(numInstructions, numStages, stallCycles, clockPeriodNs) {
  return (numInstructions + numStages - 1 + stallCycles) * clockPeriodNs;
}
function pipelineCPI(numInstructions, stallCycles) {
  return (numInstructions + stallCycles) / numInstructions; // ideal CPI is 1
}
// Verified: pipelineTime(1_000_000, 5, 0, 0.5) === 500002 (ns)
// Verified: pipelineTime(1_000_000, 5, 200_000, 0.5) === 600002 (ns)
// Verified: pipelineCPI(1_000_000, 200_000) === 1.2 (ideal CPI would be 1)

3. Data hazards

When a later instruction OVERLAPS an earlier one, it may need to read or write a register the earlier one is also reading or writing — three classic conflicts:

Forwarding (also called operand bypassing): instead of WAITING for the earlier instruction to write its register and then reading it back, the ALU result takes a "shortcut" straight from the earlier instruction's EX output into the later instruction's EX input — verified: the real 3-instruction RV32I chain ADDI x1,x0,20 / ADD x2,x1,x1 / SUB x3,x2,x1 (two back-to-back RAW hazards) gives exactly 0 stalls WITH forwarding — not a single cycle lost; with forwarding OFF, each hazard needs exactly 2 stalls (waiting until WB completes), for a total of 4 stalls.

function detectHazards(instrs, forwardingEnabled) {
  let totalStalls = 0;
  const hazards = [];
  for (let i = 1; i < instrs.length; i++) {
    const prev = instrs[i - 1], curr = instrs[i];
    const prevWritesReg =
      (prev.type === 'R' || prev.type === 'I' || prev.type === 'ILOAD') && prev.rd !== 0;
    if (!prevWritesReg) continue;
    const reads = curr.rs1 === prev.rd || curr.rs2 === prev.rd;
    if (!reads) continue;
    if (prev.type === 'ILOAD') { totalStalls += 1; /* load-use: ALWAYS 1 stall */ }
    else if (!forwardingEnabled) { totalStalls += 2; /* plain RAW, no forwarding */ }
    // forwarding on AND not load-use -> 0 stalls, nothing to add
  }
  return { totalStalls, hazards };
}
// Verified on a real RAW chain: forwarding ON -> 0 stalls; OFF -> 4 stalls.

4. Working a real example & counting stalls

The pipeline clock grid for the load-use example — the 1 stall verified above appears as the ADD's EX stage being delayed by exactly one cycle, waiting for data from the LW's MEM stage:

Straight from the formula: 2 instructions, 5 stages, 1 stall → $T = (2+5-1+1) = 7$ cycles — matching the last column in the table above (the ADD's WB lands in cycle 7). The actual CPI of this 2-instruction snippet: $CPI = (2+1)/2 = 1.5$ — well above the ideal $CPI=1$, because the stall's share of a short snippet is very large (exactly the pitfall raised in Section 2).

const seq = [
  assembleRV32I('LW',  { rd: 1, rs1: 2, imm: 0 }),
  assembleRV32I('ADD', { rd: 3, rs1: 1, rs2: 1 }),
].map(decodeRV32I);
const { totalStalls } = detectHazards(seq, true); // forwarding ON, still 1 stall

// Passing 1 as the clock period makes the result a CYCLE COUNT. Pass the real
// t_clk (e.g. 0.5) instead and the same call returns nanoseconds: 7 * 0.5 = 3.5.
const cycles = pipelineTime(2, 5, totalStalls, 1);   // = 7 cycles
const nanoseconds = pipelineTime(2, 5, totalStalls, 0.5); // = 3.5 ns
const cpi = pipelineCPI(2, totalStalls);             // = 1.5
// Verified: totalStalls=1, cycles=(2+5-1+1)=7, nanoseconds=3.5, CPI=(2+1)/2=1.5

5. Hands-on: an interactive RISC-V 5-stage pipeline simulation

The time/CPI calculator below uses EXACTLY the verified formula — change the instruction count, stall count or clock period to watch $T$ and CPI move directly. The hazard simulator lets you switch forwarding on and off across 2 real RV32I sequences (RAW and load-use) so you can watch the stall count change exactly as Section 3 described:

Summary

• ✅ A pipeline overlaps many instructions across 5 stages (IF-ID-EX-MEM-WB) to raise THROUGHPUT; it does not shorten the latency of one single instruction.
• ✅ Verified: $T=(N+S-1+stall) \times t_{clk}$ — 1 million instructions with no stalls = 500,002 ns, with 200,000 stalls = 600,002 ns at 2GHz.
• ✅ RAW is the only REAL hazard in a basic pipeline (WAR/WAW are automatically ordered correctly by reading early at ID, writing late at WB, and in-order commit).
• ✅ Verified: forwarding fully solves ALU-to-ALU RAW hazards (0 stalls); without forwarding each hazard costs 2 stalls.
• ✅ Pitfall: a load-use hazard (LW then immediate use) CANNOT be rescued by forwarding — verified to always need exactly 1 stall.

Review quiz