Problem Set Solutions/Predication/Problem 10 - 14

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

For each of these branch predictors, what speedup would be achieved if we apply a program transformation that replaces a conditional branch instruction with an ADD instruction, but can only be applied to half of the branch instructions executed in this program? What is the relationship between speedup from this transformation and the original accuracy of the predictor? Note: Assume that correctly and incorrectly predicted instructions have the same chance of being replaced during this program transformation.

Solution:

This removes half of the mispredictions, and thus half the CPI penalty. We have:

Always-taken: Old CPI: 1.495, New CPI: 1.2475, Speedup: 1.198

Always-not-taken: Old CPI: 1.405, New CPI: 1.2025, Speedup: 1.168

2-bit: Old CPI: 1.090, New CPI: 1.045, Speedup: 1.043

Global: Old CPI: 1.045, New CPI: 1.0225, Speedup: 1.022

Tournament: Old CPI: 1.018, New CPI: 1.009, Speedup: 1.009

The less accurate predictors get more speedup from this transformation – the more accurate the predictor, the fewer mispredictions there are to benefit from this transformation.