Load-Use Stalls and Control Hazards

Two kinds of pipeline problem cannot be solved by forwarding. After a load, the value simply does not exist yet, so an instruction that needs it must wait. After a branch, the processor does not yet know which instruction comes next, so it has to guess. Together, these two cost a simple pipeline almost all of its lost cycles. Memory that is slower than one cycle adds a third cost. This article explains how each of the three is detected, what it costs, how a pipeline recovers, and what designers and compilers do to reduce the damage.

11 min read | Beginner

What You'll Learn

• Explain why a load-use stall cannot be removed by forwarding
• Describe how the hardware detects the case and inserts a bubble
• Explain what a control hazard is and what a flush costs
• Describe how a pipeline freezes while waiting for slow memory

The Load-Use Stall

An arithmetic instruction has its result at the end of EX, so forwarding can hand it to the next instruction just in time. A load is different. It uses EX to compute the address, and the data arrives from memory at the end of MEM. If the next instruction needs that data at the start of its own EX, it would need a value from the future:

The add has to wait one cycle. After that, forwarding from MEM/WB delivers the value. This one-cycle wait is a load-use stall. It is the smallest cost in the pipeline, and it has a surprising amount of design around it.

Detecting It

The hardware that handles this is called the hazard detection unit, and it works in decode. It checks whether the instruction now in EX is a load, and whether the load's destination register matches either source register of the instruction in decode:

stall = id_ex_mem_read && (id_ex_rd != 0) &&
        (id_ex_rd == if_id_rs1 || id_ex_rd == if_id_rs2);

When it fires, three things happen in the same cycle. The program counter and the IF/ID register keep their values, so the instructions behind are held in place. The control signals going into ID/EX are all set to zero, so a bubble enters EX. Next cycle, the load has moved on, the check no longer matches, and the add continues.

The check should be exact, because a false alarm costs a cycle. An instruction like lui has no source registers, and jal has none either, so the bits in its source fields must not trigger a stall. A simple design may accept a few such false stalls to save logic.

What It Costs

The cost depends on the code. A bubble sort compares two values just loaded from memory, so it stalls once on every comparison. In one test, those stalls took about a tenth of the sort's cycles. Most other small programs had none at all, because the compiler had arranged their loops so that an unrelated instruction sat between each load and its use. This reordering, called instruction scheduling, is explained in What a Compiler Does. A build without scheduling made the array loop about 8 percent slower.

Designs with a longer memory pipeline pay more. Many high-frequency cores need two or three cycles for a load even when the data is in the first-level cache, so the load-use penalty rises with them, and the compiler has a harder job filling the gap.

Control Hazards

A control hazard arises because the processor must fetch the next instruction every cycle, but a branch is not decided until execute. For two cycles, it does not know which instruction comes next. Stopping fetch until it knows would cost two cycles on every branch, and branches are between one in seven and more than one in three instructions. So every pipeline does something smarter: it guesses and carries on.

The simplest guess is "not taken": keep fetching the next instructions in order. If the branch is not taken, nothing is lost. If it is taken, the two wrong instructions in IF and ID must be removed:

This removal is a flush. The two wrong instructions become bubbles, and the program counter is loaded with the target. Nothing permanent has happened, because the wrong instructions had not reached MEM or WB. The cost is 2 cycles per taken branch. Unconditional jumps, jal and jalr, cost the same in a simple design, since their target comes from EX too.

This is the main loss in a simple pipeline. In one test, flushes took about a third of all cycles in a tight array loop and in a linked-list program, and a fifth in a checksum. Loops are the reason. A loop's branch is taken on nearly every pass, which is exactly what "predict not taken" gets wrong.

Reducing the Cost

Designers have tried several ideas:

• Decide earlier. A comparator and an adder in decode can resolve the branch one stage sooner, cutting the penalty to 1 cycle. But the operands may not be ready yet, which needs more forwarding paths and stalls, and it lengthens the decode stage.
• Delay slots. Early RISC designs always ran the instruction after a branch, whether or not the branch was taken, and asked the compiler to put something useful there. That idea is built into the instruction sets of MIPS and SPARC, and it became a burden as pipelines grew. RISC-V does not use it.
• Avoid the branch. Some instruction sets offer conditional moves, which replace a short branch with a data dependence.
• Predict. A better guess removes most of the cost, and it is what nearly all real processors do. This is the subject of the next chapter, which starts with Why Branches Hurt.

When Memory Takes Longer Than a Cycle

So far, memory has answered in one cycle. Real memory often does not. A cache miss, or an access across a bus, can take from a few cycles to hundreds. The pipeline cannot continue, because the load has no value yet, and the instructions behind it are stuck.

The usual response is to freeze the pipeline: every stage holds its contents until memory answers. Mechanically, the pipeline registers all keep their values, by turning off their load enable. It is a global stall, not a bubble in one place.

The cost follows directly from how much the program uses memory. In one test, a memory copy took about 15 percent longer with one extra wait cycle per data access, and about 59 percent longer with four. A checksum, which rarely touches memory, took only about 9 percent longer with four.

A frozen pipeline has a subtle trap. Values passing between stages must not be lost. If a result is on its way to the register file in WB when a freeze begins, and a later instruction needs it by forwarding, the design must make sure that the value is still there when the pipeline wakes up. Designs that were only tested with one-cycle memory have shipped with this kind of bug.

All Three Together

Here is how the three costs combine in a CPI calculation. Assume, for this example, a program with 25 percent loads, of which one in five is followed immediately by its use, and 15 percent taken branches, on a five-stage pipeline with 2 percent of accesses waiting 10 cycles on memory:

This is the CPI stack from The Performance Equation. It shows at once that branches are the first problem to tackle in this example.

Notice how the costs depend on each other. If a predictor removes most of the branch cost, the memory and load-use layers become a larger share of what remains, and they become the next target. Fixing the largest layer first and then measuring again is the usual way to work through a stack.

Priorities When Things Happen Together

Hazards can happen in the same cycle, and the control logic must have a clear order. A flush beats a stall: if a branch in EX has just been found to be taken, the instruction in decode is wrong, so there is no point in stalling it for a load-use hazard. A memory freeze beats both, since nothing can move. Getting these priorities right is a small amount of logic, but it is one of the classic sources of pipeline bugs.

Common Mistakes