Nested Loop Optimisation in C and OpenMP

Question

Actually I have two questions, the first one is, considering cache, which one of the following code is faster?

int a[10000][10000];
for(int i = 0; i < 10000; i++){
    for(int j = 0; j < 10000; j++){
       a[i][j]++;
    }
}

or

int a[10000][10000];
for(int i = 0; i < 10000; i++){
    for(int j = 0; j < 10000; j++){
       a[j][i]++;
    }
}

I am guessing the first one will be much faster since there are a lot less cache miss. And my question is if you are using OpenMP, what kind of technique will you use to optimise such a nested loop? My strategy is to divide the outer loop into 4 chunks and assign them among 4 cores, is there any better way (more cache friendly) to do it?

Thanks! Bob

You can test both on you platform. But I assume, 1st fastest. Also, question: Is array element must be int? Perhaps, enough short or char? By decrease element size, you will decrease memory traffic. — olegarch
– olegarch, Commented Oct 11, 2013 at 23:52

EKT · Accepted Answer · 2013-10-12 01:26:08Z

2

As maxihatop pointed out, the first one performs better because it has better cache locality.

Dividing the outer loop into chunks is a good strategy in the case like this, where the complexity of the task inside the loop is constant.

You might want to take a look at #pragma omp for schedule(static). This will evenly divide the iterations contiguously among threads. So your code should look like:

#pragma omp for schedule(static)
for (i = 0; i < 10000; i++) {
    for(j = 0; j < 10000; j++){
        a[i][j]++;
    }

Lawrence Livermore National Laboratory provides a fantastic tutorial of OpenMP. You can find more information there. https://computing.llnl.gov/tutorials/openMP/

edited Oct 12, 2013 at 1:26

answered Oct 12, 2013 at 1:16

EKT

292 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Nested Loop Optimisation in C and OpenMP

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related