compute cache miss rate by given code

Question

I have been trying to solve questions like this before but I have stumbled in difficulty to track the the space of the cache. so there is an example of a question like this:

Given the code:

int A[1024,1024],B[1024,1024],C[1024,1024]

  for(int i=0;i<1024;i++){
     for(int j=0;j<1024;j++){
       for(int k=0;k<1024;k++){
            A[i,j]+=B[i,k]+C[k,j];
     }
    }
   }

That runs on a proccessor with data cache that has LRU(least recently used feature of the cache) and is fully associative. the cache has total size of 32KB and each block has size of 64B. size of int is 4 bytes. arrays are placed continously on memory.

what is the percentge miss rate(approximately) of cache in this program?

what I know: when we retrieve an element from the array we also bring all the block, for example for first element in B we bring the rest 64(Bytes)/4(size of int) =16 elements to the cache and thus we will have one miss at first but for the rest(15 elements of B) we wont have a miss cause they are in the cache. for array C we go to the main memory each time because the block that was brought is not the same block to the row after it.

thank you very much in advance!

Answer 1

Your cache has 512 cache lines (512 x 64Byte cache line size = 32Kilobyte cache size).

In the innermost loop, each value k accesses a different row of the array, with each row being 1024 x 4 = 4,096, so each k accesses a different cache line. You therefore access 1024 different cache lines, your processor only has 512 lines, so any cache line belonging to array C will have been evicted before it is reused. 1024 cache misses for the complete inner loop, 1024^3 all in all. Your cache is quite useless.

The accesses to B[i, k] read 4096 consecutive bytes for 4096/64 = 64 cache misses, so that adds 64 x 1024^2 misses, and A[i, j] will remain cached practically all the time.

You greatly improve this by looping

for (j1 = 0; j1 < 1024; j1 += 16) {
    for (k = 0; k < 1024; ++k) {
        for (j = j1; j < j1 + 16; ++j) {
            ....
        }
    }
}