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$).$

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$).$

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?