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.

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.24 cycles

2). The predict not always taken

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

    Stalls  

             = 0.56 cycles

3). The 2- bit predictor

   The stalls

                    = 0.2 x 1.2

                    = 0.24 cycles

1. entrepreneur.com

2. wikipedia

we need a link or picture : )