We have a program code consisting of five conditional branches. The program code will be executed an arbitrarily large number of times. Below are the outcomes of each branch for one execution of the program code.
Branch 1: T-T-T
Branch 2: N-N-T-N
Branch 3: T-N-T-N-N-T
Branch 4: T-T-N-T-T-T-N
The 2-bit dynamic branch prediction algorithm is used with the following states.
ST - Strongly likely to be taken
LT - Likely to be taken
LNT - Likely not to be taken
SNT - Strongly likely not to be taken
Assume that each branch has its own prediction buffer and each buffer is initialized to the branch state LT.
What is the overall accuracy of the prediction scheme?