2 Bit Branch Predictor

Download here – [wpdm_package id=’1496′]

Implement the 2 bit branch predictor given below. Keep only one global history vector of two elements.

Implementation
I. Use 4 states , 11 – strongly taken, 10 – weakly taken, 00 – strongly not taken, 01 – weakly not taken
ii. Initially set prediction as weakly taken (10).
iii. Based on the left most bit decide weather the prediction will be taken or not taken.
iv. After the branch is complete update corresponding state and bits, which help in next prediction.
v. We change from taken to not taken or vice-versa only on 2 consecutive wrong-predictions.

Advantage
I. A few atypical branches will not influence the prediction.
ii. This allows the accuracy of the predictor to approach the taken branch frequency.
iii. 2 bit branch prediction performs almost as good as other values ie. 3 bit, 4 bit and so on.
iv. Perform better than the static branch predictor and random branch predictor.

To compile the program use following command –

1. make
2.  /predictor -1 -i traces/10queens -s

Sample results for different trace file –

1. traces/10queens – 64.6642
2. traces/fib20 – 59.7713