# compute cache miss rate by given code

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!

– D.W.
Aug 12, 2022 at 8:19
• Where did you encounter this task? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
Aug 12, 2022 at 8:20
• Hey, I have just updated the question. Thank you for the notice. since I am struggling with questions like this and do not know how to approach them I thought that if someone explain to me about this then I will understand better. thank you again for your patiance :)
– user152808
Aug 12, 2022 at 8:28
• Please show me any processor with 32KB fully associative LRU cache. Aug 12, 2022 at 8:30
• I rolled back your "edit". Time was spent on supplying an answer. Your behaviour is extremely disrespectful. Aug 16, 2022 at 18:43

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) {
....
}
}
}