Question $1$: Branch Prediction $(15$ points$)$

a$)[5$ points$]$ Assume that we observed the following outcomes for the last $8$ instances of particular branch instruction: N$-$T$-$N$-$T$-$N$-$T$-$T$-$N $($where N indicates Not Taken, and T indicates Taken branch$).$ Show the content of Branch History Table $($BHT$)$ and predictions to be made if we use $1$bit branch predictor, and calculate the $\%$ of accuracy of the predictor. Assume that very first prediction is Not Taken $(N).$

$\backslash$table$[[$BHT$,$Prediction,Actual Result,True$/$False$],[0,$N$,$N$,$true$],[,,$T$,],[,,$N$,],[,,$T$,],[,,$N$,],[,,$T$,],[,,$T$,],[,,$N$,],[,,,]]$

b$)[5$ points$]$ Assume that we observed the following outcomes for the last $8$ instances of particular branch instruction: N$-$T$-$T$-$T$-$T$-$N$-$T$-$N $($where N indicates Not Taken, and T indicates Taken branch$).$ Show the content of Branch History Table $($BHT$)$ and predictions to be made if we use $2-$bit branch predictor, and calculate the $\%$ of accuracy of the predictor. Assume that we start with $01$ state that leads to have the first prediction be Not Taken $($N$).$

$\backslash$table$[[$BHT$,$Prediction,Actual Result,True$/$False$],[01,$N$,$N$,$true$],[,,$T$,],[,,$T$,],[,,$T$,],[,,$T$,],[,,$N$,],[,,$T$,],[,,$N$,],[,,,]]$

c$)[5$ points$]$ Assume a processor that employs a branch prediction whose prediction accuracy is $76\%.$ When a branch is predicted correctly, there is no performance penalty. However, when a branch is mispredicted, then there is $5$ cycles of penalty. Assume that we want to run a program whose $35\%$ of the instructions are branch instructions. Considering the ideal CPI on this processor is $1($when no hazard and stall occur$),$ what will be the CPI for this program on the given processor?