2.6.1 用于查找质数的程序

prime_omp.c 中的线程通过执行函数 is_prime() 来检查某个整数是否为质数。

    16  int is_prime(int v)
    17  {
    18      int i;
    19      int bound = floor(sqrt(v)) + 1;
    20
    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  }

线程分析器会报告第 26 行中对 pflag[ ] 的写入与第 23 行中对 pflag[ ] 的读取之间存在数据争用。但是，此数据争用是良性的，因为它不会影响最终结果的正确性。在第 23 行，线程将检查对于给定的 i 值，pflag[i] 是否等于 0。如果 pflag[i] 等于 0，则表明 i 是已知的合数（换句话说，知道 i 不是质数）。因此，无需检查 v 是否可以被 i 整除；只需检查 v 是否可以被某个质数整除。因此，如果 pflag[i] 等于 0，该线程会继续处理 i 的下一个值。如果 pflag[i] 不等于 0 并且 v 可以被 i 整除，该线程会将 0 分配给 pflag[v] 以表明 v 不是质数。

从正确性方面来说，多个线程检查同一 pflag[ ] 元素并同时向其写入是可以的。pflag[ ] 元素的初始值为 1。当线程更新该元素时，它们会为该元素分配值 0。也就是说，这些线程会在该元素的同一内存字节的同一位中存储 0。在当前的体系结构中，可以放心地认为这些存储是原子操作。这意味着，某个线程读取该元素时，读取的值要么为 1，要么为 0。如果某个线程在给定的 pflag[ ] 元素（第 23 行）被分配值 0 之前对该元素进行检查，则该线程会执行第 25–28 行。在此期间，如果另一个线程也将 0 分配给同一 pflag[ ] 元素（第 26 行），最终结果不变。在本质上，这意味着第一个线程不必要地执行了第 25–28 行，但最终结果是相同的。