0
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ We're not looking for posts that are the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W.
    Aug 12, 2022 at 8:19
  • $\begingroup$ Where did you encounter this task? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Aug 12, 2022 at 8:20
  • $\begingroup$ 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 :) $\endgroup$
    – user152808
    Aug 12, 2022 at 8:28
  • $\begingroup$ Please show me any processor with 32KB fully associative LRU cache. $\endgroup$
    – gnasher729
    Aug 12, 2022 at 8:30
  • 1
    $\begingroup$ I rolled back your "edit". Time was spent on supplying an answer. Your behaviour is extremely disrespectful. $\endgroup$
    – gnasher729
    Aug 16, 2022 at 18:43

1 Answer 1

1
$\begingroup$

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) {
            ....
        }
    }
}
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.