OpenMP Parallel for-loop showing little performance increase

Question

I am in the process of learning how to use OpenMP in C, and as a HelloWorld exercise I am writing a program to count primes. I then parallelise this as follows: ``` int numprimes = 0; #pragma omp parallel for reduction (+:numprimes) for (i = 1; i <= n; i++) { if (is_prime(i) == true) numprimes ++; } ``` I compile this code using `gcc -g -Wall -fopenmp -o primes primes.c -lm` (`-lm` for the `math.h` functions I am using). Then I run this code on an `Intel® Core™2 Duo CPU E8400 @ 3.00GHz × 2`, and as expected, the performance is better than for a serial program. The problem, however, comes when I try to run this on a much more powerful machine. (I have also tried to manually set the number of threads to use with `num_threads`, but this did not change anything.) Counting all the primes up to `10 000 000` gives me the following times (using `time`): 8-core machine: ``` real 0m8.230s user 0m50.425s sys 0m0.004s ``` dual-core machine: ``` real 0m10.846s user 0m17.233s sys 0m0.004s ``` And t…

Accepted Answer

This performance is happening because:

- `is_prime(i)` takes longer the higher `i` gets, and

- Your OpenMP implementation uses static scheduling by default for `parallel for` constructs without the `schedule` clause, i.e. it chops the for loop into equal sized contiguous chunks.

In other words, the highest-numbered thread is doing all of the hardest operations.

Explicitly selecting a more appropriate scheduling type with the `schedule` clause allows you to divide work among the threads fairly.

This version will divide the work better:

```
int numprimes = 0;
#pragma omp parallel for schedule(dynamic, 1) reduction(+:numprimes) 
for (i = 1; i <= n; i++)
{
    if (is_prime(i) == true)
        numprimes ++;
}
```

Information on scheduling syntax is available via MSDN and Wikipedia.

`schedule(dynamic, 1)` may not be optimal, as High Performance Mark notes in his answer. There is a more in-depth discussion of scheduling granularity in this OpenMP wihtepaper.

Thanks also to Jens Gustedt and Mahmoud Fayez for contributing to this answer.

OpenMP Parallel for-loop showing little performance increase

Solution

Problem