Pipelining and Hazards
Instead of finishing one instruction before starting the next, a pipelined CPU overlaps the stages of consecutive instructions, like an assembly line.
Concept
The Pipeline Idea Instead of finishing one instruction before starting the next, a pipelined CPU overlaps the stages of consecutive instructions, like an assembly line. The classic RISC pipeline has five stages:
Decode, read registers ALU operation / address calculation Data memory access Write the result back to a register
Ideally one instruction completes every cycle (CPI = 1) even though each takes 5 cycles (latency). Pipelining improves throughput, not the latency of a single instruction. Modern cores have 14–20+ stages so that each stage is short and the clock fast.
Anything that prevents the next instruction from entering the pipeline in the next cycle:
Two instructions need the same hardware in the same cycle Duplicate resources (separate instruction and data caches)
An instruction needs a result that isn't written back yet (RAW: read after write)
Forwarding/bypassing results from EX or MEM directly to the next instruction; stalls (bubbles) when forwarding can't help, e.g. the load-use hazard; compiler instruction scheduling
The next instruction's address depends on a branch outcome Branch prediction + speculation (Module 25), delay slots (old MIPS)
WAR and WAW hazards (write after read/write) appear once instructions can execute out of order; they are removed by register renaming (Module 25).
Instruction-Level Parallelism (ILP) Independent instructions can overlap even inside one execution unit: a floating-point adder with a 4-cycle latency can accept a new addition every cycle. Code with a long dependency chain (every operation needs the previous result) runs at the *latency* rate; code with independent operations runs at the *throughput* rate. Compilers (and programmers) expose ILP with loop unrolling and multiple accumulators.
Why It Matters
Pipeline behaviour explains why dependent code is slow, why compilers reorder instructions, why branch mispredictions are expensive, and why "number of instructions" is a poor predictor of run time.
Syntax
Pipeline diagrams list instructions vertically and cycles horizontally; -- marks a stall (bubble).
CPI = 1 + stall cycles per instruction
Speedup (ideal) = pipeline depthExample
24.1 A 5-stage pipeline with and without forwarding 24.2 Latency-bound vs throughput-bound: one accumulator vs four
The array fits in the L1 cache so that memory isn't the bottleneck; auto-vectorization is disabled to measure the scalar adder.
"""Classic 5-stage pipeline (IF ID EX MEM WB): timing diagrams with and without forwarding."""
PROGRAM = [ # (text, destination, sources, is_load)
("lw x1, 0(x10)", "x1", [], True),
("add x2, x1, x3", "x2", ["x1"], False), # needs x1 right after the load: load-use hazard
("sub x4, x2, x5", "x4", ["x2"], False), # needs x2 from the previous instruction
("or x6, x7, x8", "x6", [], False), # independent
("and x9, x4, x6", "x9", ["x4", "x6"], False),
]
def schedule(forwarding):
"""Return the cycle in which each instruction enters EX (1-based cycle numbers)."""
ex_cycle, ready = [], {} # ready[reg] = first cycle in which a consumer may be in EX
for i, (_, dest, srcs, is_load) in enumerate(PROGRAM):
earliest = 3 + i if not ex_cycle else ex_cycle[-1] + 1 # in order: one after the previous EX
for s in srcs:
earliest = max(earliest, ready.get(s, 0))
ex_cycle.append(earliest)
if forwarding:
ready[dest] = earliest + (2 if is_load else 1) # load data after MEM, ALU result after EX
else:
ready[dest] = earliest + 3
…#include <stdio.h>
#include <time.h>
enum { N = 4096, REPEAT = 50000 }; /* 32 KB: fits in the L1 cache */
static double data[N];
static double ms(struct timespec a, struct timespec b) { return (b.tv_sec - a.tv_sec) * 1e3 + (b.tv_nsec - a.tv_nsec) / 1e6; }
int main(void)
{
for (int i = 0; i < N; i++) data[i] = 1.0 / (i + 1);
struct timespec t0, t1, t2;
/* one accumulator: every addition must wait for the previous one (a dependency chain) */
double s = 0;
clock_gettime(CLOCK_MONOTONIC, &t0);
for (int r = 0; r < REPEAT; r++)
for (int i = 0; i < N; i++) s += data[i];
clock_gettime(CLOCK_MONOTONIC, &t1);
/* four independent accumulators: the pipelined FP adder can work on four sums at once */
double a = 0, b = 0, c = 0, d = 0;
for (int r = 0; r < REPEAT; r++)
for (int i = 0; i < N; i += 4) { a += data[i]; b += data[i + 1]; c += data[i + 2]; d += data[i + 3]; }
clock_gettime(CLOCK_MONOTONIC, &t2);
double adds = (double)N * REPEAT;
printf("1 accumulator : %.1f ms, %.2f ns per addition (sum %.6f)\n", ms(t0, t1), ms(t0, t1) * 1e6 / adds, s);
printf("4 accumulators: %.1f ms, %.2f ns per addition (sum %.
…Expected Result
Without forwarding, each dependent instruction waits in ID until the value is written back: 6 stall cycles, 15 cycles for 5 instructions.
With forwarding, results go straight from EX/MEM to the next EX; only the load-use hazard remains (the loaded value exists only after MEM) — 1 stall.
With one accumulator every addition waits for the previous one (the FP adder's latency). Four independent accumulators let the pipelined adder work on four sums at once — about 4× faster, with the same number of additions. (The last digits of the sums differ because floating-point addition isn't associative.)
without forwarding:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
lw x1, 0(x10) IF ID EX MEM WB
add x2, x1, x3 IF ID -- -- EX MEM WB
sub x4, x2, x5 IF ID -- -- EX MEM WB
or x6, x7, x8 IF ID EX MEM WB
and x9, x4, x6 IF ID -- -- EX MEM WB
5 instructions in 15 cycles (ideal 9); stall cycles: 6
with forwarding:
1 2 3 4 5 6 7 8 9 10
lw x1, 0(x10) IF ID EX MEM WB
add x2, x1, x3 IF ID -- EX MEM WB
sub x4, x2, x5 IF ID EX MEM WB
or x6, x7, x8 IF ID EX MEM WB
and x9, x4, x6 IF ID EX MEM WB
5 instructions in 10 cycles (ideal 9); stall cycles: 11 accumulator : 239.8 ms, 1.17 ns per addition (sum 444755.194882)
4 accumulators: 56.9 ms, 0.28 ns per addition (sum 444755.194852)
speedup from instruction-level parallelism: 4.2xCommon Mistakes
Assuming a deeper pipeline is always faster (more stages = bigger misprediction penalty, more hazards).
Confusing latency (time for one instruction) with throughput (instructions per cycle).
Hand-optimizing instruction counts while ignoring dependency chains.
Best Practices
Break long dependency chains (multiple accumulators, tree reductions).
Let the compiler schedule instructions (-O2, -march=native for the target CPU).
Keep loads well ahead of their uses in hot loops (software pipelining, prefetch).
Interview Relevance
High: "explain pipelining", "what are the three kinds of hazards?", "what is forwarding?", "why does a load-use hazard need a stall even with forwarding?", "latency vs throughput?", "what is ILP?".
Practice Questions
Draw the pipeline diagram for lw x1; lw x2; add x3, x1, x2 with forwarding.
How many cycles do 100 independent instructions need on an ideal 5-stage pipeline?
Reorder the instructions of 24.1 to remove the remaining stall.
Try 2 and 8 accumulators in 24.2 and explain the results.
Quick Quiz
Q1. (Multiple choice) Which hazard remains even with full forwarding in the classic 5-stage pipeline? A) Structural B) Load-use data hazard C) WAW D) None
Answer: B (verified: one stall remains).
Q2. (Predict the output) Cycles for the 5-instruction example without forwarding?
Answer: 15 (verified).
Q3. (True/False) Pipelining reduces the time an individual instruction takes.
Answer: False. It increases throughput; each instruction still passes through every stage.
Q4. (Find the bug) "Our loop has 4 instructions per element, so it must take 4 cycles per element."
Answer: Not necessarily: a dependency chain through a 4-cycle-latency operation can dominate, or several instructions may issue per cycle.
Coding Challenge
Compute the ideal speedup of a k-stage pipeline for n instructions (n·k cycles unpipelined vs k + n − 1 cycles pipelined) for k = 5 and n = 1, 10, 100, 1 000 000.
#include <stdio.h>
int main(void)
{
int k = 5;
long ns[] = {1, 10, 100, 1000000};
for (int i = 0; i < 4; i++) {
long n = ns[i];
double speedup = (double)(n * k) / (k + n - 1);
printf("n = %7ld: unpipelined %8ld cycles, pipelined %8ld cycles, speedup %.2f\n", n, n * k, k + n - 1, speedup);
}
return 0;
}