Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
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

1 Answer

up vote 3 down vote

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.

share|improve this answer
I'll add a comment that linear access makes it prefetch friendly. – rwong Jul 25 '12 at 2:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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