Consider the following C code:
int dp (int A[], int B[], int n) {
int i, sum = 0;
i = 0;
if (n == 0)
goto finished;
loop:
sum = A[i];
sum = sum * B[i];
i = i + 1;
if (i < n)
goto loop;
finished:
return sum;
}
For each line of C code, the compiler produces a machine instruction.
The code is not re-ordered by the compiler. Suppose that this function is
called 100 times, each time with a value of 3 for n. For each of
the following branch predictors, write the number of times a conditional
branch in the dp function would be predicted incorrectly (write a
single number for each predictor that is the total of all wrong predictions):
- Static "always not taken" policy.
- Static "backward taken/forward not taken" policy.
For dynamic predictors, assume there is no aliasing in branch prediction
tables and there is a single global history register that records the
outcomes of all conditional branches, and there are no other conditional
branches in the program outside the dp function. Initially all
counters and all bits of history are set to 0.
- A bimodal predictor with two-bit saturating counters.
- A two-level adaptive branch predictor with a history length of 2.