Question

You are evaluating three branch prediction strategies: (1) predict always taken, (2) predict always not taken and (3) use the 2-bit branch predictor. Experimentally, your measurements show that conditional branches account for 20% of all instructions and 70% of all branches are taken. The 2-bit predictor has an accuracy of 70%. Assuming that the penalty of a mis-prediction is 4 cycles and 0 cycles for a correct prediction, compute the average stall cycles per instruction of the three strategies.

Answer 1

The penalty of the misprediction = 4 cycles

The conditional branches of instructions = 20%

The Branch taken is = 70%

2-bit predictor accuracy is = 70%

1). The predict always taken

The stall only for the conditional instruction for which branch is not taken.

Stalls =
`$0.2 * (1-0.7) * 4$`

`$= 0.2 * 0.3 * 4$`

= 0.24 cycles

2). The predict not always taken

The stall only for the conditional instruction for which branch is taken.

Stalls
`$= 0.2 * 0.7 * 4$`

= 0.56 cycles

3). The 2- bit predictor

The stalls
`$= 0.2 * (0.7 * 0.3* 4+0.3 * 0.3* 4)$`

= 0.2 x 1.2

= 0.24 cycles