Introduction to Pipelining

Pipelining is a technique for increasing instruction-level throughput by dividing instruction execution into a sequence of stages, each handled by dedicated hardware, and allowing different instructions to occupy different stages simultaneously. In a non-pipelined multicycle processor, instruction i+1 cannot begin any work until instruction i has completely finished — every functional unit sits idle for most of each instruction's lifetime. In a pipelined processor, as soon as instruction i moves out of the fetch stage into decode, instruction i+1 moves into fetch. Every stage is busy on some instruction during every clock cycle, once the pipeline is full. The standard decomposition used in the classic RISC pipeline (as in MIPS or RISC-V) splits instruction execution into five stages: Instruction Fetch (IF), Instruction Decode / register read (ID), Execute / ALU operation (EX), Memory access (MEM), and Write-back (WB). Each stage corresponds to roughly one clock cycle of work, and a register — called a pipeline register or pipeline latch — sits between consecutive stages to hold the intermediate results of an instruction as it moves forward. This is the direct generalization of the multicycle datapath, where the same five phases exist but execute sequentially for one instruction before the next instruction's fetch even starts. Two numbers matter for understanding pipelining's payoff: latency, the time for one instruction to travel from fetch to write-back, and throughput, the rate at which instructions complete. Pipelining is fundamentally a throughput optimization. It does not shrink the amount of work any instruction requires — in fact latency for a single instruction is often slightly higher in a pipelined design, because the clock period must accommodate register overhead and the slowest stage, and instructions occasionally stall. What pipelining buys you is that, in steady state, a new instruction finishes every cycle instead of every `k` cycles, where `k` is the number of stages.

The mechanism is best understood first through the laundry analogy, then formalized with a cycle-by-cycle diagram, and finally captured in pseudocode describing how a control unit advances instructions through pipeline stages. Suppose you must wash, dry, fold, and put away four loads of laundry, and each of the four sub-tasks — wash (W), dry (D), fold (F), store (S) — takes 30 minutes on independent equipment (washer, dryer, table, closet). If you process one load fully before starting the next, four loads take `4 × 4 × 30 = 480` minutes. If instead you start load 2's wash the moment load 1 moves to the dryer, and so on, the total time drops dramatically because the four independent stages of different loads run concurrently. This is exactly what a processor does with IF, ID, EX, MEM, WB across a stream of instructions.

The key structural requirement is that each stage uses a physically distinct resource: fetch uses the instruction memory, decode uses the register file (read ports), execute uses the ALU, memory access uses the data memory, write-back uses the register file (write port). Because these are different pieces of hardware, instruction i's EX and instruction i+1's ID and instruction i+2's IF can all happen in the same clock cycle without physical conflict — this is the assumption of no structural hazards, which the article on Structural Hazards examines when it fails (e.g., a single unified memory for both instructions and data).

Step-by-step mechanism

1. Partition instruction execution into `k` stages of roughly equal duration, each performed by dedicated hardware and separated by a pipeline register. 2. Clock the whole pipeline synchronously. Every stage advances its contents to the next stage's register on every clock edge. 3. Inject a new instruction into stage 1 every cycle (assuming no hazards), rather than waiting for the current instruction to finish all stages. 4. Set the clock period equal to the time required by the slowest single stage (plus register overhead), since every stage now shares one global clock. 5. Steady state is reached after the first `k − 1` cycles (the fill time); from then on, one instruction completes every cycle. 6. Drain: the last instruction still needs `k − 1` more cycles after entering the pipeline to exit, since it must pass through all remaining stages alone. ``` // Conceptual pipeline scheduler: k stages, n instructions, // one pipeline register between consecutive stages. // stage[s] holds either an instruction-id or EMPTY. function RUN_PIPELINE(n, k): stage = array of size k, all initialized to EMPTY next_instruction = 0 completed = 0 cycle = 0 while completed < n: cycle = cycle + 1 // Advance instructions from stage k-1 down to stage 0 // (process in reverse order so a stage's old value // is read before it is overwritten this cycle) for s from k-1 down to 1: stage[s] = stage[s-1] // Stage k-1 finishing this cycle means WB completes if stage[k-1] != EMPTY: completed = completed + 1 // Inject a new instruction into stage 0 (IF) if available if next_instruction < n: stage[0] = next_instruction next_instruction = next_instruction + 1 else: stage[0] = EMPTY return cycle // total cycles to finish all n instructions ``` Running this simulation for `n` instructions and `k` stages always returns exactly `k + (n − 1)` cycles — `k` cycles to walk the very first instruction through the whole pipeline, plus one more cycle for each of the remaining `n − 1` instructions, since after fill, one instruction retires per cycle. Contrast this with the non-pipelined cost of `n × k` cycles when each instruction must fully finish before the next starts. The gap between `n × k` and `k + n − 1` is the entire story of pipelining's benefit.

Latency of one instruction. In a `k`-stage pipeline, a single instruction still requires exactly `k` cycles to travel from IF through WB — pipelining does not shorten this. If anything, the cycle time itself may be slightly longer than in a single-cycle design because of pipeline-register setup/hold overhead, so single-instruction latency in absolute time can increase.

Throughput / total time for `n` instructions. The pipelined schedule produced by the algorithm above always finishes in ``` T_pipelined(n, k) = k + (n - 1) cycles ``` Justification: the first instruction needs `k` cycles to clear the pipeline (one visit to each stage). Every subsequent instruction is exactly one cycle behind the previous one and, once the pipeline is full, retires exactly one cycle after its predecessor. So instructions `2` through `n` add `n − 1` more cycles beyond the first instruction's `k`. This is provable by induction on the simulation: assume instruction `i` retires at cycle `k + (i - 1)`; since instruction `i+1` enters stage 0 exactly one cycle after instruction `i` did (line "inject a new instruction" runs every cycle while `next_instruction < n`), and both move one stage per cycle thereafter with no stalls, instruction `i+1` retires at cycle `k + i`. The base case `i = 1` retiring at cycle `k` is immediate from the fill argument. The non-pipelined (multicycle) equivalent takes ``` T_sequential(n, k) = n * k cycles ``` since each instruction fully occupies the datapath for `k` cycles before the next can start.

Speedup is the ratio: ``` Speedup(n, k) = T_sequential / T_pipelined = (n * k) / (k + n - 1) ``` Two limits matter:

• As `n → ∞` (long instruction streams), `Speedup → k`. The pipeline approaches, but never reaches, a `k`-fold throughput improvement.
• For small `n` (short streams, frequent flushes from branches), speedup is far below `k`, because fill and drain overhead — `k − 1` "wasted" cycles where the pipeline is not yet or no longer full — dominates.

This is the same mathematical shape as Amdahl's Law: a fixed overhead (`k − 1` cycles of fill/drain) is amortized over an ever-larger useful workload (`n` instructions), so returns diminish and asymptote rather than growing without bound.

Clock period constraint (correctness of the "why not shrink the clock too" question). Because all stages share one global clock, the cycle time `T_c` must be at least as long as the slowest stage: ``` T_c = max(t_IF, t_ID, t_EX, t_MEM, t_WB) + t_register_overhead ``` If stages are unbalanced — say MEM takes twice as long as any other stage — then every stage is slowed to match MEM's time, wasting potential cycles in the faster stages. This is why pipeline designers try to partition work into stages of nearly equal latency; an uneven split reduces the effective speedup below the ideal `k`, even asymptotically, because the true comparison is against `k` balanced single-cycle-equivalent stages, not `k` arbitrary chunks of the critical path.

Correctness invariant. The scheme is correct (produces the same architectural results as the non-pipelined machine) exactly when, at every clock cycle, each stage operates on a different instruction using disjoint hardware resources, and no stage's output for instruction `i` is needed as an already-updated input by another stage still working on an earlier or later instruction in the same cycle. This disjointness assumption is what breaks under structural hazards (two instructions needing the same physical unit in the same cycle) and data/control hazards (an instruction needing a value or address not yet produced) — both deferred to their own articles, but it is worth stating precisely why the simple model above is an idealization: it assumes zero hazards, an assumption real pipelines must actively engineer for.

Space complexity. Pipelining costs `O(k)` additional storage relative to a comparable multicycle design: one pipeline register per boundary between adjacent stages, each holding the control signals and data values that later stages will need. This is genuinely extra hardware, but it is modest compared to the throughput gained.

Consider a 5-stage pipeline (`k = 5`) executing `n = 8` instructions, each stage taking 1 ns in the pipelined design, versus a multicycle design where each instruction sequentially takes `5` cycles of 1 ns each (assume, for a clean comparison, that stage boundaries align so both designs use a 1 ns cycle).

Sequential (multicycle) time: ``` T_sequential = n k = 8 5 = 40 ns ```

Pipelined time: ``` T_pipelined = k + (n - 1) = 5 + 7 = 12 ns ```

Speedup: ``` Speedup = 40 / 12 ≈ 3.33 ``` Note this is noticeably less than the "ideal" `k = 5`, because `n = 8` is small enough that fill/drain (`k − 1 = 4` cycles of the total `12`) is a substantial fraction — a third — of the run. Now scale up to `n = 1000` instructions: ``` T_sequential = 1000 * 5 = 5000 ns T_pipelined = 5 + 999 = 1004 ns Speedup = 5000 / 1004 ≈ 4.98 ``` This is much closer to the asymptotic ceiling of `5`. The table below traces cycle-by-cycle occupancy for the `n = 8` case, confirming the formula directly (`E` = empty stage):

The last retirement lands on cycle 12, exactly matching `k + n − 1 = 5 + 8 - 1 = 12`. Cycles 5–8 are fully "busy" (all five stages occupied) — that is the steady state where the pipeline delivers one instruction per cycle; cycles 1–4 are fill, and cycles 9–12 are drain.

The overlapping-stage idea predates modern computing — it is the same principle behind assembly lines — but its rigorous application to instruction execution came from a lineage of computer architects solving very concrete throughput bottlenecks in scientific computing machines.

Every general-purpose CPU shipped in the last three decades — x86 chips from Intel and AMD, ARM cores in phones and tablets, RISC-V cores in embedded and research systems — relies on pipelining as a baseline throughput technique. The 5-stage pipeline described here is the direct ancestor of the classic MIPS and early ARM designs still used pedagogically and in embedded controllers. Modern high-performance cores extend the idea into much deeper pipelines (sometimes 15–20+ stages) to permit higher clock frequencies, trading a longer branch-misprediction penalty for a shorter clock period per stage. GPUs pipeline not just instruction stages but entire thread-warp execution to hide memory latency behind arithmetic. Digital signal processors and network packet processors pipeline stages of a fixed computation (e.g., FFT butterflies, packet header parsing) for the same throughput reasons. Understanding this foundational overlap-for-throughput idea is the prerequisite for reasoning about The Pipelined Datapath, where the actual hardware pipeline registers and forwarding paths are built, and for Structural Hazards, Data Hazards, and Control Hazards, which describe exactly how and why the idealized "one instruction retires per cycle" picture breaks down in practice.

Ask the tutor: How do data hazards force the ideal pipeline model in this article to insert stall cycles, and how is that penalty quantified?