OpenMP：用于迭代次数不断变化的循环

Question

我想使用 OpenMP 使我的程序运行更快。不幸的是，情况恰恰相反。我的代码看起来像这样：

const int max_iterations = 10000;
int num_interation = std::numeric_limits<int>::max();

#pragma omp parallel for
for(int i = 0; i < std::min(num_interation, max_iterations); i++)
{
  // do sth.

  // update the number of required iterations
  // num_interation can only become smaller over time
  num_interation = update_iterations(...);
}

由于某种原因，处理的迭代比需要的多。如果没有 OpenMP，平均需要 500 次迭代。但是，即使将线程数设置为一个 (set_num_threads(1))，它也会计算超过一千次迭代。如果我使用多线程，以及在更新 num_iterations 时使用写锁，也会发生同样的情况。

我认为它与内存带宽或竞争条件有关。但这些问题不应该出现在 set_num_threads(1) 的情况下。

因此，我认为它可能与调度和块大小有关。不过，这个我真的不是很清楚。

有人可以给我提示吗？

Answer 1

the OpenMP standard 第 56 页给出了您遇到的行为的快速答案：

The iteration count for each associated loop is computed before entry to the outermost loop. If execution of any associated loop changes any of the values used to compute any of the iteration counts, then the behavior is unspecified.

本质上，这意味着您一旦进入循环就无法修改循环的边界。尽管根据标准，行为是 "unspecified"，但在您的情况下，发生的事情非常清楚，因为一旦您在代码上打开 OpenMP，您就会计算最初指定的迭代次数。

所以你必须采取另一种方法来解决这个问题。

这是一个可能的解决方案（在许多其他解决方案中），我希望它可以扩展。它的缺点是可能允许发生比您预期的次数更多的迭代（假设 //do sth. 是平衡的，最多比预期多 OMP_NUM_THREADS-1 次迭代，如果不是，则更多）。此外，它假设 update_iterations(...) 是线程安全的并且可以并行调用而不会产生不必要的副作用... 这是一个非常强大的假设，您最好强制执行！

num_interation = std::min(num_interation, max_iterations);
#pragma omp parallel
{
    int i = omp_get_thread_num();
    const int nbth = omp_get_num_threads();
    while ( i < num_interation ) {
        // do sth.

        // update the number of required iterations
        // num_interation can only become smaller over time
        int new_num_interation = update_iterations(...);
        #pragma omp critical
        num_interation = std::min(num_interation, new_num_interation);
        i += nbth;
    }
}

一个更同步的解决方案，如果 //do sth. 不是那么平衡并且不做太多额外的迭代很重要，可以是：

num_interation = std::min(num_interation, max_iterations);
int nb_it_done = 0;
#pragma omp parallel
{
    int i = omp_get_thread_num();
    const int nbth = omp_get_num_threads();
    while ( nb_it_done < num_interation ) {
        // do sth.

        // update the number of required iterations
        // num_interation can only become smaller over time
        int new_num_interation = update_iterations(i);
        #pragma omp critical
        num_interation = std::min(num_interation, new_num_interation);
        i += nbth;
        #pragma omp single
        nb_it_done += nbth;
    }
}

这里的另一个奇怪的事情是，由于您没有显示 i 的用途，因此不清楚随机迭代到域中是否是一个问题。如果不是，第一个解决方案应该可以很好地工作，即使对于不平衡 //do sth.。但如果这是一个问题，那么你最好坚持第二种解决方案（甚至可能会加强同步性）。

但归根结底，现在有一种方法（我能想到并且具有良好的并行性）可以避免潜在的额外工作要做，因为迭代次数可能会随之改变。

OpenMP：用于迭代次数不断变化的循环

OpenMP: for loop with changing number of iterations

parallel-processing

multithreading

for-loop

openmp