Grant Wallace
Describes a simple strategy for keeping track of correlation information among branches. Namely, retain correlation information about the last m branches using an m bit shift register. This will record 2^m different paths to the current branch. The value of this shift register along with some branch address bits can then index a table of N-bit counter predictors.
Makes a good case that a large degree of correlation exists between branches in a program (at least within the integer SPEC benchmark). Their results show an improved branch prediction accuracy when employing correlation information even in the degenerate case of disregarding address bits (i.e. correlation data is maintained on a global scale regardless of the specific branch).
Gives a prediction accuracy of almost 96% using a minimal implementation (1 added shift register).
I was surprised that the degenerate correlation case out-performed the 2-bit counter. My only explanation would be; they both contain the same amount of information (1KB), and correlation patterns tend to be very specific to a particular branch (i.e. if we had a different branch history table for each branch as in [2] it would be sparsely populated). Leading to the conclusion that only a few paths consistently lead to a branch.
Along a similar line, I was surprised that none of the SPEC programs showed a loss of prediction accuracy when using correlated branch prediction as compared to 2-bit counter prediction (with same table size). It seems that some programs would have little correlation, and when this is true two effects would counter the accuracy:
1. It would take longer for the path's N-bit counter to reach an accurate history.Paper [1] and [2] study different types of correlation. [1] looks at correlation among the last m branches whereas [2] correlates the last m occurrences of a particular branch. It’s interesting that [2] discusses the variations GAg, PAg, PAp but not GAp which [1] does cover. Since [1] and [2] both look at GAg we can see their results are similar, they both achieve just under 96% accuracy ([2] with m=16 and [1] with m=15).
We can see from [1] and [2] that both types of correlation (inter and intra branch) yield about the same program wide accuracy (96-97%). This leads to [3] combining the two correlation methods yielding an ideal overall correlation of about 98%.
I’m wondering if there are some branch patterns ("paths") that consistently occur more frequently across all branches. A particular language or compiler could generate certain paths with higher probability. If this were the case I would think the XOR method introduced in [3] for combining branch pattern and address bits would give better accuracy because of reduced conflict misses. The results from [3] show no consistent pattern in this area.
[1] "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation", Shien-Tai Pan, Kimming So, Joseph T. Rahmeh, Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems.
[2] "Alternative Implementations of Two-Level Adaptive Branch Prediction", Tse-Yu Yeh and Yale N. Patt, Proceedings of the 19th International Symposium on Computer Architecture.
[3] "Alternative Implementations of Hybrid Branch Predictors", Po-Yung Chang, Eric Hao, Yale N. Patt, Proceedings of the 28th International Symposium on Computer Architecture.