Optimal 2-Bit Branch Predictors

This paper presents an efficient technique to analyze finite-state machines to determine an optimal one for branch prediction. It also presents results from using this technique to determine optimal 4-state branch predictors for applications in the SPEC89 benchmark suite running on the IBM RS/6000. The paper concludes that the simple 2-bit counter is the only machine that performs consistently well and close to the optimal over all applications. © 1995 IEEE