values stored in array changed in OpenMP gcc

Question

I recently started exploring OpenMP using gcc. Basically I am executing this code for demonstrateing sieve of Eratosthenes.

void main() {
    int n, iterate_limit;

    printf("Enter the number limit for sieve of erathoros:");
    scanf("%d", &n);
    iterate_limit = (int) sqrt((double) n);
    printf("iterate limit is %d\n", iterate_limit);
    int primes[n], prime_index = 0;
    int non_primes[n], non_prime_index = 0;

    #pragma omp parallel for
    for (int i = 2; i <= iterate_limit; i++) {
        if (isprime(i) == 1) {
            int num = i;

            printf("prime is %d\n", i);
            primes[prime_index] = num;
            prime_index++;
            num += i;
            while (num < n) {
                non_primes[non_prime_index] = num;
                non_prime_index++;
                num += i;
            }
        }
    }

    printf("primes are\n"); 
    for (int i = 0; i < prime_index; i++) {
        printf("%d\n ", primes[i]);  
    }
}

Ideally, the array primes should contain all the numbers whose multiples are to be eliminated, which it does for an input of 25 or 50. But strangely enough, when giving a bigger number as input such as 99 or 125 the values in the primes array are different from expected. Even though the printf("prime is %d\n",i); gives valid output. Here is the output for 125 as input:

Enter the number limit for sieve of erathoros:125
iterate limit is 11
[New LWP 17676]
[New LWP 17677]
[New LWP 17678]
prime is 11
prime is 5
prime is 7
prime is 2
prime is 3
primes are
60
 63
 66
 69
 72
 [LWP 17676 exited]
[LWP 17677 exited]
[LWP 17674 exited]
[Inferior 1 (process 17674) exited normally]

Why I am getting 60,63,66,69,72 instead of 2,3,5,7,11?

I am running Ubuntu 18.

EDIT:

As pointed out by Osiris,I was not checking for duplicates in my non_primes array which seems to overwrite upon my primes array. Duplicate elimination did provide a temporary solution. But increasing the input number or increasing the number of threads gave incorrect results due to data races as mentioned by John Bollinger

Answer 1

You have two problems, one tactical and one strategic.

The tactical problem is that OpenMP does not relieve you of caring about data races. The OpenMP threads share variables primes and prime_index, among others. You rely on it. But all your threads both read and write prime_index, which is not atomic nor even volatile, without any inter-thread synchronization. This produces a data race, and therefore the behavior of your program is undefined. From a language perspective, that's the end of the story. "Undefined" means what it says.

In practice, the usual manifestations of data races involve different threads not seeing each others' writes to the shared variable in question, or seeing them in surprising orders. Something along those lines appears to be what is happening here.

The strategic problem is that the Sieve of Eratosthenses is a poor choice for parallelization. Or, at least its outer loop is. This is because of data dependencies across (outer) loop iterations. For the Sieve to work properly, the multiples of each prime need to be sieved out in order, because the associated prime test boils down, in words, to "has candidate X been sieved out as a multiple of a lesser number?" You cannot answer that reliably if iterations of the outer loop run in parallel rather than serial.

---

These two problems are separate and independent, in that solving the data race problem would not solve the data dependency problem, and in that it is possible, with a lot of work, to write a parallel Sieve of Eratosthenes that correctly observes data dependencies (I've actually done it, albeit in Java, not C), and that such an approach could still be broken because of data races.

By the way, even the correct and valid parallel Sieve is affected by the data dependencies, in that satisfying them limits it to having a pretty poor speedup factor.

Answer 2

If you remove OpenMP you still get the wrong output, since you are writing out of bounds of the non_primes array.

It is correct that there can not be more than n non prime numbers less than n, but you are writing some values more than once.

For example at i=2 you write every even number except 2 in the non_primes array. At i=3 you write 6,9,12,15,18,.. in it, where the even numbers are now twice element of the array. You need to check if the number is already an element of the array.