Oracle® Solaris Studio 12.4: Thread Analyzer User's Guide

Exit Print View

Updated: December 2014

A Program for Finding Primes

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

    16  int is_prime(int v)
    17  {
    18      int i;
    19      int bound = floor(sqrt(v)) + 1;
    21      for (i = 2; i < bound; i++) {
    22          /* no need to check against known composites */
    23          if (!pflag[i])
    24              continue;
    25          if (v % i == 0) {
    26              pflag[v] = 0;
    27              return 0;
    28          }
    29      }
    30      return (v > 1);
    31  }

Thread Analyzer reports that there is a data race between the write to pflag[ ] on line 26 and the read of pflag[ ] on line 23. However, this data race is benign as it does not affect the correctness of the final result. At line 23, 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 or not v is divisible by i; you 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 23) before it has been assigned the value zero, it then executes lines 25–28. If, in the meantime, another thread assigns zero to that same pflag[ ] element (line 26), the final result is not changed. Essentially, this means that the first thread executed lines 25–28 unnecessarily, but the final result is the same.