5.2.8 · D5Processor Datapath & Pipelining
Question bank — Control hazards and pipeline flushes
Before the traps, one shared vocabulary anchor so nothing is used unearned. The figure below is the map — keep it in view while you answer:
The second figure shows exactly what "flush two instructions" looks like as a timing chart — refer back to it whenever a trap mentions fetch, resolve, or bubble:
True or false — justify
The branch instruction itself gets flushed when it is taken.
False. The branch is correct — it must finish and update the PC. We flush only the wrong-path instructions fetched after it (at PC+4, PC+8).
A flushed instruction is erased from memory (RAM).
False. Flushing only zeros the control signals of the copy sitting in a pipeline register; the bytes in memory are untouched and will execute normally next time control reaches them.
A branch that is not taken on a predict-not-taken machine costs zero penalty.
True. The speculatively fetched PC+4 instructions were the correct ones all along, so nothing needs flushing — the guess was right.
Branch prediction eliminates all control-hazard penalties.
False. Prediction only reduces the penalty by being right most of the time; every misprediction still triggers a full flush of the wrong-path instructions.
Resolving a branch one stage earlier (ID instead of EX) always halves the penalty.
Roughly true here, but state it as a subtraction, not a halving. Penalty = (resolve stage) − (fetch stage); moving from EX to ID drops it from 2 to 1 — that happens to halve 2, but the rule is "one fewer flushed instruction per stage earlier."
A 2-bit saturating counter mispredicts fewer times per loop than a 1-bit counter.
True. The 1-bit predictor flips on the single loop-exit miss and is then wrong on the next loop's entry (2 misses); the 2-bit counter needs two consecutive misses to flip, so it stays "Taken" and only misses on exit (1 miss).
Control hazards and data hazards are the same underlying problem.
False. A data hazard is about which value an operand should hold (dependency); a control hazard is about which instruction to fetch next. See 5.2.05-Data-hazards-and-forwarding for the contrast.
Predict-taken is strictly better than predict-not-taken because most branches are taken.
False. Predict-taken needs the target address computed early (an adder feeding the PC in ID); without that hardware you cannot fetch the target, so "most branches taken" alone doesn't make it free.
If a branch is not taken, no instruction ever needs flushing on any machine.
False in general. On a predict-taken machine a not-taken branch means the speculatively fetched target instructions are wrong and must be flushed.
Bubbles slow the clock frequency of the pipeline.
False. Bubbles don't change timing per stage; they waste cycles (throughput), not clock period. The pipeline still ticks at the same rate.
Spot the error
"We flush the branch so the wrong path never runs." — What's wrong?
We don't flush the branch; we flush the wrong-path successors. The branch must complete to set the correct PC. Flushing the branch would lose the very instruction that computes where to go.
"With predict-not-taken, penalty = 2 cycles × , so a machine with 50% taken branches always loses exactly 1 cycle per branch." — spot the slip.
"Exactly 1" over-claims — it's the average (), not a per-branch value. Any individual not-taken branch costs 0 and any taken one costs 2; the 1 is a statistical mean.
"A 1-bit predictor in a 100-iteration loop mispredicts once (at exit)." — find the error.
It mispredicts twice: once at exit (predicts taken, loop ends) and once at the next loop's first iteration (it now predicts not-taken but the loop is entered again).
"To flush, just delete the instruction from the ID/EX register." — why is 'delete' the wrong verb?
You cannot remove a slot mid-flight without desynchronizing the synchronized stages. You neutralize it into a bubble (RegWrite=0, MemWrite=0), so it still advances stage-by-stage but changes nothing.
"BHT index = PC mod , so we use all PC bits including the low 2." — what's off?
Instructions are word-aligned, so the low 2 bits are always 0 and carry no information. The index uses , dropping those constant bits so no two useful addresses collide on a wasted entry.
"A 95%-accurate predictor makes control hazards free." — correct it.
The remaining 5% still flush. On a deep pipeline even a small miss rate costs many cycles, because each miss flushes several instructions.
Why questions
Why must a flushed instruction become a bubble rather than simply vanish?
Because pipeline stages march in lockstep; a missing slot would desynchronize downstream logic. A bubble keeps the timing intact while doing nothing to architectural state.
Why does resolving the branch in EX cost 2 flushes but in ID cost only 1?
Penalty equals how many wrong-path instructions were fetched before resolution. Between IF and EX two instructions entered; between IF and ID only one did.
Why does a taken branch cost penalty while a not-taken one (under predict-not-taken) costs nothing?
Predict-not-taken speculatively fetches PC+4. If the branch is not taken those fetches were correct — no flush; if taken they were wrong — flush.
Why do processors predict at all instead of just stalling until the branch resolves?
Stalling wastes the penalty cycles on every branch unconditionally; predicting wastes them only on mispredictions, so a good predictor is almost always cheaper. See 5.2.09-Branch-prediction-techniques.
Why does a 2-bit counter need two consecutive misses to change its prediction?
It has four states with hysteresis (Strong/Weak Taken, Weak/Strong Not-Taken); one miss only nudges Strong→Weak without crossing the taken/not-taken boundary, so a rare anomaly (like a loop exit) doesn't corrupt the dominant trend.
Why is a branch called a control hazard rather than a data hazard?
It endangers the control flow — the choice of which instruction is next — not the correctness of an operand's value.
Why can speculatively executed wrong-path instructions be discarded safely?
Because as bubbles they never wrote a register or memory; nothing they touched became architectural state, so removing them leaves the machine exactly as if they never ran. This is the foundation for 5.2.11-Speculative-execution.
Edge cases
A branch where the condition is always true (unconditional jump). Does predict-not-taken ever help?
No — it will mispredict every single time (always taken), paying full penalty on each. Such branches are exactly why predict-taken or a BTB target-cache exists.
The very first time a branch is seen by a BHT: what prediction is used?
Whatever the entry's initial/aliased state is — the predictor has no history, so the "prediction" is essentially the reset default (often set to Strongly/Weakly Taken to favor loops).
Two different branches hash to the same BHT index (aliasing). What can go wrong?
They share one counter, so one branch's behaviour corrupts the other's prediction, raising misprediction rate. This "destructive aliasing" is why index bits and tagging matter.
A back-to-back pair of branches, the second sitting in the wrong-path slot of the first. What happens on flush?
The second branch is flushed as a bubble too — it never resolves and never predicts, because it should not have been in the pipeline at all.
A branch that resolves not taken on a predict-taken machine, but the target adder was busy. Any subtlety?
The penalty is the flush of the mistakenly fetched target instructions; the "not taken" path (PC+4) must now be refetched, so the 1-cycle penalty here comes from discarding target fetches, not condition delay.
Zero-iteration loop (condition false on entry): how many mispredictions from a counter initialized to Strongly-Taken?
One — it predicts taken but the loop is skipped immediately, so the single entry mispredicts and no "99 correct" cushion exists.
Recall One-line summary to lock in
Flush the followers, not the branch; bubbles waste cycles not memory; prediction shrinks — never removes — the penalty.
Justify why the penalty formula never depends on whether the branch is forward or backward.
The penalty counts pipeline stages between fetch and resolve, which is fixed by hardware structure; direction only affects how often a static predictor is right, not the per-miss cost.