$3-$ Consider the following code segment within a loop body:

$if(d==0)$

$d=1$;

$if(d==1)$

Here is the equivalent MIPS code assuming $d$ is assigned to registers R$1.$

bnez R$1,$ L$1$ ; branch b$1(d0)$

addi $R,RO,$#$1$;$d=0,$ so $d=1$

L$1$: suiot R$3,$ R$1,$ #$1$

bnez $R3,L2$; branch b$2(d1)$

L$2$:

Assume that the following list of $8$ values of $d$ is to be processed:

$0,2,0,2,0,2,0,2$

$($a$)$ Suppose $2-$bit BPBs are used to predict the execution of the two branches in this loop. $2-$bit BPBs consists

of four states: strongly not taken $($sNT$),$ weakly not taken $($wNT$),$ strongly taken $($sT$),$ and weakly taken

$($wT$).$ Show the trace of predictions and the actual outcomes of branches b$1$ and b$2.$ Assume initial values

of the $2-$bit predictors are sNT$.$ What are the prediction accuracies for b$1$ and b$2?$ What is the overall

prediction accuracy?

$($b$)$ Suppose two$-$level $(1,2)$ branch prediction is used predict the execution of the two branches in this loop.

That is$,$ in addition to the $2-$bit predictor, a $1-$bit global register $($g$)$ is used. Assume the $2-$bit predictors are

initialized to SNT and $g$ is initialized to NT$.$ Show the trace of predictions and the actual outcomes of

branches $b1$ and $b2.$ What are the prediction accuracies for $b1$ and $b2?$ What is the overall prediction

accuracy?

$($c$)$ Suppose a two$-$level $(2,2)$ branch prediction is used predict the execution of the two branches in this loop.

That is$,$ in addition to the $2-$bit predictor, a $2-$bit global register $($g$)$ is used. Assume the $2-$bit predictors are

all initialized to SNT and $g$ is initialized to NT$,$ NT$,$ with the LSB representing the most recent branch

outcome. Therefore, initial predictions, $g,$ and their meaning are given below:

Show the trace of predictions and updated $g$ values for branches $b1$ and $b2$ in the table shown below. What

are the prediction accuracies for $b1$ and $b2?$ What is the overall prediction accuracy?