Bimodal prediction.

Branch prediction accuracy with a bimodal predictor

This medium-difficulty computer architecture question tests your understanding of how bimodal branch predictors work in modern CPUs. Specifically, it asks you to trace through the state transitions of a 2-bit saturating counter as a real conditional branch executes, and then compute the overall prediction accuracy.

To solve this, you need to understand the four states of a 2-bit counter (Strongly Taken, Weakly Taken, Weakly Not Taken, Strongly Not Taken), how branch outcomes drive state transitions, and when the predictor makes correct vs. incorrect predictions. The question rewards careful hand-simulation and attention to initial conditions and the actual branch pattern in the code.

• 2-bit saturating counter states and transitions
• Branch history and dynamic prediction
• Prediction accuracy as a ratio of correct to total predictions
• Role of the Branch Target Buffer (BTB)