Revisiting branch prediction: Can we use broader contextual information to find better patterns?

Branch prediction is essential for computer performance as it allows processors to run ahead and do useful work while waiting for slower instructions. With today’s computers having hundreds of in-flight instructions, the need for accurate branch prediction is acute.

However, the state-of-the-art is to take a history-based predictor from 2006 and “add-on” predictors for specialized contexts (e.g., loops or statistically biased branches) with all predictors competing to see which can make the most accurate prediction.

This project will reverse that approach: instead of combining the results of predictors for different contexts, we will combine the contexts to enable a better predictor.

The reason to believe this will work better is that the contexts are not independent, and by combining information from them, we believe we will be able to find more meaningful patterns to enable better predictions.We will first look at which contexts contribute useful information, including more subtle contexts as we do not need to directly make predictions from them, then look at how to represent this information in a noise-resistant manner, and then how to combine multiple contexts.

After that, we will look at the tradeoffs required for a practical implementation, including what should be learned online and offline.

This will provide fundamental insights into what information we should be using for branch prediction, how to combine it, and how to represent it.