title: Estimating the miss rate for C function
body: <p>I've been stuck on this question for a while, I think I might be missing something while trying to solve.</p>
  <p>Assumptions:</p>
  <ul>
  <li>16-way set associative L1 cache (E = 16) with a block size of 32 bytes (B = 32).</li>
  <li>N is very large, so that a single row or column cannot fit in the cache.</li>
  <li>sizeof(int) == 4</li>
  <li>Variables i, k, and sum are stored in registers.</li>
  <li>The cache is cold before each function is called.</li>
  </ul>
  <pre><code>int sum1(int A[N][N], int B[N][N])
  {
    int i, k, sum = 0;
    for (i = 0; i &lt; N; i++)
      for (k = 0; k &lt; N; k++)
       sum += A[i][k] + B[k][i];
    return sum;
  }
  </code></pre>
  <p><strong>Find the closest miss rate for sum1.</strong> (answer is 9/16)</p>
  <p>I tried to solve as follows:
  A[0][0],...,A[0][7] map to the first cache line in the first set
  A[0][8],...,A[0][15] map to the first cache line in the second set and so on till the last set in the cache, then we start filling the second cache line of each set until A is finished, then the part about calculating B was tricky because if we still have space in the cache we can fill it or we can start replacing the oldest cache blocks in each set.
  in miss rate wise, A will miss every time it maps once -&gt; a miss of N/32*N = 1/32 for one cache line  and 1/2 for all (16/32).
  Now I'm stuck trying to approach B's misses as I don't understand precisely how its being done.</p>
  <p>Thanks in advance</p>