Instruction Pipelining

The assembly-line idea

Doing a load of laundry has stages: wash, dry, fold. With one load at a time, the washer sits idle while you fold. A smarter way: start washing load 2 while load 1 is drying. Pipelining does the same thing with instructions.

A classic RISC CPU splits every instruction into 5 stages:

Each stage takes one clock cycle. Without pipelining, an instruction finishes every 5 cycles. With pipelining, once the pipe is full, one instruction finishes every cycle.

In the 3D model, the five coloured blocks at the top are the pipeline hardware and the spheres are instructions flowing through it. Below is the space-time diagram: one row per instruction, one column per clock cycle.

Speed-up

For n instructions and k stages:

• Non-pipelined: n × k cycles
• Pipelined (ideal): k + (n − 1) cycles
• Speed-up = nk / (k + n − 1) → approaches k for large n

With 6 instructions: 30 cycles versus 10 cycles — 3× faster. Pipelining doesn’t make a single instruction faster (latency stays 5 cycles); it increases throughput.

Hazards: when the pipeline must wait

1. Structural hazards — two instructions need the same hardware in the same cycle (e.g. a single memory port for both IF and MEM). Fixed with more hardware (separate instruction and data caches).

2. Data hazards — an instruction needs a result that isn’t ready yet:

   lw  r1, 0(r2)
   add r3, r1, r4    ← needs r1, which lw is still loading

3. Control hazards — after a branch, the CPU doesn’t yet know which instruction comes next. Fixed with branch prediction.

Fixing data hazards

Stalling — hold the dependent instruction in ID and insert bubbles (the red cells) until the value is written back. Simple but slow: in the demo, 6 instructions take 18 cycles.

Forwarding (bypassing) — the result actually exists at the end of EX, two stages before WB. Extra wires carry it straight from the EX/MEM or MEM/WB pipeline latch to the ALU input (the green arrows). The same program now takes 11 cycles.

The load-use hazard — a load only has its data at the end of MEM. The next instruction needs it at the start of EX in the same cycle, so even forwarding needs one stall. Compilers avoid it by reordering an independent instruction into that slot.

Code: a pipeline scheduler

def pipeline(instrs, forwarding=True):
    """instrs: list of (op, dest, [sources]). Returns the cycle of each stage."""
    times = []
    for i, (op, dest, srcs) in enumerate(instrs):
        if i == 0:
            IF, ID, EX = 0, 1, 2
        else:
            p = times[-1]
            IF = p["ID"]
            ID = max(IF + 1, p["EX"])
            EX = max(ID + 1, p["MEM"])
        for j in range(i - 1, -1, -1):            # RAW dependencies
            if instrs[j][1] in srcs:
                t = times[j]
                if not forwarding:
                    ready = t["WB"] + 1
                elif instrs[j][0] == "lw":
                    ready = t["MEM"] + 1
                else:
                    ready = t["EX"] + 1
                EX = max(EX, ready)
        times.append({"IF": IF, "ID": ID, "EX": EX, "MEM": EX + 1, "WB": EX + 2})
    return times

prog = [("lw", "r1", ["r2"]), ("add", "r3", ["r1", "r4"]), ("sub", "r5", ["r3", "r6"]),
        ("and", "r7", ["r8", "r9"]), ("or", "r2", ["r5", "r7"]), ("sw", None, ["r2", "r1"])]
print(pipeline(prog)[-1]["WB"] + 1)          # 11 cycles with forwarding
print(pipeline(prog, False)[-1]["WB"] + 1)   # 18 cycles with stalls only

Common mistakes

• Thinking pipelining makes each instruction faster — it makes the stream faster.
• Counting cycles as n × k for a pipeline. The formula is k + n − 1 (plus stalls).
• Forgetting that register files write in the first half of a cycle and read in the second, so WB and ID can share a cycle.