openMP invalid controlling predicate

Question

here in this code, I'm trying to do Sieve of Eratosthenes algorithm in parallel using OpenMP when the program is serial it's working fine in

for (int i = p * p; i <= n; i += p) prime[i] = false;

but when I'm using

#pragma omp for

it give this error

error: invalid controlling predicate 17 | for (int p = 2; p * p <= n; p++)

this is the code

#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
using namespace std;
 
void SieveOfEratosthenes(int n)
{
    #pragma omp parallel
    {
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    #pragma omp for 
    for (int p = 2; p * p <= n; p++)
    {
        
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    
    #pragma omp critical
    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d  ", p);
    }
}
 
int main()
{
    printf("Enter the siza: ");
    int n ;
    scanf("%d", &n);
    printf("Following are the prime numbers from 1 to %f \n", sqrt(n));
    SieveOfEratosthenes(sqrt(n));
    printf("\n");
    return 0;
}

Check OpenMP specs, your form of loop test expression is not supported: openmp.org/specifications. It needs to be either var relational-op ub or ub relational-op var, where you have var binary-op var relational-op ub. — Daniel Langr
The Sieve of Eratosthenes is difficult to parallelize effectively because it has a lot of data dependencies. I once managed to do it (albeit not with OpenMP), and the resulting speedup was disappointing because of all the overhead required to satisfy those dependencies. — John Bollinger
My guess is that it is a university homework, moreover n should be small as array prime created on the stack, so performance is not an issue here. — Laci

Laci Laci · Accepted Answer · 2021-10-05T15:00:07

As pointed out by @Daniel Langr your form of loop test is not supported. It has to be a canonical loop form. For more details see 2.9.1 Canonical Loop Form of the OpenMP specification. Taking the square root of both sides of comparison you can change it to a supported form:

const int end_p=sqrt(n);
#pragma omp for 
for (int p = 2; p <= end_p; p++)

Note that your code has other error as well: each thread will create a private prime array and work on their private copy, so you obtain incorrect result. You can correct it by using shared prime array and atomic read and write operations:

void SieveOfEratosthenes(int n)
{    
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    
    const int end_p=sqrt(n);
    #pragma omp parallel for 
    for (int p = 2; p <= end_p; p++)
    {
        bool prime_p;
        #pragma omp atomic read
        prime_p=prime[p];
        if (prime_p == true)
        {
            for (int i = p * p; i <= n; i += p)
            {
                #pragma omp atomic write
                prime[i] = false;
            }
        }
    }
    
    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d  ", p);
    
}

openMP invalid controlling predicate

1 Answers