Pipelining and hazards

The single-cycle processor of lesson 9 does one thing at a time: while the ALU computes, the instruction memory sits idle, and while data memory is read, the ALU waits. Pipelining puts every unit to work at once by overlapping instructions, the way an assembly line overlaps the building of many cars. Each instruction still takes several steps, but a new one starts every cycle, so throughput approaches one instruction per short cycle. Pipelining is the single most important performance technique in processor design, and every processor you are likely to use is pipelined, most of them deeply. It also introduces problems, called hazards, that arise when overlapped instructions depend on one another, and much of processor design is about handling them. This lesson covers the classic five-stage RISC pipeline, its three kinds of hazard and the standard remedies: forwarding, stalling, instruction scheduling and branch prediction.

The idea: overlap

Consider doing laundry. Washing takes 30 minutes, drying 30 and folding 30. Doing four loads one after another takes six hours. But as soon as the first load moves to the dryer, the second can start washing; with the stages overlapped, four loads finish in three hours, and each additional load adds only 30 minutes. No single load finishes faster, the latency of each is still 90 minutes, but the throughput triples. A processor pipeline works the same way: the latency of each instruction stays about the same or grows slightly, while the rate at which instructions complete increases by roughly the number of stages.

The classic RISC pipeline has five stages, which correspond to the steps of lesson 9's datapath. IF (instruction fetch) reads the instruction and computes PC + 4. ID (instruction decode) decodes it and reads registers. EX (execute) runs the ALU, computing a result, an address or a branch condition. MEM (memory access) reads or writes data memory. WB (write back) writes the result to the register file. Between each pair of stages sits a pipeline register, a bank of flip-flops that holds everything the next stage needs: the instruction's operands, its control signals and its destination register number. At each clock edge every instruction moves one stage forward.

If the stages were perfectly balanced, each taking \(1/k\) of the single-cycle time, a \(k\)-stage pipeline would complete instructions \(k\) times as fast once it was full. Real pipelines fall short for three reasons. The stages are never perfectly balanced, and the clock must suit the slowest. Pipeline registers add their own delay to every stage. And hazards force some instructions to wait. Filling and draining the pipeline also costs \(k - 1\) cycles at the start and end, negligible for long programs.

The program below draws the pipeline diagram for a short instruction sequence, one row per instruction and one column per cycle, as the figure does. With no hazards, the five instructions finish in nine cycles rather than twenty-five.

STAGES = ['IF', 'ID', 'EX', 'MEM', 'WB']

def diagram(instrs, starts):
    """starts[i] = cycle in which instruction i enters IF (stall bubbles shown as --)."""
    last = max(s + len(STAGES) + stalls for s, (_, stalls) in zip(starts, instrs))
    print(' ' * 18 + ''.join(f'{c:>5}' for c in range(1, last)))
    for (name, stalls), s in zip(instrs, starts):
        row = ['  '] * (last - 1)
        seq = STAGES[:2] + ['--'] * stalls + STAGES[2:]
        for k, st in enumerate(seq):
            row[s - 1 + k] = st
        print(f'{name:<18}' + ''.join(f'{x:>5}' for x in row))
    return last - 1

prog = [('addi t0,zero,5', 0), ('addi t1,zero,7', 0), ('lw t2,0(s0)', 0),
        ('sw t3,4(s0)', 0), ('xor t4,t5,t6', 0)]
print('cycles:', diagram(prog, [1, 2, 3, 4, 5]))

                      1    2    3    4    5    6    7    8    9
addi t0,zero,5       IF   ID   EX  MEM   WB
addi t1,zero,7            IF   ID   EX  MEM   WB
lw t2,0(s0)                    IF   ID   EX  MEM   WB
sw t3,4(s0)                         IF   ID   EX  MEM   WB
xor t4,t5,t6                             IF   ID   EX  MEM   WB
cycles: 9

Hazards

Pipelining assumes that each instruction can start one cycle after the previous one. A hazard is a situation in which it cannot. There are three kinds. A structural hazard occurs when two instructions need the same hardware in the same cycle; for example, a single memory shared between instruction fetch and data access would make every load and store collide with a fetch. RISC pipelines avoid structural hazards by design, with separate instruction and data caches and a register file that writes in the first half of a cycle and reads in the second. A data hazard occurs when an instruction needs a result that a previous instruction has not yet produced. A control hazard occurs when the processor does not yet know which instruction comes next, because a branch has not been resolved.

Data hazards and forwarding

Consider add t0, t1, t2 followed by sub t3, t0, t4. The add computes its result in EX in cycle 3 but does not write it to the register file until WB in cycle 5, while the sub wants to read t0 in ID in cycle 3. Without help, the sub must wait two cycles until the value reaches the register file; a pipeline that waits inserts stalls, also called bubbles, which do nothing. But the result already exists at the end of the add's EX stage, in the EX/MEM pipeline register. Forwarding, also called bypassing, adds wires and multiplexers that send it straight back to the ALU input for the sub's EX stage in cycle 4. With forwarding, a dependent ALU instruction runs immediately behind its producer with no stall at all.

The forwarding unit is a small piece of combinational logic. For each ALU input of the instruction in EX, it compares the source register number with the destination register of the instruction in MEM and the instruction in WB. If the newer instruction, in MEM, writes that register, its result is forwarded; otherwise if the one in WB does, its result is forwarded; otherwise the register file's value is used. The checks also confirm that the producing instruction actually writes a register and that the register is not x0, whose value is always zero.

Forwarding cannot solve every case. A load produces its value only at the end of MEM, too late to forward to an instruction immediately behind it that needs the value at the start of its EX. This load-use hazard costs one stall cycle even with forwarding. A hazard detection unit in ID spots it, by checking whether the instruction in EX is a load whose destination matches a source of the instruction in ID, and freezes the PC and the IF/ID register for one cycle while inserting a bubble into EX.

def cycles(instrs, forwarding=True):
    """Count cycles for a straight-line sequence on a 5-stage pipeline.
    instrs: (text, dest, sources, is_load). Returns total cycles and stall list."""
    ready, stalls, start, prev_start = {}, [], 0, 0
    for i, (text, dest, srcs, is_load) in enumerate(instrs):
        start = prev_start + 1 if i else 1                  # earliest IF cycle
        need_ex = start + 2                                 # cycle of this EX stage
        for s in srcs:
            if s in ready:
                avail = ready[s]                            # first EX cycle that can use it
                if need_ex < avail:
                    stalls.append((text, avail - need_ex))
                    start += avail - need_ex; need_ex = avail
        if dest:
            if forwarding:   # ALU result usable next cycle; load result one cycle later
                ready[dest] = need_ex + (2 if is_load else 1)
            else:            # must wait for WB, register read in the same cycle
                ready[dest] = need_ex + 3
        prev_start = start
    return start + 4, stalls

seq = [('lw t0,0(a0)', 't0', ['a0'], True),
       ('add t1,t0,t2', 't1', ['t0', 't2'], False),
       ('sub t3,t1,t4', 't3', ['t1', 't4'], False),
       ('sw t3,4(a0)', None, ['t3', 'a0'], False)]
for fw in (False, True):
    total, st = cycles(seq, fw)
    print(f'forwarding={fw!s:<5}: {total} cycles, stalls {st}')

forwarding=False: 14 cycles, stalls [('add t1,t0,t2', 2), ('sub t3,t1,t4', 2), ('sw t3,4(a0)', 2)]
forwarding=True : 9 cycles, stalls [('add t1,t0,t2', 1)]

Without forwarding, every dependence costs two stalls, six in all for this chain of three dependences. With forwarding only the load-use dependence, from lw to add, still costs one stall; the add-to-sub and sub-to-sw dependences are covered by forwarding paths.

Scheduling to avoid stalls

Compilers know about load-use hazards and try to hide them by reordering instructions: if an independent instruction can be placed between a load and its first use, the stall disappears. The two loops below compute the same array sum. In the first, each loaded value is used by the very next instruction. In the second, the pointer increment has been moved between the load and the add. The simulator counts load-use pairs in the actual instruction stream and estimates the cycles on a five-stage pipeline with forwarding, one stall per load-use pair, four cycles to fill the pipeline, and a two-cycle penalty for each taken branch or jump, which is what predict-not-taken with branches resolved in EX would cost.

    .data
a:      .word 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3
    .text
    .globl main
main:
    la   t0, a
    addi t3, t0, 64
    li   a1, 0
loop:
    lw   t2, 0(t0)
    add  a1, a1, t2          # uses t2 immediately: load-use stall
    addi t0, t0, 4
    bne  t0, t3, loop
    mv   a0, a1
    li   a7, 1
    ecall
    li   a7, 10
    ecall

80
instructions: 73, load-use stalls: 16, taken branches and jumps: 15
5-stage pipeline estimate: 73 + 4 + 16 + 2 x 15 = 123 cycles, CPI = 1.68

    .data
a:      .word 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3
    .text
    .globl main
main:
    la   t0, a
    addi t3, t0, 64
    li   a1, 0
loop:
    lw   t2, 0(t0)
    addi t0, t0, 4           # independent work fills the load delay
    add  a1, a1, t2
    bne  t0, t3, loop
    mv   a0, a1
    li   a7, 1
    ecall
    li   a7, 10
    ecall

80
instructions: 73, load-use stalls: 0, taken branches and jumps: 15
5-stage pipeline estimate: 73 + 4 + 0 + 2 x 15 = 107 cycles, CPI = 1.47

Moving one instruction removed all sixteen load-use stalls without changing the instruction count. Note that the taken branches cost more than the stalls did: the loop branch is taken fifteen times, two cycles each. That is the subject of the next section.

Control hazards and branch prediction

A conditional branch is not resolved until its comparison is done, in EX in the basic pipeline. By then the two instructions behind it have already been fetched. If the branch is not taken, they are the right instructions and nothing is lost. If it is taken, they must be discarded, flushed, and fetching restarted at the target, wasting two cycles. The simplest policy, predict not taken, therefore costs nothing for untaken branches and two cycles for taken ones. Designers shorten the penalty by resolving branches earlier, with a dedicated comparator in ID, which cuts it to one cycle at the cost of more forwarding paths. MIPS chose another route, the branch delay slot mentioned in lesson 5, which executes the instruction after a branch regardless; RISC-V does not have one.

Since most branches are taken in loops, a smarter guess helps. Static prediction guesses taken for backward branches, which are usually loop branches, and not taken for forward ones. Dynamic prediction learns from history. A branch history table, indexed by low bits of the branch's address, records whether each branch was recently taken. A one-bit predictor remembers only the last outcome, so a loop branch mispredicts twice per loop: once on exit and once on re-entry. A two-bit saturating counter must be wrong twice in a row before it changes its prediction, which removes the re-entry misprediction.

def simulate(outcomes, bits):
    """Predict a single branch with a 1-bit or 2-bit saturating counter."""
    top = (1 << bits) - 1
    state, wrong = top, 0               # start strongly predicting taken
    for taken in outcomes:
        predict_taken = state > top // 2
        wrong += predict_taken != taken
        state = min(state + 1, top) if taken else max(state - 1, 0)
    return wrong

# an inner loop of 8 iterations, run 100 times by an outer loop:
# the inner loop branch is taken 7 times, then not taken once, repeatedly
pattern = ([True] * 7 + [False]) * 100
for bits in (1, 2):
    w = simulate(pattern, bits)
    print(f'{bits}-bit counter: {w} mispredictions out of {len(pattern)} '
          f'({100 * (1 - w / len(pattern)):.1f}% correct)')

1-bit counter: 199 mispredictions out of 800 (75.1% correct)
2-bit counter: 100 mispredictions out of 800 (87.5% correct)

Prediction also needs the target address early, before the branch is even decoded, so processors keep a branch target buffer, a small cache mapping branch addresses to their targets, consulted during fetch. Returns are handled with a return address stack that mirrors calls. Modern predictors combine several tables with long histories of recent branch outcomes and reach accuracies well above 95 per cent on typical programs, which matters enormously because deep pipelines pay a large penalty for each misprediction, often 15 cycles or more.

The effect of all hazards on performance can be folded into the CPI of lesson 1. If a fraction \(f_{lu}\) of instructions suffer a one-cycle load-use stall and a fraction \(f_b\) are branches mispredicted at rate \(m\) with penalty \(p\), the pipelined CPI is approximately as follows.

Beyond the five-stage pipeline

Real processors go much further. Deeper pipelines split the work into more, shorter stages to raise the clock rate; desktop processors have had pipelines of roughly 14 to 20 stages, at the cost of larger misprediction penalties. Superscalar processors fetch, decode and execute several instructions per cycle, so their CPI can fall below 1; designers then speak of instructions per cycle, IPC, instead. Out-of-order processors look ahead through a window of hundreds of instructions and execute each as soon as its operands are ready rather than in program order, hiding cache misses and long-latency operations, while special hardware ensures that results are committed in program order so the program behaves as if it ran sequentially. Speculative execution goes further still, executing instructions down the predicted path of a branch before the branch is resolved and discarding them if the prediction was wrong.

Speculation turned out to have a security cost. In 2018, researchers disclosed Spectre and Meltdown, attacks in which speculatively executed instructions that are later discarded nonetheless leave traces in the cache, traces that a program can measure to read memory it should not be able to see. Their discovery led to years of changes in processors, operating systems and compilers. Lesson 11's caches are the channel these attacks use, which is a striking example of the theme of lesson 1: a lower layer leaking through an abstraction.