Data Hazards and Forwarding

A data hazard happens when an instruction in a pipeline needs a value that an earlier instruction has not finished producing. Programs do this constantly, because most instructions use the result of the one just before. Without help, the processor would have to wait several cycles each time and would lose much of the gain from pipelining. Forwarding is the simple circuit that solves most of the problem by passing a result straight to where it is needed. This article explains the kinds of data dependence, how stalling works, how forwarding works, and what it costs and gains.

12 min read | Beginner

What You'll Learn

• Identify read-after-write dependences in a sequence of instructions
• Explain how a pipeline detects a data hazard and stalls
• Describe the forwarding paths and how the select signals are computed
• Compare the gain from forwarding with its cost in area

When Instructions Depend on Each Other

Look at these two instructions:

add  a0,a1,a2      # a0 = a1 + a2
sub  a3,a0,a4      # uses the new a0

The sub needs the result of the add. In a five-stage pipeline, registers are read in decode (ID) and written in write back (WB). The add writes a0 at the end of its fifth stage, but the sub reads its registers while the add is only in execute (EX):

If the hardware did nothing, the sub would read the old a0 and compute a wrong result. The program says "use the value I just computed", and a correct processor must behave as if each instruction finished before the next one began. This rule, that overlap must never be visible to the program, is the basic contract of any pipeline.

The case above is a read-after-write (RAW) dependence, also called a true dependence: an instruction reads what an earlier one wrote. Two other kinds exist. Write-after-read and write-after-write dependences arise when instructions merely reuse a register name, with no value passing between them. In a simple pipeline these cause no trouble, because every instruction reads in the same stage and writes in the same stage, always in program order. They matter in out-of-order processors, as Out-of-Order Execution and Register Renaming explains.

A dependence belongs to the program. A hazard is what happens when the pipeline cannot honor that dependence without doing something special. In a five-stage pipeline, a RAW dependence is a hazard if the two instructions are close together: one, two or three positions apart.

The Simple Fix: Stalling

The simplest solution is to make the sub wait in decode until the add has written its result. The hardware compares the source register numbers of the instruction in decode with the destination register numbers of the instructions further along. If they match, it holds the decode stage and everything behind it, and sends bubbles, empty slots, into execute:

The stall lasts two cycles here, because the register file passes a value being written straight through to a read in the same cycle, as Registers and the Register File describes. Without that detail it would be three.

This works, and it is always correct, but it is expensive. Dependent neighbors are everywhere in compiled code. In one test on six small programs, a five-stage pipeline that always stalled had a CPI of about 1.75 to 2.2, so it spent nearly as many cycles waiting as working.

The Better Fix: Forwarding

Look at the first diagram again. The add's result does not really appear in cycle 5. The ALU computes it at the end of cycle 3, and from then on it sits in a pipeline register. The sub needs it at the start of its own EX, cycle 4. The value already exists, one stage ahead, on its way to the register file. So why not take it from there?

Forwarding, also called bypassing, does exactly that. Each ALU input gets a multiplexer, a selector, that chooses between three sources:

• the value read from the register file, when there is no hazard;
• the result held in EX/MEM, when the previous instruction wrote the register;
• the value held in MEM/WB, when the instruction before that wrote it.

The select signals come from the same kind of comparison as stalling, now done in the EX stage. For operand A:

if (ex_mem_reg_write && ex_mem_rd != 0 && ex_mem_rd == id_ex_rs1)
    fwd_a = FROM_EX_MEM;          // the newest value wins
else if (mem_wb_reg_write && mem_wb_rd != 0 && mem_wb_rd == id_ex_rs1)
    fwd_a = FROM_MEM_WB;
else
    fwd_a = FROM_REGFILE;

Three details in this short code each prevent a real bug. The check on the write enable matters because a store or a branch has a register field that is not a destination. The check against register 0 matters because x0 always reads as zero: an instruction may name it as a destination, but the result must not be forwarded. And the order matters: if both stages are writing the same register, the nearer one is the newer value, so it must win. Consider:

addi a0,a0,1       # a0 = old + 1
addi a0,a0,1       # a0 = old + 2
addi a0,a0,1       # a0 = old + 3, must take the middle result

Store data needs the same treatment. In sw a0,0(sp) right after an add to a0, the data must be forwarded too, along with the address, so the path to the memory stage also has a multiplexer.

What Forwarding Gains and Costs

With forwarding, nearly all arithmetic dependences cost no cycles at all. On the same six programs, the speedup from adding forwarding ranged from about 1.17 for an array loop to about 1.7 for a memory copy. Cycles per instruction fell to between about 1.26 and 1.6. The added hardware was just a few multiplexers and comparators: about 2.5 percent more area in one small core.

That is one of the best trades in processor design, and it is why every pipeline since the first RISC designs has it. It does have one hidden price, though. The multiplexers sit right in front of the ALU, on the most timing-critical path in the core. Each extra input makes the path a little longer, and in large cores with many pipeline stages and many ALUs the forwarding network becomes a real limit on the clock frequency. Designers sometimes leave out a rarely used path and stall in that case instead.

What Forwarding Cannot Fix

Forwarding only works if the value exists when it is needed. A load does not have its value until the end of the memory stage, one stage later than an ALU result. So an instruction that uses a loaded value right away still has to wait one cycle, however many forwarding paths there are. Load-Use Stalls and Control Hazards covers that case.

Long operations are similar. A multiply that takes three cycles, or a divide that takes thirty, produces its result late, and dependent instructions must wait. The detection logic has to know how long each operation takes, or track which registers are waiting for a result. A simple table of such registers is called a scoreboard.

Forwarding also interacts with stalls. When the pipeline is frozen for any reason, the pipeline registers hold their values and forwarding must still deliver the right one when the pipeline restarts. Handling that correctly is exactly what went wrong in the bug described in the box above.

How Much Hardware Is Involved

Forwarding is small because each piece is simple. There are two comparators per source register, each comparing two 5-bit register numbers, so a few dozen gates. There are two 3-to-1 multiplexers of 32 bits each, and a third for the store data. Nothing here stores any state. The whole unit is combinational logic that recomputes its select signals in every cycle from the values in the pipeline registers, which is why it can be described in a dozen lines of RTL and why it adds so little area.

The Compiler's Part

Hardware handles hazards automatically, so a program is correct whatever the order of its instructions. But the compiler can still help. Since a load followed immediately by its use costs a cycle, a good compiler places an unrelated instruction between them where it can, a technique called instruction scheduling, explained in What a Compiler Does. Some very early RISC processors left hazards to software entirely: the compiler had to insert nop instructions, which do nothing, and a wrong program simply computed the wrong answer. The name MIPS, a well-known early RISC, stood for "Microprocessor without Interlocked Pipeline Stages". An interlock is the hardware stall, and later versions added them anyway, because binary code should not depend on one pipeline's exact timing.

Common Mistakes