Pipelining the CPU in RTL
Our
single-cycle
CPU with its control unit works — and wastes almost everything it owns. During the 900
ps it spends on one instruction, the instruction memory works for 250 ps and idles for 650; the ALU
works for 200 and idles for 700. Five expensive stations, each busy a fifth of the time. The fix is
the oldest trick in manufacturing, the
assembly
line: cut the sweep into five stages — IF, ID, EX, MEM, WB — put a
register between each pair, and let five instructions travel the datapath at once, each
occupying a different station. Same silicon, same program — and a clock nearly five times faster.
Cutting the sweep: pipeline registers
Where exactly do we cut? At the natural seams of the walk: after fetch (IF/ID),
after decode and register read (ID/EX), after the ALU (EX/MEM),
and after data memory (MEM/WB). Each cut is a plain bank of flip-flops — an
always_ff like any other — whose job is to hold one instruction's intermediate world
while the stage behind it starts on the next instruction. Critically, each register carries
data and control together: the values read so far and the instruction's
control bundle, because the signals decoded back in ID will be needed by muxes two or three stages
downstream:
// One pipeline register, as a packed struct: DATA and CONTROL travel together.
typedef struct packed {
logic [31:0] pc, a, b, imm; // values read in ID
logic [4:0] rd; // the destination, needed all the way in WB
ctl_t ctl; // the whole control bundle rides along
} id_ex_t;
id_ex_t id_ex;
always_ff @(posedge clk)
if (!rst_n) id_ex <= '0; // an all-zero bundle = a harmless NOP
else id_ex <= id_ex_next;
// The top level reshapes from one big sweep into five short ones:
// IF: pc, imem -> if_id
// ID: decode, regfile read -> id_ex (control is BORN here)
// EX: alu -> ex_mem (control bundle shrinks)
// MEM: dmem -> mem_wb
// WB: write-back mux -> regfile write port
Control is born once, in ID, exactly as last lesson — and then rides the pipeline,
each stage peeling off the signals it consumes: EX uses alu_src/alu_op,
MEM uses mem_read/mem_write, WB uses
reg_write/mem_to_reg. The bundle physically shrinks as it travels — a
pleasing detail: by MEM/WB only two bits of it are left alive.
The arithmetic that pays for it all
The single-cycle clock had to span the whole 900 ps walk. Now each stage only has to span
itself — at worst the slowest station, 250 ps, plus the pipeline register's own overhead
(say 40 ps of clock-to-Q and setup):
T_{clk} \approx 250 + 40 = 290\ \text{ps} \quad\text{vs}\quad 900\ \text{ps} \;\Rightarrow\; \text{about } 3.1\times \text{ today, } \approx 5\times \text{ with balanced stages}
Two honest footnotes live in that formula. The clock is set by the slowest stage,
so unbalanced stages squander the win — real designs sweat to equalise them (and our 250 ps
memories are the obvious next target). And the register overhead is pure tax, paid five times per
instruction where the single-cycle design paid it once. Cut a pipeline ever finer and the tax
dominates — one reason the megahertz-chasing 31-stage pipelines of the mid-2000s were abandoned.
Reading the flow
The pipeline's life story is best told as a table of who is where, when. Here are seven
instructions (the exact program from the code block below) flowing through — each row a cycle,
each column a stage:
Read any row: five different instructions at work simultaneously. Read any
diagonal: one instruction marching IF → ID → EX → MEM → WB, taking five cycles for its
personal journey. Both readings are true at once — that is the whole trick.
The model: five stages in the two-phase simulator
In the simulator, pipelining means one thing: the State grows four new members — the
pipeline registers — and next() computes each stage from the current registers,
committing all of them at once. Note the stage order inside next() is written WB
first, IF last: every stage must consume the pre-edge values, exactly like hardware
(this is the non-blocking-assignment discipline wearing a TypeScript costume). We run a deliberately
hazard-free program — every value read is at least three instructions old:
// ── Assembler + decoder + control (recap of lessons 34 and 37, compact). ──
function R(f7: number, f3: number, rd: number, rs1: number, rs2: number): number {
return ((f7 << 25) | (rs2 << 20) | (rs1 << 15) | (f3 << 12) | (rd << 7) | 0x33) | 0;
}
function I(op: number, f3: number, rd: number, rs1: number, imm: number): number {
return (((imm & 0xfff) << 20) | (rs1 << 15) | (f3 << 12) | (rd << 7) | op) | 0;
}
const asm = {
ADD: (rd: number, rs1: number, rs2: number) => R(0x00, 0, rd, rs1, rs2),
ADDI: (rd: number, rs1: number, imm: number) => I(0x13, 0, rd, rs1, imm),
};
interface Decoded { name: string; rd: number; rs1: number; rs2: number; imm: number; useRs2: boolean }
function decode(w: number): Decoded {
const opcode = w & 0x7f, rd = (w >> 7) & 0x1f, f3 = (w >> 12) & 7;
const rs1 = (w >> 15) & 0x1f, rs2 = (w >> 20) & 0x1f, f7 = (w >>> 25) & 0x7f;
if (opcode === 0x33)
return { name: f3 === 0 ? (f7 === 0x20 ? "SUB" : "ADD") : f3 === 7 ? "AND" : "OR", rd, rs1, rs2, imm: 0, useRs2: true };
return { name: "ADDI", rd, rs1, rs2, imm: w >> 20, useRs2: false }; // (subset: ALU ops only today)
}
interface Ctl { RegWrite: number; ALUSrc: number; ALUOp: string }
function control(d: Decoded): Ctl {
return { RegWrite: 1, ALUSrc: d.name === "ADDI" ? 1 : 0, ALUOp: d.name === "ADDI" ? "ADD" : d.name };
}
// ── Four pipeline registers join pc/regs in the state. ──
interface IFID { pc: number; word: number }
interface IDEX { pc: number; name: string; rd: number; a: number; b: number; imm: number; c: Ctl }
interface EXMEM { pc: number; name: string; rd: number; alu: number; c: Ctl }
interface MEMWB { pc: number; name: string; rd: number; val: number; c: Ctl }
interface State {
pc: number; regs: number[];
if_id: IFID | null; id_ex: IDEX | null; ex_mem: EXMEM | null; mem_wb: MEMWB | null;
}
function next(s: State, imem: number[]): State {
const regs = s.regs.slice();
// WB — writes land in the first half of the cycle, so ID below reads fresh values.
if (s.mem_wb && s.mem_wb.c.RegWrite && s.mem_wb.rd !== 0) regs[s.mem_wb.rd] = s.mem_wb.val;
// MEM — nothing to do for ALU ops; just pass the result along.
const mem_wb: MEMWB | null = s.ex_mem
? { pc: s.ex_mem.pc, name: s.ex_mem.name, rd: s.ex_mem.rd, val: s.ex_mem.alu, c: s.ex_mem.c }
: null;
// EX — the ALU.
let ex_mem: EXMEM | null = null;
if (s.id_ex) {
const e = s.id_ex, b = e.c.ALUSrc ? e.imm : e.b;
const alu = e.c.ALUOp === "SUB" ? (e.a - b) | 0 : e.c.ALUOp === "AND" ? e.a & b : e.c.ALUOp === "OR" ? e.a | b : (e.a + b) | 0;
ex_mem = { pc: e.pc, name: e.name, rd: e.rd, alu, c: e.c };
}
// ID — decode once; the control bundle rides along from here.
let id_ex: IDEX | null = null;
if (s.if_id) {
const d = decode(s.if_id.word);
id_ex = { pc: s.if_id.pc, name: d.name, rd: d.rd, a: regs[d.rs1], b: regs[d.rs2], imm: d.imm, c: control(d) };
}
// IF — fetch (until the program runs out).
const word = imem[s.pc >> 2];
const if_id: IFID | null = word === undefined ? null : { pc: s.pc, word };
return { pc: s.pc + 4, regs, if_id, id_ex, ex_mem, mem_wb };
}
// ── A deliberately hazard-FREE program (every value is ≥3 instructions old when read). ──
const imem = [
asm.ADDI(1, 0, 5), // I0: x1 = 5
asm.ADDI(2, 0, 7), // I1: x2 = 7
asm.ADDI(3, 0, 9), // I2: x3 = 9
asm.ADDI(4, 0, 11), // I3: x4 = 11
asm.ADD(5, 1, 2), // I4: x5 = x1 + x2 (x1 four back, x2 three back: safe)
asm.ADDI(7, 0, 100), // I5: x7 = 100 (independent filler)
asm.ADD(6, 3, 4), // I6: x6 = x3 + x4 (x3 four back, x4 three back: safe)
];
const tag = (x: { pc: number } | null | undefined) => (x ? "I" + (x.pc >> 2) : ".");
let s: State = { pc: 0, regs: new Array(32).fill(0), if_id: null, id_ex: null, ex_mem: null, mem_wb: null };
console.log("cycle | IF ID EX MEM WB");
console.log("------+---------------------");
for (let cycle = 0; ; cycle++) {
const fetching = imem[s.pc >> 2] !== undefined ? { pc: s.pc } : null;
console.log(
` ${String(cycle).padStart(2)} | ${[fetching, s.if_id, s.id_ex, s.ex_mem, s.mem_wb].map((x) => tag(x).padStart(3)).join(" ")}`,
);
if (!fetching && !s.if_id && !s.id_ex && !s.ex_mem && !s.mem_wb) break;
s = next(s, imem);
}
console.log(`\nx5 = ${s.regs[5]} (12?) x6 = ${s.regs[6]} (20?) x7 = ${s.regs[7]} (100?)`);
// ── The cliffhanger: a DEPENDENT pair, same machinery. ──
const imem2 = [asm.ADDI(1, 0, 5), asm.ADDI(2, 0, 7), asm.ADD(3, 1, 2)];
let t: State = { pc: 0, regs: new Array(32).fill(0), if_id: null, id_ex: null, ex_mem: null, mem_wb: null };
for (let cycle = 0; cycle < 8; cycle++) t = next(t, imem2);
console.log(`\nDependent pair: x3 = ${t.regs[3]} — expected 5 + 7 = 12. The pipeline just computed garbage…`);
Seven instructions, eleven cycles, correct results — and then the sting in the tail. The dependent
pair at the bottom (addi x1 immediately consumed by add x3, x1, x2)
sails through the same machinery and computes 0 instead of 12. Nothing crashed:
add simply read x1 and x2 in ID before the
addis ahead of it had written them back. Our pipeline is fast and wrong for
any program with closely-spaced dependencies — which is to say, every real program. That bug has a
name — a data hazard — and fixing it in hardware is the entire next lesson.
A common trap: "five stages, so each instruction now finishes five times sooner." Backwards —
each individual instruction now takes five short cycles instead of one long one, roughly
the same wall-clock journey (a touch worse, thanks to the register tax). What improves — by
nearly 5× — is throughput: instructions completed per second, because
one retires every cycle instead of every 900 ps. The distinction matters everywhere in
computing: adding checkout lanes serves more shoppers per hour without making any single
shopper's queue-to-door time shorter. When a datasheet brags about pipeline depth, it is
promising throughput — never latency.
If 5 stages give ~5×, why not 50? Intel tried. The Pentium 4's NetBurst pipeline reached 31
stages chasing clock frequency as a marketing number — and collided with physics from every
side: the per-stage register tax stopped shrinking, mispredicted branches meant refilling a
31-stage pipe (a catastrophe we will taste, in miniature, next lesson), and 3.8 GHz of switching
turned the die into a hotplate. The industry retreated to ~12–20 stages and spent its transistors
on width (several instructions per cycle) and smarter prediction instead. Depth is a dial, not a
virtue — our five stages sit at the classic sweet spot where the textbooks, and a great many real
embedded cores, still live.