$4\mathrm{.}29$ This exercise examines the accuracy of various branch predictors for the following repeating pattern $($e$.$g$.,$ in a loop$)$ of branch outcomes: T$,$ NT$,$ T$,$ T$,$ NT$.$

$4\mathrm{.}29\mathrm{.}1[5]$$$4\mathrm{.}9>$ What is the accuracy of always$-$taken and always$-$not$-$taken predictors for this sequence of branch outcomes?

$4\mathrm{.}29\mathrm{.}2[5]$$$4\mathrm{.}9>$ What is the accuracy of the $2-$bit predictor for the first four branches in this pattern, assuming that the predictor starts off in the bottom left state from Figure $4\mathrm{.}78($predict not taken$)?$

$4\mathrm{.}29\mathrm{.}3[10]$$$4\mathrm{.}9>$ What is the accuracy of the $2-$bit predictor if this pattern is repeated forever?

$4\mathrm{.}29\mathrm{.}4[30]$$$4\mathrm{.}9>$ Design a predictor that would achieve a perfect accuracy if this pattern is repeated forever. You predictor should be a sequential circuit with one output that provides a prediction $(1$ for taken, $0$ for not taken$)$ and no inputs other than the clock and the control signal that indicates that the instruction is a conditional branch.

FIGURE $4\mathrm{.}78$ The states in a $2-$bit prediction scheme. By using $2$ bits rather than $1,$ a branch that strongly favors taken or not taken$-$as many branches do$-$will be mispredicted only once. The $2$ bits are used to encode the four states in the system. The $2-$bit scheme is a general instance of a counter$-$based predictor, which is incremented when the prediction is accurate and decremented otherwise, and uses the mid$-$point of its range as the division between taken and not taken.