如何在 OMP - C 中将私有数组合并到共享数组？

Question

我正在尝试并行化一个使用归约来查找局部最大值的程序。但是，我在合并过程中遇到了一个问题：合并的数组最终包含的元素比应有的元素少了两个。 这是我的代码

    double start, stop;

    const float tab[40] = {smth...};
    float maxV3[N];
    int nb_max_locaux = 0;

#pragma omp parallel
    {
        float maxTemp[N];
        int k = 0;
        int j = 0;

#pragma omp for reduction(+:nb_max_locaux)
        for (int i = 1; i < N - 1; i++) {
            if ((tab[i - 1] < tab[i]) && (tab[i + 1] < tab[i])) {
                maxTemp[nb_max_locaux] = tab[i];
                nb_max_locaux++;
                k++;
            }
        }

#pragma omp for
        for (int i = 0; i < nb_max_locaux; i++) {
            if (j < k) {
                maxV3[i] = maxTemp[j++];
            }
        }
    }

我尝试调试该问题，发现某些持有多个元素的线程完成迭代而没有完全清空其本地数组。

附注当使用少量线程（例如 3 个）运行相同的代码时，最终结果是正确的。

Answer 1

您观察到的行为的原因是最终 for 循环中的工作分配。尽管您没有指定计划，但大多数实现将使用静态计划将迭代均匀地分配给线程。如果并非所有线程都检测到相同数量的局部最大值，则某些线程将需要进行几次迭代才能写出其所有值。

使用原子索引，代码可以如下所示：

    const float tab[40] = {smth...};
    float maxV3[N];
    int nb_max_locaux = 0;
#pragma omp parallel for
    for (int i = 1; i < N - 1; i++) {
        if ((tab[i - 1] < tab[i]) && (tab[i + 1] < tab[i])) {
#pragma omp atomic capture
            int index = nb_max_locaux++;
            maxTemp[index] = tab[i];
        }
    }

这将导致争用原子递增

nb_max_locaux

并写入

maxTemp[]

。后者是由随机线程写入同一缓存行引起的。

此解决方案也不会保留值的顺序。