Calculate how many cache misses will happen if we have the following code running on a 8KB 2 way set associative cache with a LRU replacement policy. The cache has 4 words per line and words are 4 bytes each. Assume we have a 20 bit addressable memory space and the array starts at memory location 0x01000. A long is 8 bytes or 2 words and the array is stored in row-major form.
A cache lookup on this system will look like:
8 bits tag
8 bits index
2 bits block offset
2 bits word offset
With each time through the inner loop we will advance 400 bytes or 0x190 bytes in memory. This will cause a cache miss with each loop through the inner loop. But the second time through the inner loop the information is already in the cache. The third time will be misses again followed by hits in the 4th. Meaning 200 cache misses.
long A[100][4];
int i, j;
long sum = 0;
for(j = 0; j < 4; ++j)
for(i = 0; i < 100; ++i)
sum += A[i][j];
Now consider the same situation with the following code
long A[100][4];
int i, j;
long sum = 0;
for(i = 0; i < 100; ++i)
for(j = 0; j < 4; ++j)
sum += A[i][j];
In this code we will have two cache misses per time through the inner loop. We go through this loop 100 times meaning 200 cache misses again.
