1

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.

  1. what is our misprediction rate if we just use a pattern history table with 2 entries? [misprediction rate = # mispredictions / # predictions]
  2. 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.

Community
  • 1
  • 1
Bob
  • 137
  • 1
  • 6
  • 3
    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 Sep 06 '16 at 18:52
  • Agree. I meant smth. like addi $2, $0, 0. It must be the same in this context, though. – Bob Sep 06 '16 at 18:55

1 Answers1

1

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

rda
  • 86
  • 4
  • The asm has `do{}while()` loops, like normal for asm. With optimization enabled you'd expect your C loop could optimize away the check before the first iteration, because it can prove that the loop runs at least once. But if you're not going to write it with the same loop structure as the asm, you might as well write it as a `for` loop. – Peter Cordes Nov 20 '18 at 17:31
  • That's fair. However, my goal was to make the code easier to understand and I feel that while loops are cleaner than do-whiles. This is of course debatable. – rda Nov 20 '18 at 18:11
  • I feel like understanding `do{}while()` loops is critical to understanding normal asm ([Why are loops always compiled into "do...while" style (tail jump)?](https://stackoverflow.com/q/47783926)). Once you're used to reading asm, you can easily read do/while loops in C. – Peter Cordes Nov 20 '18 at 18:16