OpenMP parallel for with modulo operation

Question

I'm just learning OpenMP and trying to parallelize the following construct:

for (r = 0; r <= (int)(N/2); r++)
{
    answer = ((answer % MOD) + (2 * (solve(N, r) % MOD)) % MOD) % MOD;
}

It seems to be natural to use reduction, but modulo operator is not supported for that case.

Also I tried to use private variables, but race conditions are still there:

#pragma omp parallel for private(temp)
for (r = 0; r <= (int)(N/2); r++)
{
    temp = answer;
answer = ((temp % MOD) + (2 * (solve(N, r) % MOD)) % MOD) % MOD;
}

Is there any way to get it work? Thanks.

Answer 1

Since you are restricted by whatever is possible with OpenMP 2.0, your way to go is writing a custom reduction. The basic scheme is:

• Before the parallel region, create an array for partial results. It should have at least as many elements as there are threads in the parallel region; you might use omp_get_max_threads() function which is the upper bound. Initialize it with zeros (the identity element for summation).
• Inside the parallel region, use omp_get_thread_num() function to obtain the number of the current thread within the parallel region, and use it as the index to the above array. Accumulate the result in the corresponding array element.
• After the region, use a serial loop to reduce the partial results accumulated in the array.

Answer 2

You can use the property that (x%a + y%a)%a = (x+y)%a. Then

answer = ((answer % MOD) + (2 * (solve(N, r) % MOD)) % MOD) % MOD;

is the same as

answer = (answer + 2 * solve(N, r) % MOD) % MOD;

Over the sum you can show this is the same as

Sum(answer + 2 * solve(N, r) % MOD)%MOD

Therefore, all you need to do is this

#pragma omp parallel for reduction(+:answer)
for (r = 0; r <= (int)(N/2); r++)
{
    answer += 2 * solve(N, r) % MOD
}
answer%=MOD;

This could overflow for. In that case you can do a custom reduction like this

#pragma omp parallel
{
    int answer_private = 0;
    #pragma omp for nowait
    for(int i=0; i<n; i++) {
        answer_private = ((answer_private % MOD) + (2 * (solve(N, r) % MOD)) % MOD) % MOD;
    }
    #pragma omp critical
    {
        answer = (answer%MOD + answer_private%MOD)%MOD; 
    }
}