4.1.19 · D5Computer Architecture (Deep)
Question bank — Pipeline hazards — structural, data (RAW - WAR - WAW), control
Reminder of the vocabulary these questions lean on, so no symbol is unearned:
Recall The five stages (needed for every "which cycle" argument below)
IF fetch instruction, ID decode + read registers, EX ALU computes, MEM load/store data, WB write result into the register file. Reads happen early (ID), writes happen late (WB) — most trap answers hinge on this timing.
Before the traps, three short visual explainers set up everything the questions lean on: a picture of why a RAW gap exists and how forwarding closes it, a data-flow graph of why only RAW is irreducible, and a full derivation of the performance symbols so every letter is earned.
0. Setup pictures (read these first)
0.1 The RAW gap, the load-use stall, and the forwarding arrow
Look at the timeline below. It is the "conveyor belt": each row is one instruction, each column one clock cycle, and a box in column means that instruction occupies that stage during cycle .
- Top block (ALU→ALU RAW): the ADD produces R1 at the end of its EX (green box). The SUB wants R1 at the start of its EX, one cycle later. The value already exists — the orange forwarding arrow carries it straight from the EX/MEM latch into SUB's EX input, so zero stalls.
- Bottom block (load-use RAW): the LOAD's value only exists at the end of MEM (red box). The dependent SUB needs it in EX at the same cycle — there is no earlier place to grab it. So one bubble (gray) is inserted, then forwarding works. This is the single RAW that forwarding alone cannot fix.
0.2 Why only RAW is a true dependence
The graph below shows two instructions and the three ways they can share a register name. Solid blue = real data flowing; dashed gray = merely a reused name.
- RAW (solid): value physically flows producer→consumer. Rename all you like — the consumer still must wait for the producer. Irreducible.
- WAR / WAW (dashed): the only reason they conflict is that both instructions picked the same register name. Hand the later write a fresh name (register renaming — literally: keep a pool of spare physical registers and map each new write to an unused one) and the arrow disappears. Name dependences.
0.3 The performance symbols, defined and derived
Every symbol in the formulas below is defined here first, then derived, so nothing is used before it is earned.
Deriving step by step. WHAT: average cycles per instruction = ideal + extra stalls. WHY each factor: a branch only stalls when mispredicted. Pick a random instruction. It is a branch with probability ; if so, it mispredicts with probability ; if so, it costs cycles. Multiply the independent probabilities and the penalty:
How is actually measured (this is the symbol the reviewer flagged as opaque): is the sum of average stall cycles per instruction from each hazard family, each computed the same "fraction × penalty" way: For example = (fraction of instructions that are load-use pairs) bubble; = (fraction of cycles a resource collides) . So is never mystical — it is always rate of hazard cycles that hazard costs, added up.
True or false — justify
A single memory port shared by IF and MEM always causes a hazard on every cycle.
False — the collision only happens on cycles where one instruction is in MEM while another is in IF. In a steady stream that's frequent, but a cycle where nothing is in MEM has no conflict; the hazard is about simultaneous demand, not constant demand.
WAR hazards can occur in the classic in-order 5-stage pipeline.
False — in-order, reads happen in ID (early) and writes in WB (late), and the earlier instruction reaches ID before the later reaches WB, so the read always precedes the write. WAR needs out-of-order execution or writes in early stages to become real.
Forwarding removes all data hazards.
False — the load-use RAW survives (see figure s01, bottom block): a load's value is ready only at end of MEM, but a dependent instruction needs it in EX at the same cycle, so there's no earlier stage to forward from. One stall bubble is mandatory, then forward.
RAW, WAR, and WAW are all "true" data dependences.
False — only RAW is a true dependence (real value flow, the solid arrow in figure s02). WAR and WAW are name dependences caused by reusing register names; give each write a fresh name via register renaming and they vanish.
Register renaming can eliminate a RAW hazard.
False — renaming only removes WAR and WAW (name dependences). RAW is genuine producer→consumer data flow; no amount of renaming lets the consumer read a value that hasn't been produced yet.
Structural hazards are fixed by forwarding.
False — forwarding moves values between stages; structural hazards are about resources, and two totally independent instructions still collide. The fix is more hardware (e.g. split I-cache and D-cache).
A branch that is correctly predicted still costs the branch penalty.
False (for a good predictor) — with correct prediction the pipeline keeps fetching down the right path, so no flush and near-zero penalty. The penalty is paid only on misprediction, which is why multiplies by the mispredict rate .
Adding more pipeline stages () always increases real speedup.
False — ideal speedup rises with , but deeper pipelines resolve branches later (larger penalty ) and expose more hazards, raising the stall term . Since , past some point extra stages hurt more than they help.
Two instructions writing different registers can still form a WAW hazard.
False — WAW is an output dependence, meaning both write the same destination. Different destinations mean the final register-file state is unambiguous, so there is nothing to order.
A NOP inserted by the compiler and a bubble inserted by hardware are the same thing.
Essentially true in effect — both consume a cycle doing no useful work to preserve correctness. The distinction is who inserted it: a compiler NOP is a real instruction in the code, a hardware bubble is a stall the control logic injects at runtime.
Spot the error
"I2 reads R1 in ID at cycle 3, I1 writes R1 in WB at cycle 5, so we lose the value — nothing can save us but a stall."
The error: forgetting forwarding. As figure s01 (top block) shows, I1's result exists at end of EX (cycle 3), and we can route it from the EX/MEM latch straight into I2's EX input, so zero stalls are needed for an ALU→ALU RAW.
"WAW never matters because the two writes go to the register file in program order anyway."
The error: assuming writes are ordered. In an in-order single-write-port pipeline that's true, but with variable-latency units (a slow MUL, a fast ADD) or out-of-order issue, the later instruction can write first, leaving the stale value — that's exactly the WAW hazard.
"The load-use stall is a control hazard because the pipeline stalls."
The error: classifying by symptom, not cause. Stalling is the fix, not the category. Load-use is a data (RAW) hazard (figure s01, bottom) — it's about a value not being ready; a control hazard is about fetching the wrong instructions after a branch.
"CPI = 1 + b·p, because every branch costs the penalty."
The error: dropping the mispredict rate . Only mispredicted branches flush, so the correct steady-state cost is ; omitting overestimates the branch penalty by a factor of .
"Split L1 caches solve data hazards."
The error: mixing categories. Splitting into I-cache and D-cache removes the structural hazard of one memory port serving IF and MEM. Data hazards (value dependences) are untouched by it — they need forwarding, stalls, or renaming.
"Delayed branches eliminate the control hazard, so they cost nothing."
The error: assuming the delay slot is always fillable with useful work. If the compiler can't find a safe, useful instruction to place in the slot, it must fill it with a NOP — which costs a cycle, just like a stall.
Why questions
Why is RAW called a "true" dependence while WAR/WAW are not?
Because RAW reflects actual data flowing from producer to consumer (the solid arrow in figure s02) — the program's meaning requires it. WAR/WAW arise only from reusing register names; rename the storage and the dependence disappears, proving it was never about the data itself.
Why do reads-in-ID and writes-in-WB make WAR impossible in-order?
The earlier instruction reaches its read (ID) stage before the later instruction reaches its write (WB) stage, because stages are earlier in the pipe and instructions enter in order. So the read is guaranteed to happen first — WAR's bad ordering can never arise.
Why can forwarding not fix the load-use hazard?
Forwarding moves a value across space (stage to stage) but cannot move it back in time. The load's data first exists at end of MEM; the consumer needs it one stage earlier (EX in the same cycle). There is no earlier source to forward from, so one bubble is unavoidable.
Why does good branch prediction matter so much for performance?
In , the branch cost scales with the mispredict rate . Driving from, say, 0.5 down to 0.05 cuts branch-induced stalls by an order of magnitude — a huge lever because branches are a large fraction of typical code.
Why does the speedup formula use and not ?
Single-cycle execution takes stage-times per instruction; the pipeline takes cycles per instruction in steady state (see CPI and performance equation). Speedup is the ratio of these throughputs, not their difference — a ratio because we compare rates of completion.
Why does adding stalls relate to Amdahl's Law?
Stalls act like a serial, non-overlappable fraction of the workload. Amdahl's Law says the part you can't speed up bounds your overall gain — deep-pipeline speedup is capped by the stall cycles that no amount of extra stages can overlap away.
Why is out-of-order execution what creates the need to worry about WAR and WAW?
Out-of-order issue lets a later instruction read or write a register before an earlier one, breaking the in-order timing that made WAR/WAW harmless. This is precisely why such machines pair OoO with renaming to neutralise those name hazards.
Edge cases
What hazard type appears when a program has zero data dependences but heavy memory traffic on a single-port memory?
A structural hazard only. With no shared registers there are no data hazards, but IF and MEM still contend for the one memory port — resources conflict even when values don't.
Is there a RAW hazard between ADD R1,R2,R3 and ADD R4,R5,R6?
No hazard of any kind — the destination and sources are disjoint, so no read-after-write, no shared resource beyond normal staging, no control change. Fully independent instructions pipeline freely.
Does a branch that is always taken and always correctly predicted taken incur a control-hazard penalty?
With a dynamic predictor that learns "taken," it fetches the target correctly and pays near-zero penalty. Under a naive static predict-not-taken scheme it would mispredict every time and pay each — the answer depends entirely on the prediction policy.
What happens to WAW if both writes are to R0 on an architecture where R0 is hardwired to zero?
No real WAW — writes to a hardwired-zero register are discarded, so there is no meaningful "final value" to order. The name dependence is void because the storage never actually changes.
A two-instruction sequence has both a RAW and a WAW on the same register. Which fix addresses which?
The RAW needs true handling (forwarding or a stall) because it's genuine data flow. The WAW is a name dependence removed by renaming. They're independent problems on the same name and require different mechanisms.
If misprediction rate , what does the branch term contribute to CPI?
Nothing — , so from branches. Perfect prediction makes control hazards free in this model; the whole cost lived in the mispredict probability.
If a load is followed by an instruction that does not use the loaded value, is there a load-use stall?
No — the load-use bubble is required only when the very next instruction depends on the loaded value in its EX stage. An independent following instruction proceeds with no stall.
Recall One-line self-test before you leave
Which single dependence is "real," and what fixes the other two? The only true dependence is ::: RAW; WAR and WAW are name dependences eliminated by register renaming.