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

Solution :

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 \times (1-0.7) \times 4$

             $= 0.2 \times 0.3 \times 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 \times 0.7 \times 4$

             = 0.56 cycles

3). The 2- bit predictor

   The stalls $= 0.2 \times (0.7 \times 0.3\times 4+0.3 \times 0.3\times 4)$

                    = 0.2 x 1.2

                    = 0.24 cycles