2.6.1 A Program for Finding Primes

The threads in the following file, omp_prime.c check whether an integer is a prime number by executing the function is_prime().

11 int is_prime(int v)
    12 {
    13     int i;
    14     int bound = floor(sqrt ((double)v)) + 1;
    15      
    16     for (i = 2; i < bound; i++) {
    17         /* No need to check against known composites */ 
    18         if (!pflag[i]) 
    19             continue;
    20         if (v % i == 0) { 
    21             pflag[v] = 0;
    22             return 0;
    23         }
    24     }
    25     return (v > 1); 
    26 }

The Thread Analyzer reports that there is a data-race between the write to pflag[] on line 21 and the read of pflag[] on line 18. However, this data-race is benign as it does not affect the correctness of the final result. At line 18, a thread checks whether or not pflag[i], for a given value of i is equal to zero. If pflag[i] is equal to zero, that means that i is a known composite number (in other words, i is known to be non-prime). Consequently, there is no need to check whether v is divisible by i; we only need to check whether or not v is divisible by some prime number. Therefore, if pflag[i] is equal to zero, the thread continues to the next value of i. If pflag[i] is not equal to zero and v is divisible by i, the thread assigns zero to pflag[v] to indicate that v is not a prime number.

It does not matter, from a correctness point of view, if multiple threads check the same pflag[] element and write to it concurrently. The initial value of a pflag[] element is one. When the threads update that element, they assign it the value zero. That is, the threads store zero in the same bit in the same byte of memory for that element. On current architectures, it is safe to assume that those stores are atomic. This means that, when that element is read by a thread, the value read is either one or zero. If a thread checks a given pflag[] element (line 18) before it has been assigned the value zero, it then executes lines 20-23. If, in the meantime, another thread assigns zero to that same pflag[] element (line 21), the final result is not changed. Essentially, this means that the first thread executed lines 20-23 unnecessarily.