Predict branches, then verify the guess

Prerequisites: Pipelines, conditional branches, and architectural state.

Learning objectives

• Simulate a two-bit saturating branch predictor.
• Calculate a simple misprediction cost.
• Distinguish architectural rollback from microarchitectural effects.

A prediction keeps the front end moving

A conditional branch chooses a next instruction address based on a condition. Waiting for every branch to resolve can leave a long pipeline idle. Prediction supplies a provisional direction and target so fetching can continue. The machine later checks the guess against the actual outcome. Prediction is useful only because recovery preserves the program’s required architectural result.

A two-bit saturating counter is a small direction predictor. Let states zero and one predict not taken, while two and three predict taken. A taken outcome increments the counter up to three; a not-taken outcome decrements it down to zero. The extra bit supplies hysteresis: one unusual outcome need not reverse a strong prediction immediately.

Starting in state three, process outcomes taken, taken, not taken, taken, not taken, not taken. The states before the six branches are 3, 3, 3, 2, 3, and 2. Every prediction is taken. The third, fifth, and sixth outcomes are mispredicted; the final state is one. This example shows why a small predictor can perform poorly on a changing pattern even though it handles a mostly taken loop well.

Convert accuracy into an explicit model

Suppose branches comprise 20% of executed instructions, 10% of branches are mispredicted, and each misprediction adds twelve cycles that do not overlap other costs. The extra cycles per instruction are 0.20 × 0.10 × 12 = 0.24. With baseline CPI 1, the model predicts CPI 1.24. Improving prediction to a 5% miss rate reduces the estimate to 1.12. It does not cut total execution time in half, because only the misprediction contribution is halved.

Real machines have varying recovery costs, overlapping misses, target prediction, and history-based predictors. A branch miss count alone cannot determine elapsed time without a model of those interactions.

Rollback has a boundary

Speculative instructions may execute before the branch is resolved. Their architectural updates must be held or reversible until they are known to belong to the correct path. A misprediction discards younger incorrect-path work and restarts fetching at the correct address.

However, executing that work can change caches and other microarchitectural structures. Architectural rollback does not imply that every timing footprint disappears. This distinction matters for security reasoning as well as performance measurement. Branch prediction is not a permission to violate the instruction-set contract. It is an implementation technique whose correctness requires precise recovery and whose broader effects require separate analysis.

Primary reading

• Pipelining the Beta (MIT OpenCourseWare, Computation Structures).
• Hardware Features and Behavior Related to Speculative Execution (Intel).

Practice problem

Simulate the two-bit predictor from state zero on outcomes taken, taken, taken, not taken. Give the predictions, states after each outcome, and miss count. Then estimate extra CPI when branches are 15% of instructions, their miss rate is 8%, and recovery costs ten non-overlapping cycles.

Worked solution

Starting at state zero, the first prediction is not taken and the taken outcome increments the state to one. The second prediction is again not taken and the state rises to two. The third prediction is taken and correct, taking the state to three. The fourth prediction is taken but the actual outcome is not taken, reducing the state to two. Predictions are therefore not taken, not taken, taken, taken, with three misses. The extra CPI estimate is 0.15×0.08×10=0.12 cycles per instruction. This number is an additive estimate only under the stated non-overlap assumption. It is not a universal penalty for every implementation, and it must be combined with the rest of the execution-time model.

Check your understanding

What happens after one not-taken result in strongly-taken state three?

• The state becomes zero.
• The state becomes two and still predicts taken.
• The predictor stops updating.
• All future branches become not taken.

Explanation

A saturating counter moves one step, so a single contrary outcome does not reverse a strong prediction.

Halving a branch miss rate does what to total runtime in the simple model?

• Always halves it.
• Halves only the modeled misprediction contribution.
• Doubles instruction count.
• Eliminates the need for recovery.

Explanation

Baseline work remains, and other costs may remain as well.

Primary reading

• Pipelining the Beta: MIT OpenCourseWare, Computation Structures
• Hardware Features and Behavior Related to Speculative Execution: Intel

Open the study and save your work →