small branch prediction exercise (not homework)

Question

This is NOT homework. I was reading this site which, IMO, has pretty good introduction into branch prediction, and decided to try solving a problem following the lecture:

consider the following code [no branch delay slots]:
  add  $2, $0, $0
  addi $11, $0, 5
  addi $12, $0, 3
outer:
  addi $2, $2, 1
  add  $1, $0, $0
inner:
  addi $1, $1, 1
  bne  $1, $11, inner
  bne  $2, $12, outer
the first add instruction is located at address 0.

what is our misprediction rate if we just use a pattern history table with 2 entries? [misprediction rate = # mispredictions / # predictions]

what if we use a local history predictor with a 2-entry local history table, and a 4-entry pattern history table?

First, I wonder, if there is an error in the condition, and both add instructions must, just like the rest, be addi with immediate 0 instead of $0. Can anyone familiar with the subject comment on it?

Second, I tried to solve the problem (considering add to be addi with immediate 0, as mentioned above), and considering initial state of saturated counters to be strongly not taken. My answers were:

for 1. the misprediction rate 8/10 (8 mispredicts, 10 predicts)
for 2. the misprediction rate 13/5 (13 mispredicts, 5 predicts)
Can anyone familiar with the subject give it a check? Just wondering if I indeed understood the lecture's material. Thanks.

Register $0 is probably always 0, and something like addi $11, 0, 0 would illegal because no CPU supports instructions with two immediate operands as they're not actually useful. — Ross Ridge
Agree. I meant smth. like addi $2, $0, 0. It must be the same in this context, though. — Bob

rda rda · Accepted Answer · 2018-11-20T17:18:13

$0 (also r0 or $zero) is a register that is always zero. Is convenient for comparisons and setting variables, in your example, it's used to set variables. Note that "add $2, $0, $0" is equivalent to "addi $2, $0, 0" which is (in C-like notation) "$2 = 0;". Same expression encoded using different formats of mips instructions (R and I respectively)

If we were to write that assembly code in a C-like fashion, it would look something like this:

$11 = 5;
$12 = 3;

$2 = 0;
while ($2 != $12){
    $2++;
    $1 = 0;
    while ($1 != $11)
        $1++;
    }

Hope this helps.

small branch prediction exercise (not homework)

1 Answers