Pipelining

Before we can appreciate pipelining, we need to feel the pain of its absence. In a purely sequential, single-cycle CPU, every instruction occupies the processor for its entire execution time from start to finish before the next instruction can begin.

Suppose each of the five stages takes 200 picoseconds (ps). A single instruction takes 1000 ps (1 nanosecond). If you want to run 1000 instructions, you wait 1000 × 1 ns = 1 microsecond. Your clock cycle must be at least 1 ns long to give every instruction enough time to complete all five stages.

The key insight here is that at any given moment, only one stage is doing useful work. While the ALU is executing stage 3, the memory access hardware (stage 4) sits completely idle. While stage 4 is reading memory, the fetch unit (stage 1) is idle. This is staggering waste — four out of five units are always doing nothing.

This is the fundamental inefficiency that pipelining solves. The hardware for each stage exists and is paid for in transistors and silicon area. Why not use it?

The laundry analogy is famous in computer architecture education because it is perfect. Let's make it precise.

Suppose you have four loads of laundry. Each load requires four steps:

1. Wash (30 min)
2. Dry (40 min)
3. Fold (20 min)
4. Put away (10 min)

The total time for one load is 100 minutes.

Sequential approach: Finish load 1 completely (100 min), then load 2 (100 min), then load 3, then load 4. Total: 400 minutes.

Pipelined approach: Start load 2 in the washer as soon as load 1 moves to the dryer. While load 2 washes and load 1 dries, load 3 is waiting. You stagger the work:

• t=0: Load 1 → Washer
• t=30: Load 1 → Dryer, Load 2 → Washer
• t=70: Load 1 → Fold, Load 2 → Dryer, Load 3 → Washer
• t=90: Load 1 → Put away, Load 2 → Fold, Load 3 → Dryer, Load 4 → Washer
• t=100: Load 1 done, Load 2 → Put away, ...

Notice: Load 1 still takes 100 minutes — pipelining does not make any individual load faster. But all four loads complete far sooner than 400 minutes.

The CPU mapping is exact:

• Loads of laundry = instructions
• Washer/Dryer/Fold/Put away = pipeline stages (IF/ID/EX/MEM/WB)
• The constraint that a load must pass through stages in order = data dependencies and instruction ordering
• The bottleneck stage (slowest) = the stage that determines the pipeline clock period

One subtle point: in laundry, each stage takes a different amount of time. In a CPU pipeline, the clock cycle is determined by the slowest stage — all stages must complete within one clock period. This is why pipelined processor designers work hard to balance stage latencies.

The five-stage RISC pipeline was popularized by the MIPS architecture (Patterson & Hennessy) and underlies ARM, RISC-V, and the conceptual model for x86 microarchitectures. Each stage is a distinct hardware unit.

Stage 1 — IF: Instruction Fetch The Program Counter (PC) register holds the address of the next instruction. The IF stage reads that address, fetches the instruction word from the instruction cache (I-cache), and increments the PC to point to the next sequential instruction. Output: the raw instruction bits and the next PC value.

Stage 2 — ID: Instruction Decode The raw instruction bits are decoded to determine: what operation to perform, which registers to read, whether an immediate value is embedded in the instruction, and what the destination register is. The register file is read here — the values of source registers (rs1, rs2 in RISC-V) are fetched from the register file. Output: control signals, register values, sign-extended immediates.

Stage 3 — EX: Execute The ALU (Arithmetic Logic Unit) performs the computation: add, subtract, AND, OR, shift, compare. For branch instructions, the branch target address and the branch condition are computed here. For load/store instructions, the effective memory address is computed (base register + offset). Output: ALU result, branch decision, memory address.

Stage 4 — MEM: Memory Access For load instructions (lw, ld): reads a word from the data cache (D-cache) at the address computed in EX. For store instructions (sw, sd): writes the value from a register to the data cache. For ALU instructions and branches: this stage is a pass-through — no memory operation occurs, but the pipeline still has this slot. Output: data read from memory (for loads) or nothing meaningful (for non-memory instructions).

Stage 5 — WB: Write Back Writes the result back to the destination register in the register file. For ALU instructions, this is the ALU result from EX. For loads, this is the data read from memory in MEM. For stores and branches, nothing is written to the register file.

Why five stages specifically? This is a design choice, not a law of physics. Simple embedded cores (ARM Cortex-M0) use 3 stages. Deep out-of-order cores like modern Intel can have 14–20 stages. Five stages is the canonical teaching example because it cleanly separates the four distinct hardware resources (fetch logic, decode logic + register file, ALU, memory system) with write-back as the fifth.

# Let's trace a RISC-V add instruction through all five stages:
# add x3, x1, x2   (x3 = x1 + x2)
#
# Cycle 1 — IF:
#   PC = 0x1000
#   Fetch instruction word: 0x002081B3  (encoding of 'add x3, x1, x2')
#   PC_next = 0x1004
#
# Cycle 2 — ID:
#   Decode 0x002081B3:
#     opcode = 0110011 (R-type)
#     rd  = 00011 (x3)
#     funct3 = 000
#     rs1 = 00001 (x1)
#     rs2 = 00010 (x2)
#     funct7 = 0000000  → ADD
#   Read register file: A = reg[x1], B = reg[x2]
#
# Cycle 3 — EX:
#   ALU computes: result = A + B
#   (For this instruction, branch_taken = false, mem_addr = don't care)
#
# Cycle 4 — MEM:
#   No memory operation (R-type instruction)
#   ALU result passes through unchanged
#
# Cycle 5 — WB:
#   Write result → reg[x3]
#   x3 now holds x1 + x2

Here is a subtlety that textbook diagrams often gloss over but is essential for really understanding pipelining: pipeline registers.

Each stage runs on the same clock. At every rising clock edge, every stage simultaneously:

1. Reads its inputs (from the pipeline register before it)
2. Does its work
3. Latches its outputs into the pipeline register after it

These inter-stage flip-flop banks — the pipeline registers — are what make pipelining physically possible. Without them, you would have a combinatorial mess: stage 3's logic would be trying to use a result that stage 2's logic is still computing.

The five stages create four inter-stage registers:

• IF/ID register: holds the fetched instruction bits + PC+4
• ID/EX register: holds decoded control signals, register values (A, B), sign-extended immediate, destination register number
• EX/MEM register: holds ALU result, store data value, branch decision, destination register number
• MEM/WB register: holds memory read data (for loads) or ALU result (for non-loads), destination register number

Why does the destination register number travel the whole pipeline? Because WB needs to know which register to write into, and it finds out by reading the destination register field (rd) that was decoded in stage 2 (ID). That field gets passed through the ID/EX → EX/MEM → MEM/WB registers until it reaches WB. This is a beautiful example of values being carried forward through the pipeline rather than stored in some central place.

You can think of each pipeline register as a snapshot — a photograph of everything a downstream stage will need to do its job, taken at the moment the upstream stage finished. Each clock tick, the photographs shuffle one position down the pipeline.

// Conceptual C struct showing what lives in each pipeline register
// (This is how a software pipeline simulator represents them)

struct IF_ID {
    uint32_t instruction;   // raw fetched instruction bits
    uint32_t pc_plus_4;     // PC + 4 (next sequential PC)
};

struct ID_EX {
    uint32_t reg_A;         // value of source register 1
    uint32_t reg_B;         // value of source register 2
    int32_t  imm_ext;       // sign-extended immediate
    uint8_t  rd;            // destination register number (0-31)
    uint8_t  alu_op;        // control: what ALU operation to perform
    bool     mem_read;      // control: does this instruction read memory?
    bool     mem_write;     // control: does this instruction write memory?
    bool     reg_write;     // control: does this instruction write a register?
    bool     mem_to_reg;    // control: WB source is memory (load) or ALU?
};

struct EX_MEM {
    uint32_t alu_result;    // output of the ALU
    uint32_t store_data;    // value to write to memory (for stores)
    uint8_t  rd;            // destination register (carried forward)
    bool     mem_read;
    bool     mem_write;
    bool     reg_write;
    bool     mem_to_reg;
    bool     zero;          // ALU zero flag (for branches)
};

struct MEM_WB {
    uint32_t mem_read_data; // data read from memory (for loads)
    uint32_t alu_result;    // ALU result (for non-loads)
    uint8_t  rd;            // destination register (carried forward)
    bool     reg_write;
    bool     mem_to_reg;
};

// Each clock cycle, the pipeline advances:
void clock_tick() {
    // Order matters! Update from back to front to avoid overwriting
    MEM_WB  = exec_mem_stage(EX_MEM);
    EX_MEM  = exec_ex_stage(ID_EX);
    ID_EX   = exec_id_stage(IF_ID);
    IF_ID   = exec_if_stage(pc);
    pc      = next_pc;
}

Pipelining introduces a distinction that confuses many beginners but is one of the most important concepts in all of computer systems: throughput versus latency.

Latency is how long it takes a single instruction to complete from start to finish. In a 5-stage pipeline with a 200 ps clock cycle, one instruction takes 5 × 200 ps = 1000 ps (1 ns). In an unpipelined CPU with a 1000 ps clock cycle, one instruction also takes 1000 ps.

Throughput is how many instructions complete per unit time. In the unpipelined CPU, throughput = 1 instruction / 1000 ps = 1 GHz-equivalent. In the pipelined CPU, after the pipeline is full, a new instruction completes every 200 ps (one clock cycle), giving throughput = 5× higher.

The punchline: pipelining does not make individual instructions faster. It makes the CPU produce more instructions per second.

The analogy: a highway toll booth. Adding more booths (parallel lanes, like superscalar) would reduce individual car wait times. But pipelining is more like having one booth process cars in stages — take the cash, make change, raise the gate — so that as soon as car 1 moves to 'make change', car 2 enters 'take the cash'. Each car still takes the same total time, but cars exit the booth much more frequently.

This distinction has profound engineering consequences:

• For real-time systems with hard latency deadlines, pipelining does not help (and can hurt because of pipeline fill time).
• For throughput-oriented workloads (web servers, video encoding, database scans), pipelining is transformative.
• The Linux kernel itself has soft-real-time requirements in interrupt handlers — this is part of why interrupt latency and preemption are carefully managed.

// Observe throughput vs latency difference on your own machine:
// Throughput benchmark: tight loop doing independent adds (pipeline-friendly)
// Latency benchmark: chain of dependent adds (each depends on previous result)

#include <stdint.h>
#include <time.h>
#include <stdio.h>

#define N 1000000000UL

int main() {
    struct timespec t0, t1;
    volatile uint64_t sum = 0;

    // THROUGHPUT benchmark: independent additions
    // The pipeline can execute many of these simultaneously
    // (in practice, superscalar CPUs issue multiple per cycle)
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (uint64_t i = 0; i < N; i++) {
        sum += 1; // simple, but the compiler may vectorize this
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double throughput_ns = (t1.tv_sec - t0.tv_sec) * 1e9 +
                           (t1.tv_nsec - t0.tv_nsec);
    printf("Throughput loop: %.2f ns/iter  (sum=%lu)\n",
           throughput_ns / N, sum);

    // LATENCY benchmark: dependent chain
    // Each iteration depends on the previous — cannot overlap
    sum = 1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (uint64_t i = 0; i < N; i++) {
        sum = sum * 6364136223846793005ULL + 1442695040888963407ULL; // LCG
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double latency_ns = (t1.tv_sec - t0.tv_sec) * 1e9 +
                        (t1.tv_nsec - t0.tv_nsec);
    printf("Latency chain:   %.2f ns/iter  (sum=%lu)\n",
           latency_ns / N, sum);

    return 0;
}

If a task takes time T to complete without pipelining, and you divide it into k equal stages each taking T/k time, what is the theoretical speedup for executing N tasks?

Filling the pipeline: The first task still takes T time (it must go through all k stages). But every subsequent task completes T/k time later. For N tasks:

• Unpipelined: N × T
• Pipelined: T + (N−1) × (T/k) [first task takes T, each subsequent takes T/k]

Speedup formula:

Speedup = (N × T) / (T + (N−1) × T/k)
         = N·k / (k + N − 1)

As N → ∞ (many instructions, pipeline always full):

Speedup → k

So the ideal speedup of a k-stage pipeline over an unpipelined processor approaches k as N grows large. A 5-stage pipeline approaches 5× speedup.

Why only 'approaches'? Because of pipeline fill and drain time. The pipeline takes k−1 cycles to fill from empty, and k−1 cycles to drain at the end. For a program with 1 billion instructions, this startup cost is negligible. For a tight 10-instruction loop, it is significant.

Why is real speedup always less than k?

1. Stages are rarely perfectly balanced (one stage takes longer, setting the clock period)
2. Pipeline hazards (covered in the next module) force stalls
3. Branch mispredictions flush the pipeline
4. Cache misses stall the pipeline waiting for memory

In practice, modern CPUs achieve roughly 2–4 instructions per cycle (IPC) through a combination of deep pipelining, superscalar issue (multiple pipelines), and out-of-order execution — but the 5-stage model is the foundation of understanding all of it.

// Python: compute theoretical pipeline speedup for varying N and k
// Run with: python3 speedup.py

def pipeline_speedup(N, k):
    """N = number of instructions, k = number of pipeline stages"""
    time_unpipelined = N  # normalized: 1 unit per instruction
    time_pipelined = k + (N - 1)  # k cycles to complete first + (N-1) more
    return time_unpipelined / time_pipelined

print(f"{'N':>10}  {'Speedup (k=5)':>15}  {'Speedup (k=10)':>15}")
print("-" * 45)
for N in [1, 5, 10, 50, 100, 1000, 1000000]:
    s5  = pipeline_speedup(N, 5)
    s10 = pipeline_speedup(N, 10)
    print(f"{N:>10}  {s5:>15.3f}  {s10:>15.3f}")

# Sample output:
#          N  Speedup (k=5)  Speedup (k=10)
# -----------------------------------------
#          1          0.200           0.100
#          5          0.625           0.357
#         10          1.000           0.526
#         50          3.125           2.857
#        100          3.846           4.348
#       1000          4.780           8.333
#    1000000          5.000          10.000

A pipeline space-time diagram (also called a pipeline timing diagram) is the canonical way to see what is happening at every cycle. One axis is time (clock cycles), the other is the instruction index. Each cell shows which stage that instruction is in during that cycle.

For a 5-stage pipeline executing instructions I1 through I5:

Cycle:  1    2    3    4    5    6    7    8    9
I1:     IF   ID   EX   MEM  WB
I2:          IF   ID   EX   MEM  WB
I3:               IF   ID   EX   MEM  WB
I4:                    IF   ID   EX   MEM  WB
I5:                         IF   ID   EX   MEM  WB

Key observations:

1. Cycle 5 (column 5): All five stages are occupied simultaneously — the pipeline is full. This is steady-state operation.
2. I1 completes at cycle 5 (5 cycles latency), exactly the same as an unpipelined processor.
3. I2 completes at cycle 6, just one cycle after I1. In steady state, one instruction completes per cycle — this is what throughput = 1 IPC means.
4. Columns 1–4: The pipeline is filling up — not all stages are occupied. This is the pipeline startup penalty.
5. After all instructions are fetched: The pipeline drains — later cycles have fewer active stages.

This diagram is your debugging tool. When you study pipeline hazards (the next module), you will annotate this diagram with stall bubbles (---) inserted when an instruction cannot proceed and nop operations inserted by hardware to maintain correctness. The space-time diagram makes the cost of hazards immediately visible.

# Generate a pipeline timing diagram in your terminal
# Works for any number of instructions and stages

stages = ['IF', 'ID', 'EX', 'MEM', 'WB']
num_instructions = 7
num_stages = len(stages)
total_cycles = num_instructions + num_stages - 1

print(f"Cycle:", end="")
for c in range(1, total_cycles + 1):
    print(f"{c:>5}", end="")
print()

for i in range(num_instructions):
    print(f"I{i+1}:  ", end="")
    for c in range(1, total_cycles + 1):
        stage_idx = c - i - 1  # which stage is instruction i in at cycle c?
        if 0 <= stage_idx < num_stages:
            print(f"{stages[stage_idx]:>5}", end="")
        else:
            print(f"{'':>5}", end="")
    print()

# Output:
# Cycle:    1    2    3    4    5    6    7    8    9   10   11
# I1:       IF   ID   EX  MEM   WB
# I2:            IF   ID   EX  MEM   WB
# I3:                 IF   ID   EX  MEM   WB
# I4:                      IF   ID   EX  MEM   WB
# I5:                           IF   ID   EX  MEM   WB
# I6:                                IF   ID   EX  MEM   WB
# I7:                                     IF   ID   EX  MEM   WB

Everything so far has been theory. But you can observe pipeline behavior directly on your Linux machine using perf stat, which reads hardware performance counters built into every modern CPU.

The key metric is IPC (Instructions Per Cycle). An ideal single-pipeline CPU can execute at most 1 IPC. Modern superscalar CPUs can exceed 1 IPC (multiple pipelines). But pipeline stalls from data hazards, branch mispredictions, and cache misses reduce IPC below the theoretical maximum.

Key perf events to watch:

• instructions: total instructions retired
• cycles: total clock cycles elapsed
• branches: total branch instructions
• branch-misses: branches where the predictor guessed wrong (these flush the pipeline!)
• cache-misses: L1 data cache misses (these stall the pipeline waiting for memory)

The perf tool is the gateway drug to low-level performance analysis. Kernel developers use it constantly. Understanding pipelining is what makes perf output meaningful rather than just numbers.

# Compile and run the throughput/latency benchmark, then observe with perf:

# First, compile with optimization disabled to see raw pipeline behavior:
gcc -O0 -o bench bench.c  # bench.c from the throughput/latency concept

# Run perf stat:
perf stat ./bench

# Example output (your numbers will differ):
#  Performance counter stats for './bench':
#
#      1,842,345,123      instructions              #    0.87  insn per cycle
#      2,117,634,891      cycles
#         12,345,678      branches                  #  678.234 M/sec
#            234,567      branch-misses             #    1.90% of all branches
#
# IPC = 0.87 means the pipeline is not running at peak efficiency.
# branch-misses = 1.90% - each miss flushes ~15 cycles of pipeline work.

# Now with optimization:
gcc -O2 -o bench_opt bench.c
perf stat ./bench_opt
# You should see higher IPC (~2.0 or more) because the compiler
# rearranged instructions to avoid pipeline stalls!

# Observe the 'insn per cycle' line specifically -- this is your IPC.
# A well-pipelined program on a modern out-of-order CPU: 2-4 IPC
# A badly-stalled program: 0.1-0.5 IPC

If more stages means faster clock (each stage does less work, so it completes faster), why not have 100 stages?

This was actually tried. Intel's Pentium 4 (Netburst microarchitecture, 2000–2004) had a 20–31 stage pipeline, enabling a 3.8 GHz clock. AMD's competing Athlon 64 had a 12-stage pipeline running at 2.4 GHz. Despite the lower clock, the Athlon was often faster in real-world tasks. Why?

The deeper the pipeline, the more costly each hazard becomes.

When a branch misprediction flushes a 5-stage pipeline, you lose 4 cycles of work. When it flushes a 31-stage pipeline, you lose 30 cycles. If branches occur every 5–10 instructions on average (realistic for compiled code), and your branch predictor is 95% accurate, the math quickly shows that deeper pipelines get eaten alive by misprediction penalties.

The modern answer is a combination of:

1. Moderate pipeline depth: ~14–20 stages (not 30+)
2. Sophisticated branch predictors: 99%+ accuracy on modern CPUs (TAGE, perceptron predictors)
3. Speculative execution: keep filling the pipeline past branches by guessing the outcome
4. Out-of-order execution: find independent instructions from later in the program to fill stalled pipeline slots

This tension — deeper pipeline gives faster clock but more hazard cost — is the central design trade-off in CPU microarchitecture. The Pentium 4's failure to win despite a higher clock rate is one of the most instructive case studies in computer architecture history.

RISC-V (pronounced 'RISC Five') is the perfect architecture to study pipelining on because it was explicitly designed to pipeline cleanly. It is free, open, and used in real silicon from SiFive, Alibaba, Western Digital, and increasingly in RISC-V Linux kernel work.

RISC-V design choices that enable clean pipelining:

1. Fixed instruction width (32 bits for RV32I): IF stage always knows how many bytes to fetch. x86's variable-length instructions make IF/ID much more complex.

2. Load-use latency is explicit: RISC-V has a one-cycle load-use hazard by design. The compiler (or programmer) is expected to schedule instructions to avoid it. This simplifies hardware.

3. Register-register ALU operations: Most operations read two registers, compute, write one register. Memory access (loads/stores) is separate. This is the RISC philosophy — clean separation of concerns per stage.

4. Branch delay slot (in MIPS, not RISC-V): MIPS had a 'branch delay slot' where the instruction after a branch always executes regardless of the branch outcome — a hardware-visible pipeline artifact. RISC-V wisely omitted this, opting for hardware interlocks and branch prediction instead.

Looking at the RISC-V spec, you can read the ISA with pipelining in mind: every instruction format tells you exactly which fields are read in ID, which go to the ALU in EX, and which register is written in WB. This is not coincidence — it is what 'designed for pipelining' looks like.

# RISC-V assembly: trace the pipeline registers manually
# (RISC-V RV32I base integer ISA)
#
# Program: compute x5 = x1 + x2 * x3
# (using only adds for simplicity, since RV32I base has no multiply)
# We will use: x5 = x1 + (x2 + x3)

.section .text
.global _start
_start:
    # Assume: x1 = 10, x2 = 20, x3 = 30 (set by OS or prior code)
    add  x4, x2, x3     # x4 = x2 + x3 = 50
    add  x5, x1, x4     # x5 = x1 + x4 = 60
    # HAZARD ALERT: x4 is written by instruction 1 and read by instruction 2!
    # In a 5-stage pipeline without forwarding, instruction 2 would read
    # the OLD value of x4 (not yet written back by WB).
    # This is a RAW (Read After Write) data hazard.
    # Solution 1: insert NOP instructions (wasteful)
    # Solution 2: data forwarding (forwarding the EX/MEM result directly
    #             to the EX stage input of the next instruction)
    # Real RISC-V CPUs use forwarding — covered in the hazards module.

    # Pipeline timing without forwarding (stalls needed):
    # Cycle:  1    2    3    4    5    6    7    8    9
    # add x4: IF   ID   EX  MEM   WB
    # add x5:      IF   ID  ---  ---   EX  MEM   WB
    #                    ^stall^stall
    # x4 is not in register file until cycle 5 (WB)
    # x5's ID stage needs x4 — it must wait until cycle 6 to enter EX

    # With forwarding:
    # Cycle:  1    2    3    4    5    6    7    8
    # add x4: IF   ID   EX  MEM   WB
    # add x5:      IF   ID   EX  MEM   WB
    #                   ^x4 forwarded from EX/MEM register at start of cycle 4