A Comprehensive Study of Dynamic Global History Branch Prediction

This report recapitulates and analyzes the most significant results on global history branch prediction during the past decade. Most global history branch predictors (GHBP) are implemented using one or several two-bit counter tables. The global branch history, i.e., the outcomes of the most recently encountered branches, is combined with the branch address to index those tables. Previous studies addressed several questions : Why use two-bit counters ? What limit for the prediction accuracy of a GHBP ? Which hardware budget is needed to come close to this limit ? How to better utilize a limited hardware budget ? This study revisits these questions- . First we show that a two-bit counter is close to an optimal predictor, while allowing simple hardware implementations. Then we use a PPM algorithm as a vehicle to understand practical prediction accuracy limits for most GHBPs. Using PPM, we show that a long global history can potentially improve the prediction accuracy, even though a part of this potential is offset by the impact of cold-start misses. We observe that programs with branches that are difficult to predict are likely to have their working set increase very fast with the global history length. These programs experience a lot of cold-start misses and, also, require huge branch prediction tables to come close to PPM limit. Then we study «dealiased» GHBPs, which are approximations of PPM, given a limited hardware budget. We isolate the few dealiasing primitives constituting the «active principles» of dealiased GHBPs previously published. We study these primitives and show that some of them are actually similar. We show that simple combinations of these primitives are able to exploit long global histories for realistic hardware budgets. Finally, we conduct an experimental study on the perceptron branch predictor, which, unlike previously published GHBPs, does not derive from BPPM. Although the perceptron alone is generally not as accurate as a well-tuned «classical» dealiased GHBP, it sometimes succeeds where classical GHBPs fail. This suggests that, by using the perceptron in a hybrid predictor, it might be possible to overcome PPM limitations