Interlocks, Bubbles, and How a Stall Propagates Backwards

A pipeline with no interlock produces wrong answers whenever a dependency cannot be forwarded. The interlock is the hardware that notices and holds the dependent instruction until the value exists. The interesting part is not the comparison that detects the hazard; it is the mechanism that stops the right set of stages for the right number of cycles, because a stall is not a local event. Freezing one stage while the stages ahead of it continue means the instruction in that stage is overwritten by the one behind it. The freeze has to propagate backwards, and something has to be inserted ahead to fill the hole the freeze creates.

A stall is a freeze plus an injection

Consider the load-use case from forwarding paths. The consumer sits in ID and needs one more cycle before its operand exists. The producer is in EX and must keep moving: it has to reach MEM to fetch the data. So the consumer’s stage freezes and the producer’s stage advances. Now the IF stage, which has been fetching into the IF/ID register that the consumer occupies, cannot write that register. If IF keeps fetching, the fetched instruction is dropped, and the PC has advanced past an instruction that was never executed.

Two things must therefore happen in the same cycle:

1. The PC and the IF/ID register are held, so the instruction in IF stays in IF and is re-fetched next cycle (or simply held, depending on whether IF has internal state).
2. A control word with every write enable cleared is injected into the ID/EX register, so the EX stage does something harmless this cycle.

That injected control word is the bubble. It occupies a stage for a cycle without changing architectural state. If the pipeline’s control is carried alongside the data as a bundle of write enables and multiplexer selects, the bubble is simply the all-zeros bundle, and injecting it requires no special datapath.

        cycle 1  cycle 2  cycle 3  cycle 4  cycle 5  cycle 6
lw x1   IF       ID       EX       MEM      WB
add x2   -        IF       ID       ID       EX       MEM
and x3   -        -        IF       IF       ID       EX

and is held in IF for one cycle because the register it would have written is occupied. Nothing is lost: the PC does not advance, so and is still there when the freeze lifts.

Why the freeze must travel backwards and not forwards

A forward-propagating freeze would be simpler to describe and wrong. Suppose the interlock freezes only ID and lets IF continue. The fetched instruction lands in IF/ID, overwriting the stalled consumer, and the consumer is gone. Suppose instead it freezes ID and IF but not the stage before ID in a deeper pipeline: the same overwrite happens one stage earlier. The rule is that every stage whose output feeds a frozen stage must also be frozen, which by induction means every stage from the hazard point back to fetch.

The stages ahead of the hazard — EX, MEM, WB in this example — must not be frozen, because they hold instructions that are older and must complete. Freezing them would be harmless for correctness but would turn a one-cycle stall into a pipeline-wide drain, which is the whole cost the interlock exists to avoid.

This asymmetry is why an interlock is drawn as a signal that runs right-to-left along the pipeline registers. Each register has a hold input; the hazard logic asserts hold on the registers from the stalling stage backwards to IF, and asserts clear (or select-bubble) on the register immediately ahead of the stall point.

Detecting the hazard without false positives

The comparison itself is a small amount of logic, but the conditions attached to it decide whether the machine is correct and whether it stalls unnecessarily.

A source register matches a destination only if the destination is actually written. An instruction that writes no register — a store, a branch, a no-operation — must not trigger a stall even if its destination field happens to equal the consumer’s source. The write-enable bit carried down the pipeline is what distinguishes them. Without it, every store whose unused destination field aliases a live register causes a spurious stall.

The zero register must be excluded, for the reason given in the forwarding article: it is hardwired and never a real dependency.

The distance matters. In a five-stage pipeline the load-use interlock only needs to compare the consumer in ID against the producer in EX. A producer in MEM or WB is far enough ahead that the MEM/WB bypass covers it. A producer in ID has not yet read its own operands and cannot have produced a value. So the detector is one comparator per source operand against one pipeline register, not a search over all in-flight instructions.

/* Hazard detection for one cycle. Returns 1 if the pipeline must stall. */
int load_use_hazard(const struct if_id_reg *id, const struct idex_reg *ex)
{
    if (!ex->mem_read)                 /* only loads are late */
        return 0;
    if (ex->rt == 0)                   /* writing the zero register: no dependency */
        return 0;
    /* MIPS-style encoding: rs is always a source; rt is a source unless the
       instruction writes rt (lw, or an immediate-form ALU op). */
    int uses_rt = id->uses_rt;
    return (ex->rt == id->rs) || (uses_rt && ex->rt == id->rt);
}

The uses_rt flag is the part that a decoder must supply and that a naive implementation omits. On an encoding where the same field is a source for one instruction and a destination for another, the comparison cannot be made from the register numbers alone.

Stalls that last more than one cycle

The load-use interlock holds for exactly one cycle because the producer advances one stage per cycle and after one cycle it is in MEM/WB where the bypass reaches. An interlock on a multi-cycle unit holds for as many cycles as the unit’s remaining latency. A divide with a twelve-cycle latency stalls the consumer for twelve cycles if the consumer is issued immediately behind it, and the hold signal stays asserted for that whole time.

There are two ways to build the multi-cycle case. The counter approach keeps a down-counter in the interlock, loaded with the unit’s latency when the operation issues, and asserts hold while it is nonzero. The scoreboard approach gives each unit a busy bit and a destination tag, and the interlock asserts hold whenever the consumer’s source matches a busy unit’s tag. The scoreboard generalizes to several units and to out-of-order issue, and its cost is the tag comparison against every busy entry rather than against a single pipeline register.

The important consequence for scheduling is that a multi-cycle stall blocks everything behind the consumer, including independent instructions. A single in-order pipeline cannot skip over the stalled instruction, so one long-latency consumer converts into a full pipeline bubble of that length. This is the specific inefficiency that dynamic scheduling and out-of-order issue were invented to remove, and it is why the interlock’s cost is quoted as the exposed latency rather than the unit’s latency: if no independent work is available to fill the gap, the whole gap is exposed.

Interlocks in the presence of exceptions

A stall interacts badly with anything that must be exact. If a stage ahead of the stall point raises an exception while the pipeline is frozen, the exception must be attributed to the right instruction and the frozen instruction must be restartable at the same PC. Freezing the PC is what makes the restart possible: the stalled instruction has not advanced, so its PC is still in the register and the handler can return to it.

This is one reason the interlock holds the PC rather than merely suppressing the write. An implementation that lets the PC advance and marks the instruction invalid has to reconstruct the address later, and reconstruction is where restart bugs live. The general machinery for making a pipeline’s state exact at an arbitrary instruction boundary is covered in precise exceptions and pipeline restart.

The cost of an interlock, stated as CPI

An interlock that fires with frequency f and holds for c cycles adds f times c to the CPI. The load-use case has c = 1. A divide with c = 12 and a frequency of one per thousand instructions adds 0.012, which is negligible. The same twelve cycles at a frequency of one per twenty instructions adds 0.6, which is not.

This arithmetic explains why interlocks are the right answer for rare long-latency operations and the wrong answer for common ones. It also explains why a machine that stalls on every load-use pair is paying roughly the load frequency in CPI, and why compilers that schedule around the one-cycle gap earn a measurable improvement on such machines but not on machines with dynamic scheduling.

The final property worth stating is that an interlock is invisible in the instruction set. Software does not see the bubble; it sees only that the program takes more cycles than the instruction count. That invisibility is the design goal, and it is what distinguishes a hardware-managed pipeline from one that exposes delay slots and pushes the scheduling problem to the compiler.