Instruction Pipelining

in reviewThis lesson is complete and being validated before release - details may still change.

Five-stage pipeline

Loading interactive demo…

The grid is a pipeline diagram: one row per instruction as it runs, one column per clock cycle, each cell the stage the instruction is in that cycle. A held decode reads as a stall, a squashed instruction ends in a cross, and the finished diagram is drawn faint. The listing beside it is the program with the instruction being fetched lit. Tap a row to read that instruction's timing.Take the tour, or press and explore. Legend:

The panel beside the stage is the real Pipeline class from the published library executing in your browser, with the current line highlighted.

The current cycle.
Fetch and decode.
Execute.
Memory.
Write back: the instruction completes.
A stall, or a squashed instruction.

cycle counts clock ticks, completed the instructions through write back, CPI their ratio, and stalls, forwards, and squashed the hazards met so far.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Overlap. The tiny CPU's three moves became five stages here: fetch, decode, execute, memory, write back. An instruction spends one cycle in each, so its latency is five cycles, unchanged. But the stages are separate hardware, so while one instruction executes the next can decode and the one after it can be fetched. In steady state every stage is busy and one instruction finishes per cycle: a throughput five times the unpipelined machine's with the same latency. The registers between stages are the flip-flops of two lessons ago, clocked together.

Cycles per instruction. For $n$ independent instructions in a $k$ -stage pipeline, the first finishes after $k$ cycles and the rest one per cycle: $n + k - 1$ cycles in all, so

\text{CPI} = \frac{n + k - 1}{n} \to 1 .

Four instructions in five stages take eight cycles, a CPI of two; a hundred take 104. The fill and the drain are a fixed cost that a long program amortises. Hazards add to the numerator.

Data hazards. The second instruction of the default program reads $r1$ , which the first writes. The first computes $r1$ in execute during cycle 3 and writes it in cycle 5; the second wants it in decode during cycle 3. Without help, decode must hold still until write back has happened, two cycles of stall, and a bubble travels down the pipe in its place. Each stall is a cycle in which the pipeline finishes nothing.

Forwarding. The value exists at the end of execute. A wire from the output of execute, and another from the output of memory, back into the input of execute lets the dependent instruction take it directly, a cycle before write back would have delivered it. With forwarding the chain runs with no stalls at all. The one case it cannot fix is a load followed by its use: the value arrives from memory at the end of the memory stage, one cycle too late for an execute that starts right after the load's. One stall remains, and a compiler tries to put an unrelated instruction in that slot.

Control hazards. A branch is resolved in execute, two cycles after it was fetched, and fetch has not waited: two more instructions are in the pipe by then. If the branch is taken they are the wrong ones, and they are squashed, their partial work thrown away, as fetch restarts at the target. Each taken branch here costs two cycles. Deeper pipelines resolve branches later and pay more per branch, which is the Pentium 4's lesson and the reason the next lesson exists: a predictor that guesses the target before the branch resolves turns most of that cost into nothing.

Where the time goes. Read the CPI as the diagram fills. The independent program approaches one; the dependent chain without forwarding sits far above it; the loop pays for every taken branch. A processor's design is the sum of what it does about each of these rows.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

step resolves a branch before it checks for data hazards, because a squashed instruction in decode must not stall anything; then it advances every stage at once, the way one clock edge moves every pipeline register.
An instruction is described by what it reads and writes, a destination and sources, not by what it computes. Hazards are a property of names, and that is all the pipeline needs to know.
A hazard is detected in decode against execute and memory only. Write back is excluded because the register file is written and read in the same cycle, which is itself a small forwarding trick.
Forwarding is a flag, and the load-use case is the one test that stays a stall with it on: writer === executing && kind === "load".
A branch carries its outcomes as data, consumed each time it is fetched, so the loop runs its body a fixed number of times without the pipeline interpreting anything.
The timeline records the last cycle an instance spent in each stage, so a stall shows as decode lasting several cycles and a squashed instance simply has no later stages.

The tiny CPU finished one instruction before fetching the next, so most of its hardware sat idle most of the time. Overlapping the stages, so that one instruction is fetched while another decodes and a third executes, is older than the microprocessor: IBM's Stretch did it in 1961 and Seymour Cray's CDC 6600 in 1964. The 1980s RISC projects at Berkeley and Stanford designed instruction sets so that every instruction fit the same five stages, and the pipeline on this stage is theirs. Hazards, the moments when overlapping breaks, are what the rest of processor design is about.

1961IBM - The 7030 Stretch overlaps instruction fetch and execution, an early pipeline, and coins the word 'byte' along the way.source
1964Seymour Cray and Control Data - The CDC 6600 issues instructions to ten functional units with a scoreboard tracking the hazards between them.source
1981John Hennessy and the Stanford MIPS group - MIPS, a Microprocessor without Interlocked Pipeline Stages, designs the instruction set around a fixed pipeline and leaves the hazards to the compiler.source
1990John Hennessy and David Patterson - Computer Architecture: A Quantitative Approach makes the five-stage pipeline, its hazards, and forwarding the standard way the subject is taught.source
2004Intel - The Pentium 4 Prescott stretches its pipeline to 31 stages for clock speed, and the cost of each squashed branch shows why the industry turned back.source
2017John Hennessy and David Patterson - Receive the Turing Award for the quantitative approach to processor design that the pipelined RISC machines embodied.source

Used today

Every processor - A modern core pipelines over a dozen stages and issues several instructions per cycle; the hazards on this stage are the ones it still resolves.
GPUs and signal processors - Deep pipelines over many identical operations are what make graphics and media hardware fast.
Compilers - Instruction scheduling reorders a program so that dependent instructions are far enough apart to need no stall.

program

forwarding

cycle: 14 of 14
completed: 4
CPI: 3.50
stalls: 6
forwards: 0
squashed: 0

pipeline.ts

import type { Tracer } from "../trace";/** The classic five stages, in order. */export const STAGES = ["IF", "ID", "EX", "MEM", "WB"] as const;export type Stage = (typeof STAGES)[number];export type InstructionKind = "alu" | "load" | "store" | "branch";/** One instruction of a small register machine, described by what it reads and writes. */export interface PipelineInstruction {  text: string;  kind: InstructionKind;  /** The register written in WB, or null. */  dst: string | null;  /** The registers read in ID (or forwarded into EX). */  src: readonly string[];  /** A branch: where it goes when taken, and what it does each time it executes, first execution first. */  branch?: { target: number; outcomes: readonly boolean[] };}export interface PipelineOptions {  /** Pass results from EX and MEM straight to the next instruction's EX, so only a load-use pair stalls. */  forwarding: boolean;}/** One dynamic instance of an instruction: which static instruction, and the nth time it ran. */export interface Instance {  id: number;  instruction: number;}export interface CycleState {  cycle: number;  /** The instance in each stage, by stage name; null for a bubble. */  stages: Record<Stage, number | null>;}export interface PipelineReport {  cycles: number;  instructions: number;  stalls: number;  forwards: number;  flushes: number;  /** Cycles per instruction completed. */  cpi: number;  /** Every instance, in fetch order, with the cycle each stage ran in; a squashed instance ends early. */  timeline: { id: number; instruction: number; squashed: boolean; cycles: Partial<Record<Stage, number>> }[];}export const MAX_PIPELINE_CYCLES = 64;export const MAX_PROGRAM = 16;interface Slot {  id: number;  instruction: PipelineInstruction;  index: number;  /** Which branch outcome this instance consumed, if a branch. */  taken: boolean;}/** * A five-stage pipeline: fetch, decode, execute, memory, write back. * Every cycle each instruction moves one stage on, so five run at * once and one finishes per cycle, until a hazard. A data hazard is an * instruction in decode that reads a register an earlier instruction * has not yet written: without forwarding it waits until the writer * reaches write back; with forwarding the result is passed from EX or * MEM straight into its EX, and only a load, whose value exists after * MEM, costs a cycle. A control hazard is a branch: fetch keeps going * past it, and when the branch resolves taken in EX the two * instructions fetched behind it are squashed and fetch restarts at * the target. * * Time: O(cycles). Space: O(instances). */export class Pipeline {  private readonly slots: [Slot | null, Slot | null, Slot | null, Slot | null, Slot | null] = [null, null, null, null, null];  private readonly pending: Slot[] = [];  private readonly timeline = new Map<number, PipelineReport["timeline"][number]>();  private readonly outcomeIndex: number[];  private pc = 0;  private nextId = 0;  private cycle = 0;  private stalls = 0;  private forwards = 0;  private flushes = 0;  private completed = 0;  constructor(    private readonly program: readonly PipelineInstruction[],    private readonly options: PipelineOptions,    private readonly tracer?: Tracer,  ) {    if (program.length === 0 || program.length > MAX_PROGRAM) throw new RangeError(`a program is 1 to ${MAX_PROGRAM} instructions`);    for (const instruction of program) {      if (instruction.kind === "branch" && !instruction.branch) throw new RangeError(`branch "${instruction.text}" has no target`);      if (instruction.branch && (instruction.branch.target < 0 || instruction.branch.target > program.length)) throw new RangeError(`branch "${instruction.text}" targets outside the program`);    }    this.outcomeIndex = program.map(() => 0);  }  /** Runs until the pipeline drains or the cycle cap is hit. */  run(): PipelineReport {    // An instruction completes in its write-back cycle, so the run ends once nothing is left before WB.    while (this.cycle < MAX_PIPELINE_CYCLES && (this.pc < this.program.length || this.slots.slice(0, 4).some((slot) => slot !== null))) this.step();    const instances = [...this.timeline.values()].sort((a, b) => a.id - b.id);    return { cycles: this.cycle, instructions: this.completed, stalls: this.stalls, forwards: this.forwards, flushes: this.flushes, cpi: this.completed === 0 ? 0 : this.cycle / this.completed, timeline: instances };  }  /** One clock cycle: resolve a branch in EX, decide whether ID must wait, then advance every stage. */  step(): CycleState {    this.cycle++;    const executing = this.slots[2];    const memory = this.slots[3];    // A taken branch in EX squashes what fetch and decode hold and redirects fetch.    if (executing?.instruction.kind === "branch" && executing.taken) {      const squashed = [this.slots[0], this.slots[1]].flatMap((slot) => (slot ? [slot.id] : []));      for (const id of squashed) this.timeline.get(id)!.squashed = true;      this.flushes += squashed.length;      this.slots[0] = null;      this.slots[1] = null;      this.pc = executing.instruction.branch!.target;      // ▸ a branch in execute is taken: squash what fetch and decode hold and fetch from the target      this.tracer?.emit("flush", { cycle: this.cycle, branch: executing.id, squashed, target: this.pc });    }    // A data hazard: decode reads a register that EX or MEM will write later.    let stalled = false;    const reader = this.slots[1];    const decodingInstruction = this.slots[1];    if (reader) {    if (decodingInstruction) {      const writers = [executing, memory].filter((slot): slot is Slot => slot !== null && slot !== reader && slot.instruction.dst !== null && reader.instruction.src.includes(slot.instruction.dst ?? ""));      const producersAhead = [executing, memory].filter((slot): slot is Slot => slot !== null && slot !== decodingInstruction && slot.instruction.dst !== null && decodingInstruction.instruction.src.includes(slot.instruction.dst ?? ""));      for (const writer of writers) {      for (const writer of producersAhead) {        const loadInExecute = writer === executing && writer.instruction.kind === "load";        if (!this.options.forwarding || loadInExecute) {          stalled = true;          this.stalls++;          // ▸ decode needs a register an earlier instruction has not written yet, and nothing can hand it over: wait a cycle          this.tracer?.emit("stall", { cycle: this.cycle, waiting: reader.id, on: writer.id, reason: loadInExecute ? "load-use" : "data", register: writer.instruction.dst });          this.tracer?.emit("stall", { cycle: this.cycle, waiting: decodingInstruction.id, on: writer.id, reason: loadInExecute ? "load-use" : "data", register: writer.instruction.dst });          break;        }        this.forwards++;        // ▸ the value exists in execute or memory, so pass it straight to the waiting instruction's execute        this.tracer?.emit("forward", { cycle: this.cycle, from: writer.id, to: reader.id, stage: writer === executing ? "EX" : "MEM", register: writer.instruction.dst });        this.tracer?.emit("forward", { cycle: this.cycle, from: writer.id, to: decodingInstruction.id, stage: writer === executing ? "EX" : "MEM", register: writer.instruction.dst });      }    }    // Advance: the instruction entering WB completes this cycle, the rest shift; a stall holds IF and ID and sends a bubble into EX.    // Decode is read after the flush, so a squashed instruction never moves on.    this.slots[4] = memory;    if (memory) this.completed++;    this.slots[3] = executing;    if (stalled) {      this.slots[2] = null;    } else {      this.slots[2] = this.slots[1];      this.slots[1] = this.slots[0];      this.slots[0] = this.fetch();    }    this.slots.forEach((slot, i) => {      if (slot) this.timeline.get(slot.id)!.cycles[STAGES[i]!] = this.cycle;    });    const stages = Object.fromEntries(STAGES.map((stage, i) => [stage, this.slots[i]?.id ?? null])) as Record<Stage, number | null>;    // ▸ the clock ticks: every instruction moves one stage on, and the one in write back is done    this.tracer?.emit("cycle", { cycle: this.cycle, stages, stalled, completed: this.completed });    return { cycle: this.cycle, stages };  }  /** The next instruction as a new instance, or nothing once the program is past its end. */  private fetch(): Slot | null {    const instruction = this.program[this.pc];    if (!instruction) return null;    const index = this.pc;    let taken = false;    if (instruction.branch) {      const outcomes = instruction.branch.outcomes;      taken = outcomes[Math.min(this.outcomeIndex[index]!, outcomes.length - 1)] ?? false;      this.outcomeIndex[index]!++;    }    const slot: Slot = { id: this.nextId++, instruction, index, taken };    this.timeline.set(slot.id, { id: slot.id, instruction: index, squashed: false, cycles: {} });    this.pc++;    return slot;  }}

cycles =: 14
cpi =: 3.50

4 instructions in 14 cycles: 3.50 cycles per instruction, with 6 stalls, 0 forwards, and 0 squashed.

import type { Tracer } from "../trace";/** The classic five stages, in order. */export const STAGES = ["IF", "ID", "EX", "MEM", "WB"] as const;export type Stage = (typeof STAGES)[number];export type InstructionKind = "alu" | "load" | "store" | "branch";/** One instruction of a small register machine, described by what it reads and writes. */export interface PipelineInstruction { text: string; kind: InstructionKind; /** The register written in WB, or null. */ dst: string | null; /** The registers read in ID (or forwarded into EX). */ src: readonly string[]; /** A branch: where it goes when taken, and what it does each time it executes, first execution first. */ branch?: { target: number; outcomes: readonly boolean[] };}export interface PipelineOptions { /** Pass results from EX and MEM straight to the next instruction's EX, so only a load-use pair stalls. */ forwarding: boolean;}/** One dynamic instance of an instruction: which static instruction, and the nth time it ran. */export interface Instance { id: number; instruction: number;}export interface CycleState { cycle: number; /** The instance in each stage, by stage name; null for a bubble. */ stages: Record<Stage, number | null>;}export interface PipelineReport { cycles: number; instructions: number; stalls: number; forwards: number; flushes: number; /** Cycles per instruction completed. */ cpi: number; /** Every instance, in fetch order, with the cycle each stage ran in; a squashed instance ends early. */ timeline: { id: number; instruction: number; squashed: boolean; cycles: Partial<Record<Stage, number>> }[];}export const MAX_PIPELINE_CYCLES = 64;export const MAX_PROGRAM = 16;interface Slot { id: number; instruction: PipelineInstruction; index: number; /** Which branch outcome this instance consumed, if a branch. */ taken: boolean;}/** * A five-stage pipeline: fetch, decode, execute, memory, write back. * Every cycle each instruction moves one stage on, so five run at * once and one finishes per cycle, until a hazard. A data hazard is an * instruction in decode that reads a register an earlier instruction * has not yet written: without forwarding it waits until the writer * reaches write back; with forwarding the result is passed from EX or * MEM straight into its EX, and only a load, whose value exists after * MEM, costs a cycle. A control hazard is a branch: fetch keeps going * past it, and when the branch resolves taken in EX the two * instructions fetched behind it are squashed and fetch restarts at * the target. * * Time: O(cycles). Space: O(instances). */export class Pipeline { private readonly slots: [Slot | null, Slot | null, Slot | null, Slot | null, Slot | null] = [null, null, null, null, null]; private readonly pending: Slot[] = []; private readonly timeline = new Map<number, PipelineReport["timeline"][number]>(); private readonly outcomeIndex: number[]; private pc = 0; private nextId = 0; private cycle = 0; private stalls = 0; private forwards = 0; private flushes = 0; private completed = 0; constructor( private readonly program: readonly PipelineInstruction[], private readonly options: PipelineOptions, private readonly tracer?: Tracer, ) { if (program.length === 0 || program.length > MAX_PROGRAM) throw new RangeError(`a program is 1 to ${MAX_PROGRAM} instructions`); for (const instruction of program) { if (instruction.kind === "branch" && !instruction.branch) throw new RangeError(`branch "${instruction.text}" has no target`); if (instruction.branch && (instruction.branch.target < 0 || instruction.branch.target > program.length)) throw new RangeError(`branch "${instruction.text}" targets outside the program`); } this.outcomeIndex = program.map(() => 0); } /** Runs until the pipeline drains or the cycle cap is hit. */ run(): PipelineReport { // An instruction completes in its write-back cycle, so the run ends once nothing is left before WB. while (this.cycle < MAX_PIPELINE_CYCLES && (this.pc < this.program.length || this.slots.slice(0, 4).some((slot) => slot !== null))) this.step(); const instances = [...this.timeline.values()].sort((a, b) => a.id - b.id); return { cycles: this.cycle, instructions: this.completed, stalls: this.stalls, forwards: this.forwards, flushes: this.flushes, cpi: this.completed === 0 ? 0 : this.cycle / this.completed, timeline: instances }; } /** One clock cycle: resolve a branch in EX, decide whether ID must wait, then advance every stage. */ step(): CycleState { this.cycle++; const executing = this.slots[2]; const memory = this.slots[3]; // A taken branch in EX squashes what fetch and decode hold and redirects fetch. if (executing?.instruction.kind === "branch" && executing.taken) { const squashed = [this.slots[0], this.slots[1]].flatMap((slot) => (slot ? [slot.id] : [])); for (const id of squashed) this.timeline.get(id)!.squashed = true; this.flushes += squashed.length; this.slots[0] = null; this.slots[1] = null; this.pc = executing.instruction.branch!.target; // ▸ a branch in execute is taken: squash what fetch and decode hold and fetch from the target this.tracer?.emit("flush", { cycle: this.cycle, branch: executing.id, squashed, target: this.pc }); } // A data hazard: decode reads a register that EX or MEM will write later. let stalled = false; const reader = this.slots[1]; const decodingInstruction = this.slots[1]; if (reader) { if (decodingInstruction) { const writers = [executing, memory].filter((slot): slot is Slot => slot !== null && slot !== reader && slot.instruction.dst !== null && reader.instruction.src.includes(slot.instruction.dst ?? "")); const producersAhead = [executing, memory].filter((slot): slot is Slot => slot !== null && slot !== decodingInstruction && slot.instruction.dst !== null && decodingInstruction.instruction.src.includes(slot.instruction.dst ?? "")); for (const writer of writers) { for (const writer of producersAhead) { const loadInExecute = writer === executing && writer.instruction.kind === "load"; if (!this.options.forwarding || loadInExecute) { stalled = true; this.stalls++; // ▸ decode needs a register an earlier instruction has not written yet, and nothing can hand it over: wait a cycle this.tracer?.emit("stall", { cycle: this.cycle, waiting: reader.id, on: writer.id, reason: loadInExecute ? "load-use" : "data", register: writer.instruction.dst }); this.tracer?.emit("stall", { cycle: this.cycle, waiting: decodingInstruction.id, on: writer.id, reason: loadInExecute ? "load-use" : "data", register: writer.instruction.dst }); break; } this.forwards++; // ▸ the value exists in execute or memory, so pass it straight to the waiting instruction's execute this.tracer?.emit("forward", { cycle: this.cycle, from: writer.id, to: reader.id, stage: writer === executing ? "EX" : "MEM", register: writer.instruction.dst }); this.tracer?.emit("forward", { cycle: this.cycle, from: writer.id, to: decodingInstruction.id, stage: writer === executing ? "EX" : "MEM", register: writer.instruction.dst }); } } // Advance: the instruction entering WB completes this cycle, the rest shift; a stall holds IF and ID and sends a bubble into EX. // Decode is read after the flush, so a squashed instruction never moves on. this.slots[4] = memory; if (memory) this.completed++; this.slots[3] = executing; if (stalled) { this.slots[2] = null; } else { this.slots[2] = this.slots[1]; this.slots[1] = this.slots[0]; this.slots[0] = this.fetch(); } this.slots.forEach((slot, i) => { if (slot) this.timeline.get(slot.id)!.cycles[STAGES[i]!] = this.cycle; }); const stages = Object.fromEntries(STAGES.map((stage, i) => [stage, this.slots[i]?.id ?? null])) as Record<Stage, number | null>; // ▸ the clock ticks: every instruction moves one stage on, and the one in write back is done this.tracer?.emit("cycle", { cycle: this.cycle, stages, stalled, completed: this.completed }); return { cycle: this.cycle, stages }; } /** The next instruction as a new instance, or nothing once the program is past its end. */ private fetch(): Slot | null { const instruction = this.program[this.pc]; if (!instruction) return null; const index = this.pc; let taken = false; if (instruction.branch) { const outcomes = instruction.branch.outcomes; taken = outcomes[Math.min(this.outcomeIndex[index]!, outcomes.length - 1)] ?? false; this.outcomeIndex[index]!++; } const slot: Slot = { id: this.nextId++, instruction, index, taken }; this.timeline.set(slot.id, { id: slot.id, instruction: index, squashed: false, cycles: {} }); this.pc++; return slot; }}