Workload Characterization for Branch Prediction
Abstract
Branch prediction is a method adopted in modern processors that tries to infer the outcome of a conditional branch instruction and prepare for the most probable result. An accurate predictor reduces the number of instructions executed on the incorrect path in modern superscalar out-of-order pipelined processors, which results in an overall improvement of performance and energy consumption. Thus, branch prediction has become a vital component in all modern CPU designs. Predicting a branch’s direction is a pattern recognition problem where we learn mappings from a context to the branch outcome. The branch prediction model is typically trained against the context, and then the outcome is reproduced when the same context is presented again in the future.
We present a workload characterization methodology for the branch prediction. We have proposed two new trace-level branch prediction accuracy identifiers - branch working set size and branch predictability. These parameters are highly correlated with branch misprediction rates of two state-of-art branch prediction techniques - Andre Seznec’s TAgged GEometric length predictor (TAGE) [1, 2] and Daniel Jiménez’s multiperspective perceptron branch predictor [3, 4]. We have defined the branch working set as the most frequently occurring branch context present in a trace and analyzed its size and predictability to find strong correlations with the modern branch predictor’s accuracy. We present this analysis in multiple configurations with varying lengths of branch histories and branch working set threshold to find a sweet spot for the workload characterization.
We have characterized 2451 workload traces in 7 branch working set size based and 9 predictability-based categories after analyzing their branch behavior. We present insights on the source of prediction accuracies and favored workload categories for modern branch predictors. We show that the winner of the Championship Branch Prediction competition [CBP5] [2] outperforms the runner-up design [4] in almost all the workload categories except a few having a smaller working set or low inherent predictability, where the runner up design seems to be a better choice.
Citation
Vikas (2020). Workload Characterization for Branch Prediction. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /191903.