Analysis of a tag-based branch predictor

The method most often used for inventing new branch predictors is to start from a known predictor and try to improve it. However, this method gives little insight in the frequent case where we fail to improve the predictor. This study proposes a new approach, which we think provides a better understanding. We start from a model of ideal predictor, and introduce successive degradations, until we obtain a predictor that can be implemented in hardware. On each degradation, it is possible to quantify the loss, analyze the reasons for it, and sometimes propose remedies. This paper is an illustration of this method on the family of tag-based predictors derived from PPM