In computer architecture, branch predictors are a digital circuit component which try to guess the outcome of a branch before it is definitively known. A branch instruction has 2 possible outcomes: taken or not-taken. However, to know the definite outcome of the branch we need some clock cycles. A new instruction can't be fetched into the pipeline during this time as the address of the next instruction is dictated by the branch outcome. Branch predcictors predict the direction of the branch, thus allowing us to fetch instructions without any delays. However, we need to stall the pipeline in case the branch prediction is wrong. Thus an accurate branch predictor is a great boost for performance.
I have implemented a branch predictor for the Chamspsim Simulator Framework. The branch predictor has been written in the C++ language.
Ideas for the branch predictor have majorly been taken from the following two research papers:
- Install Champsim on your PC. Refer to the instructions in the Champsim repository.
- Add the
oh_snap.bpredfile to thebranchfolder in the Champsim directory. - Simulate the branch predictor according to the instructions provided in the Champsim repository
The predictor is a hybrid of the SNIP and the gshare low-level preedictor. As mentioned in the Combining Branch Predictors, this hugely boosts performance
Instead of using a single 2-D weight array, I have used multiple weight arrays having different rows based on the weight position. This has been done in accordance with the idea that recent weights have a larger correlation to the branch outcome. Different weight sizes have also been chosen for the different rows.
A weight scaling factor which is modified dynamically based on branch outcome is multiplied with the weights before making the prediction
The threshold parameter which dictates the required confidence level in predcition to avoid training, is also modified dynamically based on ideas presented in Analysis of the O-GEometric history length branch predictor research paper.
Minimal comments are present in the oh_snap.cpp file. For more explanation refer to this Resources folder. It contains powerpoint presentations and some other resources which cover every aspect of the code and the underlying ideas in detail.