Branch Prediction as a Reinforcement Learning Problem: Why, How and Case
  Studies
  Recent years have seen stagnating improvements to branch predictor (BP)
efficacy and a dearth of fresh ideas in branch predictor design, calling for
fresh thinking in this area. This paper argues that looking at BP from the
viewpoint of Reinforcement Learning (RL) facilitates systematic reasoning
about, and exploration of, BP designs. We describe how to apply the RL
formulation to branch predictors, show that existing predictors can be
succinctly expressed in this formulation, and study two RL-based variants of
conventional BPs.
