The Role of Adaptivity in Two-level Adaptive Branch Prediction

Stuart Sechrest, Chih-Chieh Lee, Trevor N. Mudge


Seeking higher branch prediction accuracy, architects are making use of the extended history of individual branches. One approach is to divide the branch prediction task into two levels, the first records the results of previous branches, the second makes predictions based upon previous instances in which particular patterns arose. Current two-level schemes use simple state machines in this second level to provide adaptive predictions. We demonstrate that the predictions in this second level can be made statically with performance that is competitive with adaptive schemes. Further we provide a simple algorithm for devising these predictions. This fixed scheme makes errors in a way that matches the errors made by adaptive schemes, providing insight into the workings of adaptive two-level schemes.


dynamic branch prediction, two-level branch prediction

Talk Overheads (239191 bytes)