The Pipelined Datapath

A single-cycle datapath computes every instruction in one long clock cycle, sized to accommodate the slowest instruction (typically a load: register file read, ALU address computation, memory access, and register file writeback all in series). This wastes time on every faster instruction and, more importantly, forbids starting a new instruction until the current one fully finishes. Pipelining breaks this monolithic cycle into a sequence of stages, each doing a bounded amount of work, so that a new instruction can enter the first stage every cycle while earlier instructions occupy later stages. The five classic stages are: Instruction Fetch (IF) — read the instruction from memory and increment the program counter; Instruction Decode / Register Fetch (ID) — decode the opcode, read source registers, and generate control signals; Execute (EX) — perform the ALU operation or compute a branch/memory address; Memory Access (MEM) — read or write data memory; Writeback (WB) — write a result back into the register file. Each stage is a combinational block bounded by the same clock period, sized to the slowest single stage rather than the slowest whole instruction — this is precisely why pipelining can increase clock frequency. The mechanism that makes this legal is the pipeline register, a set of edge-triggered flip-flops inserted between each pair of adjacent stages. A pipeline register does two jobs simultaneously: it holds the data an instruction has computed so far (e.g., the ALU result, the destination register number, a memory address), and it holds the control signals that later stages will need to know how to treat that data (e.g., "this is a store," "write this register," "branch was taken"). Without control signals traveling in the same registers as the data, a later stage would have no way to know which instruction's data it is looking at or what to do with it — this is the single most important design discipline in building a correct pipelined datapath.

Start from a single-cycle datapath: PC, instruction memory, register file, sign extender, ALU, data memory, and the control unit that decodes the opcode into control signals. The transformation into a pipeline proceeds in four mechanical steps.

Step 1 — Draw stage boundaries. Partition the combinational datapath into five sequential blocks matching IF, ID, EX, MEM, WB, in the order data naturally flows.

Step 2 — Insert pipeline registers. Between every adjacent pair of stages, insert a register: IF/ID, ID/EX, EX/MEM, MEM/WB. Each register is as wide as everything that must survive from that boundary onward.

Step 3 — Replicate control forward. The control unit lives in ID (it decodes the opcode once). But EX, MEM, and WB each need some of those control bits. So the control signals themselves are stored in ID/EX, then copied into EX/MEM, then copied into MEM/WB — control signals ride the pipeline exactly like data, just carrying fewer bits as stages that no longer need them are dropped.

Step 4 — Verify per-instruction consistency. At every clock edge, the values latched into a pipeline register must all belong to the same instruction. This is the invariant that makes the pipeline correct in the absence of hazards (hazards are handled by separate mechanisms covered elsewhere). Below is a stage-by-stage account of exactly what crosses each register, followed by pseudocode for one iteration of the pipeline's clocked behavior. ``` // State held in pipeline registers (conceptually, one struct per boundary) struct IF_ID { instruction, PC_plus_4 } struct ID_EX { PC_plus_4, readData1, readData2, signExtImm, rs, rt, rd, controlSignals_EX_MEM_WB } struct EX_MEM { branchTarget, zeroFlag, aluResult, writeDataForStore, destReg, controlSignals_MEM_WB } struct MEM_WB { memReadData, aluResult, destReg, controlSignals_WB } // One simulated clock cycle, in program order per stage. // All five stages execute "simultaneously": read old register values, // compute new ones, latch on the same clock edge. function CLOCK_TICK(regs): // ---- WB stage: consumes MEM_WB, no output register (writes regfile) ---- if regs.MEM_WB.controlSignals_WB.RegWrite: writeBackData = regs.MEM_WB.controlSignals_WB.MemToReg ? regs.MEM_WB.memReadData : regs.MEM_WB.aluResult RegisterFile.write(regs.MEM_WB.destReg, writeBackData) // ---- MEM stage: consumes EX_MEM, produces next MEM_WB ---- ctrl_MEM = regs.EX_MEM.controlSignals_MEM_WB memReadData = ctrl_MEM.MemRead ? DataMemory.read(regs.EX_MEM.aluResult) : undefined if ctrl_MEM.MemWrite: DataMemory.write(regs.EX_MEM.aluResult, regs.EX_MEM.writeDataForStore) next_MEM_WB = { memReadData, regs.EX_MEM.aluResult, regs.EX_MEM.destReg, ctrl_MEM.WB_bits } // ---- EX stage: consumes ID_EX, produces next EX_MEM ---- ctrl_EX = regs.ID_EX.controlSignals_EX_MEM_WB aluInputB = ctrl_EX.ALUSrc ? regs.ID_EX.signExtImm : regs.ID_EX.readData2 aluResult = ALU(regs.ID_EX.readData1, aluInputB, ctrl_EX.ALUOp) zeroFlag = (aluResult == 0) branchTarget = regs.ID_EX.PC_plus_4 + (regs.ID_EX.signExtImm << 2) destReg = ctrl_EX.RegDst ? regs.ID_EX.rd : regs.ID_EX.rt next_EX_MEM = { branchTarget, zeroFlag, aluResult, regs.ID_EX.readData2, destReg, ctrl_EX.MEM_WB_bits } // ---- ID stage: consumes IF_ID, produces next ID_EX ---- instr = regs.IF_ID.instruction ctrl = MainControl(opcode(instr)) // generated fresh each cycle readData1 = RegisterFile.read(rs(instr)) readData2 = RegisterFile.read(rt(instr)) signExtImm = SignExtend(immediate(instr)) next_ID_EX = { regs.IF_ID.PC_plus_4, readData1, readData2, signExtImm, rs(instr), rt(instr), rd(instr), ctrl } // ---- IF stage: fetches new instruction, produces next IF_ID ---- instructionWord = InstructionMemory.read(PC) next_IF_ID = { instructionWord, PC + 4 } PC = PC + 4 // (branch resolution is handled in EX/MEM in later chapters) // ---- Latch all pipeline registers simultaneously ---- regs.IF_ID = next_IF_ID regs.ID_EX = next_ID_EX regs.EX_MEM = next_EX_MEM regs.MEM_WB = next_MEM_WB return regs ``` Notice the update order in the pseudocode: WB is computed from old register state before EX computes new state, and so on down to IF — this mirrors real hardware, where all five stages read their input pipeline register (set at the end of the previous cycle) and compute new values that are latched into their output pipeline register at the end of the current cycle, all in parallel. The pseudocode processes them in reverse pipeline order (WB first) purely so that a straight-line simulation can read old values before they are overwritten; in real hardware there is no such ordering — everything happens combinationally and simultaneously between two clock edges.

Throughput and latency. Let a single-cycle datapath require a clock period $T_{single}$ sized to the slowest instruction's total combinational delay, and let a pipelined design split that same work into $k=5$ stages, each with delay $t_i$, plus a fixed register overhead $\delta$ (setup/hold + clock skew) per stage boundary. The pipelined clock period is

For $n$ instructions, single-cycle execution takes $n \cdot T_{single}$. Pipelined execution takes

As $n \to \infty$, throughput approaches one instruction per $T_{pipe}$, and since $T_{pipe} \ll T_{single}$ (a fifth of the work, roughly), overall speedup approaches a factor near $k=5$ in the ideal case — though in practice, imperfect stage balancing and register overhead $\delta$ reduce this. Notice that per-instruction latency does not decrease (it is $k \cdot T_{pipe}$, generally slightly more than $T_{single}$ due to the added register delays); pipelining improves throughput, not the time to execute any single instruction.

Space. The additional hardware cost is the pipeline registers themselves: four registers whose combined width equals roughly the sum of all data and control signals live at each boundary — a modest, fixed overhead, independent of $n$, that does not asymptotically grow with program size. This is $O(1)$ extra state relative to the single-cycle datapath's combinational logic.

Correctness argument. The design is correct as long as the following invariant holds at every clock edge: > Every pipeline register, at every cycle, contains data and control signals belonging to exactly one instruction, consistent with that instruction's position in the pipeline. We can verify this invariant inductively. Base case: before any instruction enters, all pipeline registers hold a designated "bubble" (no-op) state, trivially satisfying the invariant (there is no instruction to be inconsistent about). Inductive step: assume at the start of cycle $c$, each pipeline register correctly holds instruction $I_j$'s state for the appropriate $j$ (the instruction that is $j$ stages ahead of instruction $I_{j-k}$... more simply: register $R_i$ holds the instruction that has completed exactly $i$ stages). During cycle $c$, each stage reads only its own input register (never another stage's), computes a pure function of that data plus global unchanging state (like the register file, which is separately guarded — see below), and writes only its own output register. Since the write to every register happens on the same clock edge, and each stage's computation depended only on data that was itself consistently tagged to one instruction, the newly latched registers again satisfy the invariant, now advanced by one stage per instruction. By induction, the invariant holds at every cycle. The one shared piece of global state, the register file, deserves a specific correctness note: with a single write port active only in WB and read ports active in ID, this design is only fully sound for straight-line, mutually independent instructions. If an instruction in ID needs a value that an earlier, still-in-flight instruction will write back later, the naive register file read in ID sees stale data — this is exactly the data hazard problem, addressed by forwarding and stalling logic in later material. Likewise, if two instructions want the same functional unit or memory port in the same cycle, that is a structural hazard; the datapath described here assumes separate instruction and data memories precisely to avoid one common structural hazard by construction. This article's correctness proof therefore comes with an explicit caveat: it establishes only that control and data are threaded consistently through the pipeline registers, assuming no cross-instruction dependency conflicts — the deeper correctness guarantees under hazards are the subject of the Data Hazards and Forwarding treatment.

Trace four instructions through the pipeline, assuming no hazards between them (chosen so writeback and reads never collide): ``` I1: add $t0,$s1, $s2 I2: sub$t1, $s3,$s4 I3: lw $t2, 0($s5) I4: or $t3,$s6, $s7 ```

Follow I3 (`lw $t2, 0($s5)`) specifically to see what rides in each pipeline register:

• Cycle 3 (IF): PC fetches the `lw` instruction word; `IF/ID` latches `{instruction = lw..., PC+4}` at the end of cycle 3.
• Cycle 4 (ID): Control unit decodes opcode `lw`, sets `RegDst=0, ALUSrc=1, MemToReg=1, RegWrite=1, MemRead=1, MemWrite=0, Branch=0`. Register file reads `s5`. Sign-extends the offset `0`. `ID/EX` latches `{readData1=s5, signExtImm=0, rt=$t2, all control bits}` at end of cycle 4.
• Cycle 5 (EX): ALU computes `s5 + 0` (the effective address). `EX/MEM` latches `{aluResult=address, destReg=t2, control bits for MEM and WB only: MemRead=1, MemToReg=1, RegWrite=1}` — note `ALUSrc` and `RegDst`, needed only in EX, are not propagated further; they are consumed and dropped.
• Cycle 6 (MEM): `MemRead=1` triggers a data memory read at the latched address. `MEM/WB` latches `{memReadData, destReg=$t2, control bits for WB only: MemToReg=1, RegWrite=1}`.
• Cycle 7 (WB): `MemToReg=1` selects `memReadData` (not `aluResult`) as the value written into `$t2`.

This traces the exact claim from the "How it works" section: control signals shrink as they pass through registers (5 stage's worth in ID/EX down to 1 bit's worth of relevance by MEM/WB), because each later stage only needs the subset of control bits still relevant to it. Meanwhile I1 finishes writeback in cycle 5, two cycles before I3 even reaches MEM — instructions genuinely overlap, and (since none of I1–I4 depend on each other's registers) no stall is required. Total time: 8 cycles for 4 instructions, matching $n+k-1 = 4+5-1=8$ exactly.

The pipelined datapath as taught today crystallized from decades of practice in scaling processor throughput without a proportional cost increase in circuit complexity, culminating in the RISC design philosophy of the 1980s that made regular, evenly-staged pipelines practical to teach and build.

Every mainstream CPU core — from a microcontroller's simple in-order pipeline to a superscalar out-of-order server chip — descends conceptually from this five-stage skeleton, even when the real pipeline has ten, fifteen, or twenty stages instead of five. RISC-V teaching cores (like the widely used single-issue in-order RISC-V pipeline implementations), ARM Cortex-M microcontroller cores, and early MIPS and SPARC workstations all implement close variants of exactly this IF/ID/EX/MEM/WB structure. Understanding how control signals must be threaded through pipeline registers is a direct prerequisite for understanding structural hazards (what happens when two stages want the same resource simultaneously) and data hazards (what happens when a later stage needs a value an earlier, still-in-flight instruction has not yet produced) — both of which require additional hardware (forwarding paths, stall/bubble logic, or hazard-detection units) layered directly onto the datapath and pipeline registers built here. Compiler instruction scheduling, branch prediction, and superscalar issue logic in real high-performance processors are all elaborations that assume this basic overlapped-stage machinery as their foundation, alongside broader ideas from Introduction to Pipelining and Single-Cycle Control.

Ask the tutor: How does the hazard detection unit modify this pipeline register scheme when a load is immediately followed by a dependent instruction?