Branch Prediction with Bayesian Networks

Abstract. This paper studies the architectural problem of branch prediction. We analyse the popular technique of two-level adaptive prediction, relating it to the state-of-the-art Machine Learning technique of Bayesian Networks (BNs). We show that a two-level predictor is an approximation to the BN formalism. This link allows us to explore the wider family of BN predictors. We investigate how to adapt BN techniques to operate within realistic hardware constraints, using the same primitive components that are present in existing branch predictors. We systematically study how performance is affected by these simplification. We aim to use these ideas to reduce the storage overhead of BN predictors without losing significant prediction accuracy. The key motivating factor is that storage required in two-level predictors grows exponentially with branch history length, whereas BNs provide a framework to reduce this overhead.