title: small branch prediction exercise (not homework)
body: <p>This is NOT homework. I was reading <a href="http://cseweb.ucsd.edu/%7Ej2lau/cs141/week7.html" rel="nofollow noreferrer">this site</a> which, IMO, has pretty good introduction into branch prediction, and decided to try solving a problem following the lecture:</p>
  <blockquote>
  <p>consider the following code [no branch delay slots]:</p>
  <pre><code>  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
  </code></pre>
  <p>the first add instruction is located at address 0.</p>
  <ol>
  <li>what is our misprediction rate if we just use a pattern history table with 2 entries? [misprediction rate = # mispredictions / # predictions]</li>
  <li>what if we use a local history predictor with a 2-entry local history table, and a 4-entry pattern history table?</li>
  </ol>
  </blockquote>
  <p><strong>First</strong>, 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?</p>
  <p><strong>Second</strong>, I tried to solve the problem (considering add to be addi with immediate 0, as mentioned above), and considering <strong>initial state of saturated counters to be strongly not taken</strong>. My answers were:</p>
  <p>for 1. the misprediction rate 8/10 (8 mispredicts, 10 predicts)<BR>
  for 2. the misprediction rate 13/5 (13 mispredicts, 5 predicts)<BR>
  Can anyone familiar with the subject give it a check? Just wondering if I indeed understood the lecture's material.
  Thanks.</p>