Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

values stored in array changed in OpenMP gcc

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*

Cancel
2
  • Yes,I removed OpenMP and got the same issue, turns out that when I write out of bound for non_primes, it overwrites onto primes. so adding a function to check if the value already exists in non_primes resolves the issue for both single and multithreaded solutions.
    – Ankur Ranjan
    Commented Jul 18, 2018 at 18:36
  • @AnkurRanjan Yes, but for it to work reliable with multithreading you have to ensure that the data access of the variables is atomic. See also the other answer.
    – Osiris
    Commented Jul 18, 2018 at 18:41