-1

If I have a for loop like the one the bellow. How do I calculate the cache miss rate.

for (i = 0; i < N-1; i++){
 a[i] = (a[i] + a[i+1])/2;
}

There will be a compulsory cache miss at the starting as the cache wouldn't have been loaded. But will there also be a cache miss for a[i+1]? is this the correct approach for calculating cache miss rate?

1 Answer 1

0

You can try to use the tsc register from the core is executing your code, whenever there's a cache miss you'll get a significantly higher access time so you can infer a cache miss happened.

unsigned long long int rdtsc(void){
       unsigned long long int x;
       unsigned a, d;

       __asm__ volatile("rdtsc" : "=a" (a), "=d" (d));

       return ((unsigned long long)a) | (((unsigned long long)d) << 32);;
}

So you might want to read tsc register before and after you execute the instruction you want to measure access to cache, like the following graph.

You can check the image on the following link to give you an idea on how this works. https://adriancolyer.files.wordpress.com/2018/01/meltdown-fig-4.jpeg?w=480

long long int start_time = 0;
long long int total_time = 0;

for (i = 0; i < N-1; i++){
    start_time = rdtsc();
    a[i] = (a[i] + a[i+1])/2;
    total_time = rdtsc() - start_time;
}

Hope this helps you.

2
  • We need to do it by hand and as well as code and compare... How would you do it by hand?
    – Sri davei
    Apr 19, 2018 at 17:05
  • Guess it depends of the size of each member of your array and your cache line granularity, in the best case scenario your array is cache line aligned, and your first access will bring the beginning of your array and will be able to accessed all data until the for loop sweeps the data contained within the first cache line, if it runs out it will need to fetch the next cache line, and so on and so forth... however modern CPU's prefetchs data surrounding the first fetched $line minimizing cache miss. Apr 19, 2018 at 21:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.