Consider the following code fragment:

int a[8192], b[8192], c[8192];
int i;
for(i = 0; i < 8192; i++)
    c[i] = a[i] + b[i];

For what kind of cache will this program not run well (set associative, direct, associative)? I've been thinking about how to optimize this, but can't really see how it can be done. How can I change this code to have fewer cache misses?

  • You might find a few hints in Ulrich Drepper's paper here: akkadia.org/drepper/cpumemory.pdf – James Jul 24 '12 at 22:55
  • I've done some research, and I believe that with a set-associative mapped cache, this code will cause a large number of cache misses. The solution is to increase the size of each array by 1, so the number of elements is not a power of 2. – Meta Jul 25 '12 at 1:57

I'd expect virtually nothing in terms of cache misses from the sample code. It has only three streams, and it's directly linear in memory.

The best that you can do to improve it's speed is align the arrays to a page boundary (4kb on x86) and attempt vectorization, loop unrolling, and possibly parallelism. Past that, there's not much more you can do.

  • I'll add a comment that linear access makes it prefetch friendly. – rwong Jul 25 '12 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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