Skip to main content

Hazard Detection: Pipeline Dependencies and Solutions

Trace data, structural and control hazards, understand forwarding and load-use stalls, and connect register dependencies to scheduling.

Pipeline Architecture established the capacity of an ideal stream of independent instructions. Now let one instruction consume another's result. The pipeline must decide whether the value can arrive in time, whether to bypass the register file, or whether the consumer has to wait.

Helpful background

Pipeline architecture

Distinguish latency from throughput, compare pipeline depth and width, and connect ready work to out-of-order execution.

Open full page

Trace the reason for a wait

Start with the RAW scenario and step until the dependent instruction reaches EX. Turn forwarding off and replay the same instructions. Then choose Load-use to find the wait that bypass wiring cannot remove in this model.

Why does this cycle wait?

Settings

Step through the program. Which instruction needs a value or resource next?

IF·empty
ID·empty
EX·empty
MEM·empty
WB·empty

Instructions move IF → ID → EX → MEM → WB.

Cycle
0
Complete
0/5
Stalled
0
Forwards
0

A true RAW dependency keeps its producer. Compare bypassing with waiting for writeback.

Dependency details

Live producer/readiness inspection, not a full scoreboard algorithm. Data-stall cycles: 0; blocked-fetch cycles: 0. Stalled cycles count their union.

  • I0 → I1: RAW on R1
  • I1 → I2: RAW on R4
  • I2 → I3: RAW on R6
I0: R2 [R2] ← initial (committed); R3 [R3] ← initial (committed). Destination: R1 [R1].
I1: R1 [R1] ← I0 (pending); R5 [R5] ← initial (committed). Destination: R4 [R4].
I2: R4 [R4] ← I1 (pending); R7 [R7] ← initial (committed). Destination: R6 [R6].
I3: R6 [R6] ← I2 (pending); R9 [R9] ← initial (committed). Destination: R8 [R8].
I4: R11 [R11] ← initial (committed); R12 [R12] ← initial (committed). Destination: R10 [R10].

Committed register writers

R1: initial · R2: initial · R3: initial · R4: initial · R5: initial · R6: initial · R7: initial · R8: initial · R9: initial · R10: initial · R11: initial · R12: initial

Model details and sources

Scalar in-order, ideal memory, one cycle per stage including MUL/DIV. Each snapshot shows the stages executing during that cycle and writes through its end. Writeback writes before decode reads. Routes connect current MEM (EX/MEM latch) or WB (MEM/WB latch) to EX. A waiting load consumer stays in ID. Store addresses are literals; store data is needed at EX. No caches, branches, numerical execution or out-of-order scheduling.

Sources: CS61C data hazards, structural hazards, and BOOM renaming. This model does not reproduce BOOM.

Authored in-order teaching model. Symbolic values, not measurements.

This is a deterministic, scalar, in-order teaching pipeline with one cycle per stage and ideal memory. Writeback can supply a register read in the same cycle. Even MUL and DIV use the model's one-cycle EX stage; there are no cache misses, numerical instruction execution or branch traces. WAR and WAW views inspect names and renaming without simulating out-of-order scheduling. Cycle counts below apply to these stated assumptions.

What can prevent an instruction from advancing?

Structural hazards: a resource is occupied

Two operations can need the same resource in the same cycle. With one shared memory port, an older load in MEM can conflict with a new instruction fetch. In the explorer, MEM wins and the fetch waits; already-fetched instructions may keep moving.

Separate instruction and data memories avoid that particular conflict. Additional execution units or register-file ports can avoid other conflicts, while arbitration determines which operation waits when capacity is still limited. The CS61C structural-hazard notes explain these resource choices. They do not imply that every real processor is free of structural limits.

Data hazards: a required value is unavailable

A RAW (Read After Write) dependency connects a consumer to its producer:

text
ADD R1, R2, R3    # Produces R1
SUB R4, R1, R5    # Needs that value of R1

Changing the register's name cannot make the required sum exist earlier. The consumer needs either the register-file value or a bypass from the producer, and it must wait if neither can deliver the value in time.

WAR (Write After Read) and WAW (Write After Write) describe different ordering requirements:

DependencyWhat must be preserved?Example
RAWA read receives the intended earlier writeADD writes R1; SUB reads R1
WARA later write does not replace a value before an earlier readADD reads R2; MUL later writes R2
WAWThe final register value comes from the last write in program orderADD writes R1; SUB later writes R1

WAR and WAW are naming dependencies. The fixed-stage, in-order model here preserves their order naturally, so they do not introduce extra stalls. They matter when reads or writes can overtake one another, including more complex pipelines with differing operation latencies. Renaming gives later writes different physical destinations while keeping each read attached to its correct producer.

The renaming views therefore change the name-dependency graph, not the execution order of this explorer. RAW edges remain because their values are still required.

Control hazards: the next instruction address is uncertain

A branch makes the next fetch depend on a condition and target. A processor can wait for resolution or fetch speculatively. A wrong prediction requires discarding younger work from the wrong path and redirecting fetch. The cost depends on where resolution occurs and how recovery works, not simply the total number of stages.

The next lesson, Branch Prediction & Speculation, follows the predictor's state and the recovery decision. The explorer on this page concentrates on data and resource hazards.

Forwarding: use a result before writeback

An ALU result is available after EX in this model, before the instruction reaches WB. A bypass can route it from a later pipeline latch to the consumer's EX inputs. An immediately dependent arithmetic instruction can then execute without waiting for a register-file write.

Without forwarding, the consumer stays in ID until writeback supplies its register read. IF and ID are held, and an empty slot, or bubble, enters EX. Older instructions continue toward completion. CS61C's data-hazard explanation develops this distinction between stalling and bypassing.

Why an immediate load consumer still waits

A load's value appears after MEM, one stage later than the ALU result. If its consumer entered EX immediately behind it, that consumer would need the value before the load had produced it. In this five-stage timing model, holding the consumer for one cycle makes the bypass possible.

Compare load-use timing side by side

Compare a load followed by its consumer

Data hazard · deep dive

LOAD then dependent ADD

Dependent instructions
LOAD R2, [mem]      // R2 won't be written back until cycle 5
ADD  R4, R2, R3     // reads R2 — needs the result early
No forwarding: 2 stalls
Without forwarding, ADD stalls for 2 cycles and completes at the end of cycle 8
InstructionCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8
LDIFIDEXMEMWBNot activeNot activeNot active
ADDNot activeIFIDSTALLSTALLEXMEMWB
MEM→EX forwarding: 1 stall
With MEM-to-EX forwarding, ADD stalls for 1 cycle and completes at the end of cycle 7
InstructionCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8
LDIFIDEXMEMWBNot activeNot activeNot active
ADDNot activeIFIDSTALLEXMEMWBNot active

Forwarding routes the loaded value directly from the MEM stage of LD into the EX stage of ADD, skipping the wait for write-back. Stalls (gray ·) shrink from 2 to 1. The ADD finishes at the end of cycle 7 instead of 8, saving 1 cycle.

Calculated five-stage teaching schedules. A register read can observe WB in the same cycle; a forwarded load becomes available after MEM. Completion is counted at the end of WB. Both schedules preserve the dependency.

The optional comparison follows the same LOAD and ADD through both schedules. With writeback available to decode in the same cycle, no forwarding requires two stall cycles. MEM-to-EX forwarding reduces that to one. The ADD completes one cycle earlier. Other load latencies, cache behavior or bypass paths require a different schedule.

A compiler may fill the gap with independent work. This authored example assumes both loads access valid ordinary memory and can safely move:

text
LOAD R1, 0(R2)     # Produces the first value
LOAD R5, 4(R2)     # Independent work between the first load and its use
ADD  R3, R1, R4
ADD  R6, R5, R7

Under the model's timing, each ADD has enough separation from its load to avoid a load-use bubble. Real instruction scheduling must also preserve exceptions, memory ordering and dependencies.

How hardware detects the dependency

Compare the operands that are actually used

An in-order detector compares a consumer's source-register identifiers with valid older destinations, excluding writes to a hardwired zero register where the ISA has one. It also checks whether the instruction really reads that operand and when the producer's value becomes available.

A matching name is only the start of the decision. The required producer may have an ALU result ready to forward, a load result that needs another cycle, or a value already written back. If multiple older instructions write the same register, the consumer needs its nearest older writer, not whichever match is found first.

Scoreboarding: track readiness and resources

With multiple functional units and unequal latencies, a scoreboard can track busy units, pending register destinations and operand availability. Issue and writeback checks preserve dependencies while allowing work that is ready to proceed. MIT's scoreboarding handout shows why in-order issue alone does not guarantee in-order completion.

Tomasulo: wait for a producer tag

In the classic Tomasulo scheme, reservation stations hold ready operand values or tags naming the producers they await. A completed result broadcasts its tag and value; matching stations capture it and become eligible to execute when all operands are ready.

Tags also separate successive writes to an architectural register, resolving naming dependencies. This is a conceptual bridge to the renaming and issue structures in Pipeline Architecture. Modern implementations vary in their queues, wakeup networks and retirement mechanisms; the explorer above does not simulate Tomasulo. The MIT architecture lectures cover complex pipelines, out-of-order execution and register renaming.

Account for the lost cycles

For the scalar, fixed-depth model, start with the hazard-free finite-run baseline. If BB is the number of extra cycles on the completion path caused by stalls or fetch gaps, then:

T=n+k−1+B,CPI=Tn=1+k−1n+Bn.T=n+k-1+B,\qquad \mathrm{CPI}=\frac{T}{n}=1+\frac{k-1}{n}+\frac{B}{n}.

This is an accounting identity for the model, not a universal estimate of processor CPI. Several blocked instructions in one cycle do not necessarily add several elapsed cycles, and overlapping causes should not be counted twice. The explorer distinguishes data-stall cycles from blocked-fetch cycles so the reason remains visible.

Expose independent work without changing the result

A long dependency chain limits overlap even when hardware has spare width. For example, separate partial sums can expose independent additions before the final combination:

c
// Unsigned addition preserves the result modulo the unsigned range.
unsigned left = a + b;
unsigned right = c + d;
unsigned total = left + right;

Whether this changes generated code or runtime depends on compiler optimization and the target. Floating-point reassociation has different numerical semantics. Compilers can also schedule work from adjacent loop iterations, known as software pipelining, when dependencies and memory accesses permit it. These techniques create scheduling opportunities; they do not guarantee that a particular pipeline stays full.

Operand readiness explains when known instructions can run. A branch raises the next question: which instructions should enter the pipeline before the condition is known? Continue with Branch Prediction & Speculation.

If you found this explanation helpful, consider sharing it with others.

Mastodon