Question bank — Branch prediction (static and dynamic)

False. It needs no state, but it is wrong every time a branch is actually taken (e.g. loops), so it's simple, not accurate.

False. On a short loop (3 iterations) the 2-bit counter can score worse on the first pass because its hysteresis makes it slow to trust "taken"; it wins only over many repetitions.

True. Static uses a rule fixed at design/compile time; dynamic updates a hardware table from the branch's actual runtime outcomes.

True. A loop's back-edge points to a lower address (target < PC) and is taken almost every iteration, so "backward ⇒ taken" is correct 90%+ of the time.

True. On a correct guess the speculatively fetched instructions were the right ones, so the pipeline never stalls or flushes — that's the whole point of predicting.

False. It mispredicts twice per loop entry-to-exit: once on the first iteration (cold start) and once on the exit — because a single not-taken flips its bit, so re-entry starts wrong again.

True. In $\text{CPI}=1+P_{\text{branch}}\times P_{\text{mispredict}}\times \text{Penalty}$, a bigger Penalty multiplies every mistake, so the same mispredict rate costs more cycles.

True. A branch can be individually unpredictable but correlated with recent branches; the global history register captures that pattern a per-address counter cannot see.

True. There's no exit event to flip the bit back, so after the first (cold) miss the bit stays at 1 and stays correct forever.

Wrong — a miss is the expensive case: the speculatively fetched instructions are flushed and the pipeline restarts, costing the full ~5–10 cycle penalty. Only correct guesses are free.

Wrong — the rule is predict Taken only when the counter is $\ge 10$. 01 is still in the Not-Taken half, so it predicts Not-Taken.

Wrong — the bottom 2 bits are dropped because instructions are 4-byte aligned and would always be 00; we use $\text{PC}[n:2]\mathrm{mod}{2}^k$, wasting no index bits.

Wrong — static schemes have no learning; BTFNT's ~84% is a fixed ceiling set by the target-address rule, unchanged run to run.

Wrong — it oscillates: the exit flips the bit to Not-Taken, so the next entry mispredicts again. It reaches ~98%, and it re-loses the entry cycle every re-entry, unlike a 2-bit counter which holds "Strongly Taken."

Wrong — they also need the global history register (recent outcomes of other branches); using only the address makes it a plain bimodal predictor.

Wrong — forward branches (error checks, early returns) are usually not taken, so Predict-Not-Taken fits them; Predict-Taken suits backward loop branches.

So a single anomalous outcome (like a loop's one exit) can't flip the prediction — it takes two consecutive misses to switch, letting the predictor stay right on the dominant behaviour.

The loop is too short to amortise its two guaranteed misses (cold start + exit) over few iterations — 2 wrong out of 4 branch events is exactly 50%.

Because the branch outcome isn't known for ~10–20 cycles, and stalling starves the pipeline — an educated guess keeps it full and only occasionally wastes work, which on average is far faster. This underpins Speculative Execution and Instruction-Level Parallelism (ILP).

More stages means more in-flight instructions to flush on a miss, so the misprediction penalty grows — the cost of a bad guess scales with pipeline depth.

The compiler can arrange code and emit branch hints (likely/unlikely) using knowledge of loop structure and profiling, feeding the fixed hardware rule. See Compiler Optimizations.

The inner branch may only execute (or resolve a certain way) because the outer branch went a specific way; the global history encodes "outer was taken," letting the inner prediction condition on it.

A wrong guess fetches instructions and data from the wrong path, polluting the cache with lines the program never uses and possibly evicting useful ones — connecting to Cache Performance.

They issue several instructions per cycle, so a flush wastes multiple instructions' worth of work per cycle across the whole pipeline width — the penalty is multiplied by the issue width.

The BHT entry holds its initial state (often 00 / Not-Taken), so the first prediction is essentially a blind guess and is often wrong regardless of how good the predictor is.

Taken — the rule is $\ge 10\Rightarrow$ Taken, so 10 predicts Taken but a single not-taken drops it to 01 and flips the prediction.

They share one counter and interfere ("destructive aliasing"), so one branch's outcomes corrupt the other's prediction — accuracy drops even though each branch alone is predictable.

About 50% — no history or rule can beat a fair coin, so this is the theoretical worst case where prediction adds cost (flushes) with no benefit.

Poorly — it never saturates, hovering around the weak states and mispredicting frequently, because the pattern flips faster than the hysteresis can settle. This is exactly the case correlating predictors are built to catch.

It's fixed by the target-address rule (~84% typical), so even perfectly loop-heavy code can't push it higher — because it can't learn per-branch behaviour.

The exit is genuinely not-taken while the counter says Strongly Taken, so that one branch resolves against the prediction — but it only drops the counter to 10, so re-entry is still correct. That single unavoidable exit miss is the "one per loop" cost.