Bimodal prediction II

Bimodal branch-predictor correctness in a loop

This hard computer-architecture question tests your understanding of how modern CPUs predict conditional branches and update their prediction state. It is representative of the kind of low-level reasoning Intel and other processor-design firms expect from candidates who work on microarchitecture and performance modelling.

The problem combines two key CPU components: a bimodal predictor that learns branch direction from history, and a Branch Target Buffer (BTB) that caches the target address of previously-seen branches. You must trace through the state transitions of the predictor across loop iterations, accounting for how the predictor's confidence changes as it observes the actual branch outcomes. The goal is to count the total number of correct predictions over all iterations, not just the final steady state.

• 2-bit saturating counters and predictor state machines
• Weak vs. strong prediction states
• BTB compulsory misses and warm-up behaviour
• Loop-carried branch prediction patterns