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.