c - 存储在数组中的值在 OpenMP gcc 中更改

Question

我最近开始使用 gcc 探索 OpenMP。基本上，我正在执行这段代码来演示埃拉托色尼筛法。

void main() {
    int n, iterate_limit;

    printf("Enter the number limit for sieve of erathoros:");
    scanf("%d", &n);
    iterate_limit = (int) sqrt((double) n);
    printf("iterate limit is %d\n", iterate_limit);
    int primes[n], prime_index = 0;
    int non_primes[n], non_prime_index = 0;

    #pragma omp parallel for
    for (int i = 2; i <= iterate_limit; i++) {
        if (isprime(i) == 1) {
            int num = i;

            printf("prime is %d\n", i);
            primes[prime_index] = num;
            prime_index++;
            num += i;
            while (num < n) {
                non_primes[non_prime_index] = num;
                non_prime_index++;
                num += i;
            }
        }
    }

    printf("primes are\n"); 
    for (int i = 0; i < prime_index; i++) {
        printf("%d\n ", primes[i]);  
    }
}

理想情况下，primes 数组应该包含所有要消除其倍数的数字，输入为 25 或 50 时它会这样做。但奇怪的是，当输入一个更大的数字时，例如作为 99 或 125，primes 数组中的值与预期不同。即使 printf("prime is %d\n",i); 给出了有效的输出。这是 125 作为输入的输出:

Enter the number limit for sieve of erathoros:125
iterate limit is 11
[New LWP 17676]
[New LWP 17677]
[New LWP 17678]
prime is 11
prime is 5
prime is 7
prime is 2
prime is 3
primes are
60
 63
 66
 69
 72
 [LWP 17676 exited]
[LWP 17677 exited]
[LWP 17674 exited]
[Inferior 1 (process 17674) exited normally]

为什么我得到的是 60,63,66,69,72 而不是 2,3,5,7,11？

我正在运行 Ubuntu 18。

编辑:

正如 Osiris 指出的那样，我没有检查我的 non_primes 数组中的重复项，它似乎覆盖了我的 primes 数组。重复消除确实提供了一个临时解决方案。但是，如 John Bollinger 所述，由于数据竞争，增加输入数量或增加线程数量会产生不正确的结果。

Answer 1

您有两个问题，一个是战术问题，一个是战略问题。

战术问题 是 OpenMP 并不能解除您对数据竞争的关注。 OpenMP 线程共享变量 primes 和 prime_index 等。你依靠它。但是你的所有线程都读取和写入 prime_index，这不是原子的，甚至不是 volatile，没有任何线程间同步。这会产生数据竞争，因此您的程序的行为是未定义的。从语言的角度来看，这就是故事的结尾。 “未定义”就是它所说的。

在实践中，数据竞争的常见表现包括不同的线程看不到彼此对相关共享变量的写入，或者以令人惊讶的顺序看到它们。沿着这些思路的东西似乎就是这里正在发生的事情。

战略问题是 Eratosthenses 筛法对于并行化来说是一个糟糕的选择。或者，至少它的外循环是。这是因为跨(外)循环迭代的数据依赖性。为了使 Sieve 正常工作，需要按顺序筛选出每个素数的倍数，因为相关的素数测试归结为“是否已筛选出候选 X 的倍数一个较小的数字？”如果外循环的迭代是并行运行而不是串行运行，则您无法可靠地回答这个问题。

---

这两个问题是分开和独立的，因为解决数据竞争问题不会解决数据依赖性问题，而且有可能通过大量工作编写一个并行的埃拉托色尼筛法来正确观察数据依赖项(我实际上已经做到了，尽管是在 Java 中，而不是在 C 中)，并且由于数据竞争，这种方法仍然可能被打破。

顺便说一句，即使是正确有效的并行 Sieve 也会受到数据依赖性的影响，因为满足它们会限制它具有非常差的加速因子。