Data Hazard

computer-architecture

Definition

Data Hazard

A data hazard is a pipelined hazard in which an instruction needs a value that a previous instruction has not yet written back.

So the later instruction depends on a register or other result that is still being produced by the pipeline.

Handling

Real pipelined processors often combine these techniques.

• rearranging code reduces hazards statically;
• forwarding resolves many hazards dynamically;
• stalling is used when the other methods are not enough.

Inserting Nops

Inserting Nops

One way to avoid a data hazard is to insert explicit nop instructions between the instruction that produces a value and the instruction that consumes it.

This gives the pipeline enough time to write the value back before it is read.

The method is simple, but it wastes cycles.

Leaky abstraction nop instructions depend on details of the hardware pipeline.

In particular, the required number of nop instructions depends on how many stages the pipelined processor has and when results become available. So the binary is no longer independent of the concrete hardware.

Example

add s8, s4, s5
nop
nop
sub s2, s8, s3
or  s9, t6, s8
and s7, s8, t2

The nop instructions create delay slots so that s8 is available before sub reads it.

Rearranging Code

Rearranging Code at Compile Time

A compiler can move independent instructions between the producer and the consumer.

This fills the gap that would otherwise be occupied by nop instructions. The idea is the same as inserting delays, but useful work is done instead of idling.

Example

add s8, s4, s5
sub s2, s8, s3
or  s9, t6, s8
and s7, s8, t2

rearranging the shown instructions does not help much, because sub, or, and and all depend on s8.

So this method only helps if some independent instruction is available that can be moved into the gap after add.

Forwarding Data

Forwarding Data at Run Time

Forwarding, or bypassing, sends a result directly from a later pipeline stage to an earlier stage that needs it.

So the dependent instruction does not have to wait until the value is written back to the register file.

This removes many data hazards, but only when the required value has already been computed somewhere in the pipeline.

Forwarding cases

1. if the execute-stage source register matches the destination register of the memory stage, forward from the memory stage;
2. otherwise, if it matches the destination register of the write-back stage, forward from the write-back stage;
3. otherwise, use the value read from the register file.

For the first ALU input, this can be written as:

$$\text{ForwardAE}=\{\begin{array}{ll}10& \text{if }(Rs1E=RdM)\wedge RegWriteM\wedge (Rs1E\ne 0)\\ 01& \text{if }(Rs1E=RdW)\wedge RegWriteW\wedge (Rs1E\ne 0)\\ 00& \text{otherwise}\end{array}$$

The equation for ForwardBE is analogous, with Rs1E replaced by Rs2E.

Example

add s8, s4, s5
sub s2, s8, s3
or  s9, t6, s8
and s7, s8, t2

the value produced by add for s8 can be forwarded directly to the later instructions instead of waiting until s8 is written back to the register file.

Stalling the Processor

Stalling the Processor at Run Time

If the needed value is still not available, the processor can stall the pipeline.

In that case, early pipeline stages are held in place and one or more bubbles are inserted until the data hazard disappears.

This preserves correctness, but reduces throughput.

Example

add s8, s4, s5
sub s2, s8, s3
or  s9, t6, s8
and s7, s8, t2

the processor may detect that sub needs s8 too early and temporarily stop the advance of the pipeline. During that pause, a bubble is inserted until the value of s8 becomes available.

Load-use hazard

The classic case that still needs a stall is the load-use hazard.

If the instruction in the execute stage is a load and the instruction in the decode stage already wants to read the loaded register, forwarding alone is not enough, because the loaded value is not available yet.

A common detection condition is:

$$\mathrm{lwStall}=((Rs1D=RdE)\vee (Rs2D=RdE))\wedge {\mathrm{MemToReg}}_E$$

and then:

$$\mathrm{StallF}=\mathrm{StallD}=\mathrm{FlushE}=\mathrm{lwStall}$$

So the front of the pipeline is stalled and a bubble is inserted behind the load.

Example

Register value not ready

Suppose one instruction computes a value for a register, and the following instruction immediately wants to read that same register.

If the first instruction has not yet reached write-back, the correct value is not yet available in the register file. This creates a data hazard.

A typical instruction sequence is:

add s8, s4, s5
sub s2, s8, s3
or  s9, t6, s8
and s7, s8, t2

Here the first instruction produces the value for s8, and the following instructions try to read s8 before that value has necessarily reached the register file.