The pipelined datapath: forwarding, stalls and exceptions

CMP-229 built a single-cycle processor and then cut it into five stages to make a pipeline. That first pipeline showed the idea: while one instruction executes, the next is decoded and the one after that is fetched, so in the best case one instruction finishes every cycle. This lesson opens the pipeline up and looks at the hardware that makes it work correctly at speed: the pipeline registers that carry each instruction's state, the forwarding unit that passes results directly between stages, the hazard detection unit that inserts stalls when forwarding cannot help, and the mechanisms that let a pipelined processor stop cleanly when an instruction faults. These details decide whether a real pipeline achieves a CPI near 1 or wastes a third of its cycles.

Maren's Core A is exactly this kind of machine: a classic five-stage, single-issue, in-order RISC-V pipeline. Before comparing it with Core B's dual-issue design, Jonah needs to understand where Core A's measured CPI of 1.40 comes from, and how much of it the compiler could recover by scheduling instructions better.

The five stages and their pipeline registers

The classic pipeline has five stages. Instruction fetch, IF, reads the instruction at the program counter and computes PC + 4. Instruction decode, ID, decodes the instruction, reads up to two source registers and builds the immediate. Execute, EX, performs the ALU operation, computes a memory address or evaluates a branch condition. Memory access, MEM, reads or writes data memory for loads and stores. Write back, WB, writes the result into the register file.

Between each pair of stages sits a pipeline register, named for the stages it separates: IF/ID, ID/EX, EX/MEM and MEM/WB. On every clock edge, each register captures everything the next stage needs about the instruction that just left the previous stage: operand values, the destination register number, the immediate, and the control signals that the decoder generated. Control is decided once, in ID, and then travels down the pipeline with its instruction, so that WB knows to write register x6 three cycles after decode chose to. Seeing the pipeline registers as the place where each instruction's identity lives makes forwarding and exceptions much easier to reason about.

Data hazards and the forwarding unit

A data hazard arises when an instruction needs a value that an earlier instruction has not yet written to the register file. In the sequence add x6, x5, x7 followed by sub x8, x6, x9, the add computes x6 at the end of its EX stage but does not write it until WB, two cycles later, while the sub wants x6 at the start of its own EX stage, one cycle after the add's. Waiting for the write would cost two stall cycles every time a result is used immediately, which in typical code is very often.

Forwarding, also called bypassing, removes most of those stalls. The value the sub needs already exists: it sits in the EX/MEM pipeline register at the moment the sub enters EX. Multiplexers in front of the ALU inputs can choose that value instead of the stale one read from the register file. A forwarding unit compares the source register numbers of the instruction in EX with the destination register numbers of the instructions in MEM and WB and steers the multiplexers. Its conditions, for the first ALU input, read as follows.

Three details matter. The check rd ≠ 0 prevents forwarding a value to an instruction that reads x0, which must always read as zero. The EX/MEM condition is tested first, because when two earlier instructions both write the same register, the more recent one holds the correct value. And the register file itself is designed to write in the first half of a cycle and read in the second, so an instruction in ID can read a value being written by an instruction in WB in the same cycle, covering a dependence three instructions apart without any forwarding path.

The load-use hazard and the hazard detection unit

Forwarding cannot fix every dependence. A load produces its value at the end of MEM, one stage later than an ALU instruction. If the very next instruction uses the loaded register in EX, the value does not yet exist when it is needed, and no wire can send data backward in time. The pipeline must stall for one cycle. A hazard detection unit in ID checks whether the instruction in EX is a load whose destination matches a source of the instruction in ID. If so, it holds the program counter and the IF/ID register for a cycle, so that fetch and decode repeat, and it inserts a bubble by setting all the control signals in ID/EX to zero, which turns that slot into a no-operation as it flows down the pipeline.

Compilers reduce load-use stalls by scheduling: moving an independent instruction between a load and its first use. The optimization is cheap and often effective, because loop bodies usually contain independent work. On Core A, Jonah finds that the classifier's inner loop loads a filter coefficient and immediately multiplies by it; reordering the loop so that the next coefficient is loaded one iteration early removes the stall.

The program below performs the same count mechanically. For each instruction it finds the earliest cycle in which the instruction can enter EX, given when its source registers become available, and reports the stalls. It is a small version of the cycle-level simulators architects use to evaluate pipelines.

# Five-stage pipeline timing: count cycles with and without forwarding
# Each instruction: (text, dest, sources, is_load)
prog = [("lw   x5, 0(x10)",  "x5", ["x10"], True),
        ("add  x6, x5, x7",  "x6", ["x5", "x7"], False),
        ("sub  x8, x6, x9",  "x8", ["x6", "x9"], False),
        ("lw   x11, 4(x10)", "x11", ["x10"], True),
        ("sw   x8, 8(x10)",  None, ["x8", "x10"], False),
        ("and  x12, x11, x8", "x12", ["x11", "x8"], False)]

def run(forwarding):
    ready = {}            # register -> first cycle its value can be used in EX
    ex_prev = 0           # cycle the previous instruction was in EX
    for i, (text, rd, srcs, is_load) in enumerate(prog):
        ex = max([ex_prev + 1, i + 3] + [ready.get(r, 0) for r in srcs])
        stalls = ex - max(ex_prev + 1, i + 3)
        if rd:
            if forwarding:
                ready[rd] = ex + (2 if is_load else 1)   # load data after MEM, ALU result after EX
            else:
                ready[rd] = ex + 3                        # written in WB, read in ID the same cycle
        print(f"  {text:18s} EX in cycle {ex:2d}  stalls {stalls}")
        ex_prev = ex
    total = ex_prev + 2       # MEM and WB of the last instruction
    return total

for fw in (False, True):
    print("forwarding" if fw else "no forwarding")
    t = run(fw)
    print(f"  total cycles {t}, CPI over {len(prog)} instructions = {(t - 4) / len(prog):.2f}")

no forwarding
  lw   x5, 0(x10)    EX in cycle  3  stalls 0
  add  x6, x5, x7    EX in cycle  6  stalls 2
  sub  x8, x6, x9    EX in cycle  9  stalls 2
  lw   x11, 4(x10)   EX in cycle 10  stalls 0
  sw   x8, 8(x10)    EX in cycle 12  stalls 1
  and  x12, x11, x8  EX in cycle 13  stalls 0
  total cycles 15, CPI over 6 instructions = 1.83
forwarding
  lw   x5, 0(x10)    EX in cycle  3  stalls 0
  add  x6, x5, x7    EX in cycle  5  stalls 1
  sub  x8, x6, x9    EX in cycle  6  stalls 0
  lw   x11, 4(x10)   EX in cycle  7  stalls 0
  sw   x8, 8(x10)    EX in cycle  8  stalls 0
  and  x12, x11, x8  EX in cycle  9  stalls 0
  total cycles 11, CPI over 6 instructions = 1.17

The sequence takes 15 cycles without forwarding and 11 with it. Subtracting the four cycles needed to fill the pipeline, the CPI over these six instructions falls from 1.83 to 1.17. Over a long program the fill cost disappears, and the remaining excess over 1.0 comes from load-use stalls, branches and cache misses.

Structural hazards

A structural hazard occurs when two instructions need the same hardware resource in the same cycle. The classic five-stage pipeline avoids most of them by design: separate instruction and data caches let IF and MEM access memory in the same cycle, and the register file has two read ports and one write port, enough for one instruction per stage. Structural hazards reappear when a unit is not fully pipelined. Core A's integer divider, for example, takes 34 cycles and cannot accept a new divide until the previous one finishes, so two divides close together stall the second. The hazard detection unit handles such cases by checking a busy flag. In practice designers accept rare structural hazards when the hardware to remove them would cost more than the stalls.

Control hazards, briefly

Branches create control hazards: the pipeline must fetch the next instruction before it knows whether the branch is taken. In the basic pipeline, the branch outcome is known in EX, so if the pipeline keeps fetching sequentially and the branch is taken, the two instructions fetched behind it must be flushed, costing two cycles. Moving the comparison into ID cuts the penalty to one cycle at the cost of a comparator and forwarding paths in decode. Lesson 4 treats control hazards properly, with branch prediction and speculation, because they become the dominant cost as pipelines grow deeper and wider.

Exceptions and precise interrupts

An exception is an unexpected event that changes control flow: an illegal instruction, a misaligned access, a page fault, an environment call, or an external interrupt from a timer or the radar's data-ready line. A pipeline holds up to five instructions in flight at once, so when one of them causes an exception the processor must decide what state to present to the handler. An exception is precise if all instructions before the faulting one have completed and none after it has changed any architectural state. Precise exceptions let the handler fix the problem, for example by loading a missing page, and resume the program exactly where it stopped. RISC-V requires precise exceptions.

The five-stage pipeline achieves precision by recording exceptions in the pipeline registers instead of acting on them immediately. An instruction that faults in ID or EX carries a flag down the pipeline; when it reaches the point of commitment, conventionally the end of MEM, the processor flushes it and every younger instruction, writes the faulting instruction's address into the exception program counter register, records the cause, and fetches from the handler's address. Because older instructions have all passed that point and younger ones have not written anything, the state is precise. If two instructions fault in the same cycle, the older one wins, because it is further down the pipeline. Lesson 6 shows how out-of-order processors keep the same promise with a reorder buffer.

How deep should a pipeline be?

Splitting work into more stages shortens each stage and raises the clock rate, but each stage adds the delay of a pipeline register and its clock skew, which does not shrink. Hazards also cost more cycles in deeper pipelines, because more instructions sit between the point where a value is produced and the point where it is needed, and a mispredicted branch flushes more work. Performance therefore rises with depth at first and then falls. Studies of real workloads have put the optimum for general-purpose code somewhere around 15 to 20 stages for high-end designs, while power-conscious embedded cores like the NS-5 candidates use 3 to 8 stages, because every pipeline register costs energy on every cycle and the clock rate is limited by power long before it is limited by logic depth.

In this rough model, k is the number of stages, t_logic the total logic delay, t_latch the per-stage overhead and h a hazard rate that grows the stall cost in proportion to depth. Multiplying the two gives a time per instruction that is minimized at a finite k, which is the quantitative version of the argument above.