A comparison of dynamic branch predictors that use two levels of branch history

TLDR

Speculative execution has driven the need for improved branch prediction beyond what was previously available. The paper demonstrates that the basic two‑level adaptive branch predictor has nine distinct variations. The authors compare the nine variations by varying branch history lengths and pattern history table configurations to assess the impact of history information. The evaluation shows differences in cost‑effectiveness among the nine variations.

Abstract

Recent attention to speculative execution as a mechanism for increasing performance of single instruction streams has demanded substantially better branch prediction than what has been previously available. We [1,2] and Pan, So, and Rahmen [4] have both proposed variations of the same aggressive dynamic branch predictor for handling those needs. We call the basic model Two-Level Adaptive Branch Prediction; Pan, So, and Rahmeh call it Correlation Branch Prediction. In this paper, we adopt the terminology of [2] and show that there are really nine variations of the same basic model. We compare the nine variations with respect to the amount of history information kept. We study the effects of different branch history lengths and pattern history table configurations. Finally, we evaluate the cost effectiveness of the nine variations.