An answer to this question on Stack Overflow.

Question

I have a loop that iterates from 1 to N and takes a modular sum over time. However N is very large and so I am wondering if there is a way to modify it by taking advantage of multithread.

To give sample program

for (long long i = 1; i < N; ++i)
   total = (total + f(i)) % modulus;

f(i) in my case isn't an actual function, but a long expression that would take up room here. Putting it there to illustrate purpose.

Answer

Yes, try this:

double total=0;
#pragma omp parallel for reduction(+:total)
for (long long i = 1; i < N; ++i)
  total = (total + f(i)) % modulus;

Compile with:

g++ -fopenmp your_program.c

It's that simple! No headers are required. The #pragma line automatically spins up a couple of threads, divides the iterations of the loop evenly, and then recombines everything after the loop. Note though, that you must know the number of iterations beforehand.

This code uses OpenMP, which provides easy-to-use parallelism that's quite suitable to your case. OpenMP is even built-in to the GCC and MSVC compilers.

This page shows some of the other reduction operations that are possible.

If you need nested for loops, you can just write

double total=0;
#pragma omp parallel for reduction(+:total)
for (long long i = 1; i < N; ++i)
for (long long j = 1; j < N; ++j)
  total = (total + f(i)*j) % modulus;

And the outer loop will be parallelised, with each thread running its own copy of the inner loop.

But you could also use the collapse directive:

#pragma omp parallel for reduction(+:total) collapse(2)

and then the iterations of both loops will be automagically divied up.

If each thread needs its own copy of a variable defined prior to the loop, use the private command:

double total=0, cheese=4;
#pragma omp parallel for reduction(+:total) private(cheese)
for (long long i = 1; i < N; ++i)
  total = (total + f(i)) % modulus;

Note that you don't need to use private(total) because this is implied by reduction.