Problem Set Solutions/Predication/Problems 7 - 9

This problem assumes that we are using a processor with a 15-stage pipeline and that the actual direction (T or NT) for a branch is determined during the 10th stage. The processor is executing a program in which 10% of executed instructions are conditional branches, and the only stalls occur when the direction of a conditional branch is mispredicted. The accuracies of different predictors for this program are as follows:

predication.jpg

Some branch instructions are much more predictable than others. If we know that 80% of all executed conditional branch instructions are easy-to-predict loop-back branches that are always predicted correctly by a dynamic predictor, what is the accuracy of each dynamic predictor on the remaining 20% of conditional branch instructions?

Solution:

Let us look at the 2-bit predictor as an example, and let us assume we execute 100 branches. The average accuracy across all branches is 90%, so 90 branches are predicted correctly and 10 are mispredicted. Of the 100 branches, 80 are easy to predict, so of the 90 correctly predicted branches only 10 are of the difficult-to-predict variety. Therefore, among the 20 difficult-to-predict branches, 10 are predicted correctly and 10 are predicted incorrectly, so the predictor accuracy on these branches is only 50%. Note that the total number of branches does not matter – if we used N instead of 100, N would cancel out and we would still have a 50% accuracy among difficult-to-predict branches.

For the global predictor, we have 5% of all branches mispredicted, and these mispredictions all happen among those 20% that are difficult to predict. This means that the accuracy of the predictor on difficult-to-predict branches is 75%.

For the tournament predictor, we have 2% of all branches mispredicted, and those mispredictions all happen among those 20% that are difficult-to-predict, so among difficult-to-predict branches we have 90% accuracy.