Figure 9: Combined branch prediction techniques
Next: Experimental Results
Up: No Title
Previous: Aliasing Problem
Different branch prediction schemes have different advantages. For example xoring schemes has very good prediction accuracy but has more aliasing problem, however branch address scheme suffers less aliasing problem but performance of it is not as good as xoring schemes. The natural question is whether the different advantages can be combined in a new branch prediction method with better prediction accuracy. One such method proposed by McFarling [] combines branch address scheme and global history schemes. In his approach, it uses three counter tables two of them for branch address and global history predictors and the other table is used to select best predictor for respective counter. Each counter (2-bit saturated up-down) of this new table which is called decision table, keeps track of which predictor is more accurate for branches (Fig.9).
Figure 9: Combined branch prediction techniques
A counter in decision table indicated which prediction scheme would be used for more accurate prediction. For each prediction, this new counter content show which predictor has to be used for that branch. After prediction, if both predictor gives correct results or in-correct results, the new table is not updated. However, if first scheme gives correct results but second one gives in-correct result, then it is incremented otherwise it is decremented. Here, the same question arises, how we index this new table. In McFarling approach, the branch address is used to index to the new table. Again from results of first part of project, xoring schemes uses more information then using pc, therefore the xoring scheme can be used for this new table.
The idea of combining two prediction schemes is that use the which one gives more correct results. The question is how we measure the correctness of the predictors. We can keep the number of correct results for each counter in two PHTs and decision can be made by looking the rate of correct results. However, this idea can give bad results for some condition. For example, a counter might predict the branches correctly at the beginning of the execution and increase the number of it's correct prediction. After some amount of execution, it might begin predicting incorrectly, but its correntness rate remains still high and this high correct number cause to be selected for prediction. Therefore, to keep the number of correct results from beginning of the execution can cause wrong decision. We need more resent information to make a decision about which counter would be used. Instead of using global approach to correctness value, we can use local approach. For example, correctness of last k prediction can be used. I call this predcition techniques as correctness history scheme. Ecah counter has a correctness rate of lask k prediction. While making prediction, counter which has higher correctness history is selected and after the results of branch is known, the content of counters and correctness history rates are updated.
