Pipelining creates overlap, and overlap creates situations in which an instruction cannot safely use a resource or value at the moment its ideal schedule requests it. These situations are hazards. A data hazard concerns dependence between values, a structural hazard concerns competition for hardware, and a control hazard concerns uncertainty about which instruction should execute next. Hazard handling is not an optimization layered on correctness; it is the mechanism that preserves the sequential architectural contract while internal work is concurrent.
Dependence graphs and hazard names
For instructions and with a true read-after-write (RAW) dependence exists when writes a location that reads. must see the value produced by A write-after-read (WAR) anti-dependence occurs when an earlier instruction reads a location that a later instruction writes; the later write cannot occur before the earlier read. A write-after-write (WAW) output dependence occurs when both write the same location and program order determines the final value.
An in-order, single-issue five-stage pipeline reads registers in ID and writes in WB, so RAW hazards are the dominant register hazard. WAR and WAW do not arise when all reads happen before all writes in program order. An out-of-order or multi-issue machine can encounter all three and uses register renaming, issue constraints, and in-order retirement to preserve the architectural result.
The dependence graph is not the same as a hazard schedule. A dependence becomes a hazard only when the producer’s availability and consumer’s demand overlap unfavorably. Two instructions may be dependent but execute without a stall if forwarding provides the value in time. Conversely, a structural hazard can occur between independent instructions.
Find the dependence
What creates a read-after-write data hazard?
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Forwarding and interlocks
Consider:
add r1, r2, r3
sub r4, r1, r5
The add computes its result at the end of EX. In the next cycle, sub needs r1 at the beginning of EX. A pipeline register such as EX/MEM already holds the result, so a forwarding mux can choose that value instead of the stale register-file read. The hazard unit compares the consuming source register with destination registers in older stages and selects the newest value that is known to be available.
The newest match wins. For:
add r1, r2, r3
add r1, r1, r4
add r5, r1, r6
the third instruction must receive the second instruction’s result, not the first’s. A forwarding network that checks only whether “some older instruction writes r1” can silently select stale data. The control priority must prefer the closest producing stage, subject to validity and register-zero conventions.
Forwarding is a form of dynamic bypass around the architectural register file. It does not change the ISA’s register semantics; it changes where the implementation obtains a value. The proof obligation is observational: the consumer’s ALU input must equal the value that a sequential execution would have read at that point.
Forward or stall?
In a five-stage pipeline, ADD produces r3 in EX. The following SUB needs r3 in its own EX stage before ADD reaches writeback.
Which evidence establishes that issuing SUB is safe?
The load-use hazard
A load has a later availability point than an ALU instruction. In a basic five-stage pipeline, address calculation occurs in EX, memory returns data in MEM, and write-back occurs in WB. The instruction immediately after the load reaches EX before the data has returned:
lw r1, 0(r2)
add r3, r1, r4
Forwarding from EX/MEM cannot help because EX/MEM contains the load’s address, not its loaded data. A one-cycle interlock is necessary unless the implementation has an earlier memory or special load-use path. The controller freezes the PC and IF/ID register, injects a bubble into ID/EX, and permits the load to advance. After the bubble, the dependent add reaches EX when the loaded value is available for forwarding from MEM/WB.
The stall is a temporal transformation of the schedule, not an alteration of the instruction stream. The load remains exactly once; the add remains exactly once; the bubble has no architectural identity. A common bug is to freeze the load in ID/EX as well as the dependent instruction, repeating the load indefinitely. Another is to freeze only the PC, allowing the fetched instruction to be overwritten or duplicated. A correct interlock identifies which pipeline registers represent the consumer and which represent older work that must advance.
Structural hazards and resource contracts
Suppose instruction fetch and data access share one single-ported memory. When a load is in MEM, the processor cannot simultaneously fetch the next instruction. The instructions are independent, but the resource is not. The controller must stall fetch, or the implementation must provide separate instruction/data paths, a second port, banking, or a cache hierarchy that permits both requests.
| Contending Stages | Shared Resource | Arbitration Policy | Cycle Action for Stalled Stage | Cycle Action for Granted Stage |
|---|---|---|---|---|
MEM (load/store) vs IF (fetch) | Single-ported memory port | Prioritize MEM (older instruction) | Freeze PC and IF/ID; inject bubble into ID/EX | Complete data access; advance EX/MEM to MEM/WB |
EX (div) vs EX (alu) | Non-pipelined multi-cycle divider | Hold issue until divider ready | Assert stall_EX; freeze preceding pipeline stages | Continue iterative computation until done=1 |
Writeback stage (WB) | Register file write port | Single write-port contention | Stall multicycle functional unit completion | In-order pipeline commits standard ALU/load result |
Resource conflicts should be specified as ownership contracts. A memory port may accept one request per cycle, or accept a request and return a response later. A multiplier may be pipelined and accept one operation per cycle, or be iterative and remain busy for several cycles. The hazard unit must use the actual valid/ready/busy protocol rather than assume every unit has one-cycle latency.
Structural and data hazards can interact. A load-use stall may coincide with a memory response stall. The controller needs a priority and a compositional invariant: older instructions retain their state, younger instructions do not pass an unavailable resource, and no request is duplicated unless the interface explicitly allows retries. The safe default is to make stalls hold all state that identifies an in-flight instruction while allowing independent older work to complete.
Control hazards
A conditional branch determines the next PC from a comparison. Until the condition and target are known, fetch does not know whether the sequential instruction is correct. In the single-issue five-stage pipeline considered here, a branch in EX can have at most two younger instructions in IF and ID. If the branch is taken, those instructions must be invalidated; if it is not taken, they may continue. Wider machines or extra fetch buffers can contain more younger work, but that is a different model.
The simplest policy stalls fetch until resolution. This avoids wrong-path work but costs cycles on every branch. Predict-not-taken fetches sequentially and flushes only taken branches. A static backward-taken/forward-not-taken rule exploits common loop behavior. A dynamic predictor records recent outcomes, perhaps with a branch-history table, two-bit saturating counters, a global history register, or a target buffer. The predictor is an implementation optimization, not part of the ordinary architectural state, unless the ISA exposes prediction hints.
A two-bit saturating counter has states strongly-not-taken, weakly-not-taken, weakly-taken, and strongly-taken. A taken outcome increments toward strongly taken; a not-taken outcome decrements toward strongly not taken. The prediction changes only after crossing the middle boundary, so one anomalous outcome does not immediately reverse a stable loop prediction. This reduces oscillation on branches that are usually taken with one exit.
Target prediction is separate from direction prediction. Knowing that a branch is likely taken is not enough if the target address is unavailable until decode or execute. A branch target buffer caches the target associated with a fetch PC; a return-address stack predicts procedure returns. Predictor structures trade storage and access latency for fewer front-end bubbles.
Worked trace — a two-bit counter on a loop
A loop branch is taken five times and then not taken on exit. The six outcomes below start from the strongly-not-taken state 00. A taken outcome moves one step toward strongly taken; a not-taken outcome moves one step toward strongly not taken.
| Outcome | Counter before | Prediction | Counter after | Correct? |
|---|---|---|---|---|
| T | 00 | not taken | 01 | no |
| T | 01 | not taken | 10 | no |
| T | 10 | taken | 11 | yes |
| T | 11 | taken | 11 | yes |
| T | 11 | taken | 11 | yes |
| N | 11 | taken | 10 | no |
The first two taken outcomes are mispredicted while the counter learns; subsequent taken outcomes are predicted correctly, and the exit is mispredicted. If the loop is short, warm-up costs matter more. A predictor that reacts faster can learn sooner but may also flip after a single anomalous outcome.
A single counter indexed by PC ignores correlation between branches. A global history register records the recent outcomes of other branches and indexes a table of counters, so if (a) followed by if (a && b) can predict b using the outcome of a. A TAGE predictor combines several tables indexed by different history lengths, selects the longest matching entry when it has enough confidence, and falls back to a shorter history or a base predictor when it does not. Longer history captures correlated branches; shorter history limits damage from aliasing and cold entries. Predictor state is microarchitectural: it must be checkpointed or repaired on misprediction but never becomes part of the architectural result.
Use the trace to predict when the dependent add reaches MEM and WB. Then toggle the branch outcome: which instruction disappears, and which older instructions must be unaffected? The stage model assumes forwarding into EX and separate instruction/data memories, so a load-use stall is its only data stall.
Trace a load-use and branch hazard
The detector holds IF/ID, inserts one invalid EX entry, then either keeps the fall-through instruction or flushes it after branch resolution.
- I0:
lw r1,0(r2) - I1:
add r3,r1,r4 - I2:
beq r3,r0,target - I3:
or r5,r6,r7
T = first target instruction; · = invalid bubble; — = empty. Each row shows occupancy during the cycle; branch redirection takes effect at its end.
| Cycle | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | I0 | — | — | — | — |
| 2 | I1 | I0 | — | — | — |
| 3 | I2 | I1 | I0 | — | — |
| 4 | I2 | I1 | · | I0 | — |
| 5 | I3 | I2 | I1 | · | I0 |
| 6 | — | I3 | I2 | I1 | · |
| 7 | — | — | I3 | I2 | I1 |
| 8 | — | — | — | I3 | I2 |
| 9 | — | — | — | — | I3 |
Model scope: single issue, five stages, separate instruction/data memory, one-cycle load-use stall, ALU and load forwarding to EX, and predict-not-taken with EX resolution. Branch outcome is supplied, not computed from registers. The branch traverses WB without writing a register.
- I0:
lw r1,0(r2) - I1:
add r3,r1,r4 - I2:
beq r3,r0,target - I3:
or r5,r6,r7
T = first target instruction; · = invalid bubble; — = empty. Each row shows occupancy during the cycle; branch redirection takes effect at its end.
| Cycle | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | I0 | — | — | — | — |
| 2 | I1 | I0 | — | — | — |
| 3 | I2 | I1 | I0 | — | — |
| 4 | I2 | I1 | · | I0 | — |
| 5 | I3 | I2 | I1 | · | I0 |
| 6 | — | I3 | I2 | I1 | · |
| 7 | T | · | · | I2 | I1 |
| 8 | — | T | · | · | I2 |
| 9 | — | — | T | · | · |
| 10 | — | — | — | T | · |
| 11 | — | — | — | — | T |
Static state: I0 writes back at cycle 5, I1 at cycle 7, and I2 reaches WB at cycle 8. The taken branch squashes I3 before EX; the target reaches WB at cycle 11.
Check the stage and flush invariantsExpandCollapse
The load occupies MEM at cycle 4 and WB at cycle 5. Its consumer is held in ID at cycle 4, reaches EX at cycle 5, MEM at cycle 6, and WB at cycle 7. The branch reaches EX at cycle 6 and resolves at that cycle’s end. A taken branch removes the younger or, but must not remove or accelerate the older add. Advancing add directly from EX to WB is not a legal trace in this model.
Flushes, speculation, and side effects
Speculation lets the processor execute predicted-path instructions before a branch is resolved. Speculative values can occupy internal registers and caches, but architectural side effects must wait until the instruction is known to be on the correct path and older exceptions have been handled. A wrong-path store cannot write memory. A wrong-path system call cannot enter the kernel. A wrong-path register value cannot retire.
| Speculative State Layer | Action on Predicted Path | Action on Branch Resolution (Mispredict) | Architectural Visibility Barrier |
|---|---|---|---|
| Register file | Allocates rename physical register | Restores committed rename map; frees speculative register | In-order reorder buffer (ROB) commit |
| Data cache hierarchy | Line fills and tag updates occur | Lines remain allocated in cache (microarchitectural leakage) | Line invalidation / speculative fence |
| Store buffer | Buffers uncommitted store data | Squashes uncommitted store queue entries | Drain to cache only after instruction retires |
| Memory-mapped I/O | Speculative access prohibited | Trapped or rejected by memory management unit | Strict in-order commit before MMIO transaction |
The security literature shows why “not architecturally visible” is not identical to “unobservable.” Speculative execution can affect caches and other microarchitectural state, and a later measurement may infer information about a discarded path. Architectural hazard handling still requires flushing invalid instructions; security hardening may additionally constrain speculation around sensitive checks. The microarchitecture must document or mitigate such channels according to its threat model.
Renaming and out-of-order hazards
In a superscalar machine, the pipeline may issue instructions out of program order. WAR and WAW hazards are name dependences: two instructions use the same architectural register name even when no true data dependence exists. Register renaming maps each architectural destination to a fresh physical register. A later write no longer destroys a physical register that an earlier read still needs, and two independent writes no longer contend for one storage location.
The rename map changes on dispatch; a reorder buffer or retirement map commits the architectural mapping in program order. If an instruction faults or a branch mispredicts, speculative mappings are discarded and the older committed map is restored. Renaming removes false dependences but cannot remove RAW dependence: a consumer still waits for the physical register produced by its true predecessor.
Worked dependence analysis. For r1=r2+r3; r2=r4+r5; r6=r1+r2, the second instruction has a WAR relationship with the first because it overwrites r2 after the first reads it; renaming gives the second result a new physical register and preserves the first’s source. The third instruction has true RAW dependencies on both earlier results and cannot execute until both physical values are ready. It may issue after the second result even if unrelated instructions between them are still waiting.
Recovery and precise ordering
When a branch prediction fails, the processor identifies the branch’s younger instructions, cancels them, restores the rename state or checkpoint associated with the branch, and redirects fetch to the correct target. When an exception occurs, all younger instructions are discarded while older instructions retire. The recovery mechanism must also restore predictor or speculative state sufficiently to prevent a stale instruction from committing.
| Recovery Phase | Triggering Event | Hardware Mechanism | Invariant Enforced |
|---|---|---|---|
| Pipeline Slot Flush | Branch mispredict in EX | Clear valid bits in IF/ID and ID/EX | No wrong-path instruction modifies registers or memory |
| Rename Map Repair | Misprediction or trap | Revert speculative map table from checkpoint or walk ROB | Architectural register names resolve to committed state |
| Store Queue Drain | In-order retirement | Retire head of ROB; write data to coherent cache | Stores become globally visible strictly in program order |
| Target PC Redirection | Branch resolution in EX | Drive target address into PC_next; resume IF | Next fetched instruction belongs to correct program path |
The cost of recovery includes detection latency, cancellation, rename-map restoration, front-end redirection, instruction-cache access, and pipeline refill. A deeper machine may have a shorter clock but a larger recovery window. This is why branch prediction accuracy is a first-order performance variable rather than a minor implementation detail.
Verification by adversarial traces
Hazard verification should use traces designed to defeat the common case. Include chains of dependent ALU instructions, alternating destinations, load-use pairs, destination register zero, taken and not-taken branches, back-to-back stores, memory stalls, simultaneous hazards, and exceptions immediately after branches. For each trace, record stage occupancy, source values, forwarding selections, stall signals, valid bits, and committed state.
Assertions can state that a consumer never enters EX with an unavailable source, a memory request is issued only once per transaction, a flushed instruction never asserts a side-effect enable, and a retired instruction’s operands equal the reference-model operands. A performance counter can measure stalls but cannot establish correctness; a processor may be fast because it silently uses wrong values.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.5.1: Data Dependency Classification
Classify every dependence in add r1,r2,r3; sub r4,r1,r5; xor r1,r6,r7; add r8,r1,r9 and identify forwarding sources.
HintExpandCollapse
Distinguish true RAW dependencies from name-based WAR and WAW anti-dependencies.
Worked solutionExpandCollapse
The first-to-second pair is RAW on r1; the second-to-third pair is a WAW on r1 if the third writes it, while the third also reads r1 from the second? Here xor r1,r6,r7 overwrites the first result, so the fourth consumer must receive the third result. The implementation must prioritize the newest valid producer. A careful solution distinguishes the architectural names from the actual instruction order.
Exercise 2.5.2: Load-Use Hazard Stall and Forwarding
Design the exact stall/forward behavior for a load followed by two consumers, one immediately adjacent and one separated by an independent instruction.
HintExpandCollapse
Determine the cycle in which memory data is returned and calculate required stall cycles for dependent ALUs.
Worked solutionExpandCollapse
The adjacent consumer requires one bubble in a basic five-stage machine; after the bubble, forwarding from the load’s data-producing stage supplies it. The second consumer may use the first loaded value if one independent instruction provides enough separation, but the exact answer depends on the implementation’s memory and forwarding timing; state that assumption instead of applying a universal rule.
Exercise 2.5.3: Structural Memory Conflict Trace
Give a structural hazard trace for a unified memory and compare separate caches, multiporting, and stalling.
HintExpandCollapse
Show the collision when instruction fetch and data memory access contend for a single unified port.
Worked solutionExpandCollapse
A load in MEM conflicts with instruction fetch in the same cycle. Separate instruction/data caches remove the conflict, multiporting duplicates access hardware and bandwidth, and stalling preserves correctness at lower throughput. The choice is architectural only if latency or ordering is exposed; otherwise it is a microarchitectural trade-off.
Exercise 2.5.4: Branch Misprediction Penalty Calculation
Derive the expected branch penalty for a predictor with frequency 18%, accuracy 94%, and resolution penalty 6 cycles.
HintExpandCollapse
Multiply the branch instruction frequency by the misprediction rate and pipeline recovery cycle cost.
Worked solutionExpandCollapse
Misprediction frequency is per instruction; multiplied by 6 cycles gives 0.0648 CPI, before other stalls.
Exercise 2.5.5: Two-Bit Saturating Predictor State Transitions
Explain how two-bit prediction behaves on a loop with nine taken outcomes followed by one not-taken exit.
HintExpandCollapse
Trace state changes in the four-state machine (strongly/weakly taken/not-taken) across loop iterations.
Worked solutionExpandCollapse
Starting weakly not-taken (01), the first taken outcome is mispredicted and increments the counter to weakly taken (10). The second taken outcome is correctly predicted and moves it to strongly taken (11); the remaining taken outcomes leave it there. The not-taken exit is mispredicted and decrements the counter once, to 10. Other initial states change the warm-up.
Exercise 2.5.6: Register Renaming for Hazard Elimination
Rename a sequence containing WAR and WAW hazards, then identify the remaining RAW dependencies.
HintExpandCollapse
Map architectural register names to distinct physical registers to eliminate false WAR and WAW hazards.
Worked solutionExpandCollapse
Give each architectural destination a fresh physical register. Reads retain the physical versions visible at their dispatch time; WAR and WAW disappear, while a later read of a value produced by an earlier instruction remains RAW and waits for readiness.
Exercise 2.5.7: Wrong-Path Instruction Squashing Invariant
State the invariants required to prove that a mispredicted branch cannot commit a store.
HintExpandCollapse
Ensure all pipeline registers populated on wrong-path execution are cleared before state commitment.
Worked solutionExpandCollapse
Every wrong-path instruction has a valid bit that becomes false on flush; memory write enable is gated by valid and retirement/commit permission; the store queue or memory system accepts only committed stores; recovery removes younger entries. Together these establish that a mispredicted store can be computed internally but never changes architectural memory.
References & Further Reading
- Hennessy, J. L., & Patterson, D. A. (2019). Computer Architecture: A Quantitative Approach (6th ed.), Chapter 3 (“Instruction-Level Parallelism and Its Exploitation”). Morgan Kaufmann. (Hazards, forwarding, speculation, and branch prediction.)
- Smith, J. E. (1981). A Study of Branch Prediction Strategies. ISCA, 135–148. (Two-bit saturating counters and branch-history prediction.)
- Seznec, A., & Michaud, P. (2006). A Case for (Partially) TAgged GEometric History Length Branch Prediction. Journal of Instruction-Level Parallelism, 8, 1–23. (TAGE.)
- MIT 6.004 Computation Structures: lecture notes and examinations
- MIT 6.004 learning objectives
- UC Berkeley CS 61C: five-stage pipeline notes