c++ - 如何减少 OpenMP 中 for 循环内关键部分内的值？

Question

编辑

让我们重述一切。我正在 OpenMP 上实现 Bellman-Ford。据我了解， compare 步骤和 dist 的设置必须在关键 block 中完成，因为更新 dist 可能会改变结果compare 步骤——这里存在数据竞争。

我的问题是 updated_last_round 变量不需要在关键 block 中更新。这里存在数据竞争，但唯一的更新值是 true，所以这无关紧要。我对当前实现的担心是所有线程都以原子方式更新 updated_last_round 并相互减慢速度。

bool compare(int v1, int w, int v2) {
    // checks if v1 + w < v2
    if (v1 == INT_MAX) return false;
    if (v2 == INT_MAX) return true;
    return ((v1+w) < v2);
}

vector<int> bellman_ford(Graph& g, int root) {
    vector<int> dist(g.num_nodes());
    # pragma omp parallel for
    for (int i = 0; i < g.num_nodes(); i++)
        dist[i] = INT_MAX; // set INF

    dist[root] = 0;

    int round = 0;
    bool updated_last_round = true;
    // relax procedure
    while (updated_last_round && round < g.num_nodes()) {
        updated_last_round = false;
        #pragma omp parallel for
        for (int u = 0; u < g.num_nodes(); u++) {
            vector<int> neighbors = g.out_neighbors(u);
            vector<int> weights = g.out_weights_neighbors(u);
            #pragma omp parallel for 
            for (int j = 0; j < g.out_degree(u); j++) {
                int v = neighbors[j];
                int weight = weights[j];
                #pragma omp critical
                {
                if (compare(dist[u], weight, dist[v])) { 
                    dist[v] = dist[u] + weight;
                    updated_last_round = updated_last_round || true;
                }
                }
            }
        }
        round += 1;
    }

    /* ... */

    return dist;
}

原创

我正在尝试并行化 OpenMP 中的一些代码，这些代码需要在并行 for 循环内进行原子检查和设置，并且我在每次迭代结束时计算是否至少设置了一个值。

现在我正在使用 reduction(||:updated_last_round) 来减少每次迭代结束时的 bool 值，但我不确定这是否真的加快了速度，因为更新 bool 值的实际代码行仍在临界区内。

bool updated_last_round = true

while (updated_last_round) {
  updated_last_round = false;

  #pragma omp parallel for reduction(||:updated_last_round)
  for (/* stuff */) {
    // other stuff
    #pragma omp critical
    {
    if (should_update(vars_to_decide_with)) { 
      // do the important critical update

      // I DON'T want this to be atomically updated, as
      // the data race doesn't matter at all
      updated_last_round = updated_last_round || true;
    }
  }
}

有一种方法可以让关键部分只做关键的事情，然后继续设置线程本地 bool 值，然后在每次迭代结束时减少本地值，这应该是有道理的。我应该如何实现？

Answer 1

首先，同时写入 updated_last_round 在技术上仍然是竞争条件，even if you only write the same value .

但是，不要担心对 updated_last_round 的写入。与关键部分的总开销相比，它不太可能重要。 不要担心每个微小的内部循环迭代中关键部分的开销。考虑到对 dist[v] 和 dist[u] 的读写依赖性，我看不出有任何方法可以解决临界区问题。

如何添加缩减并仍然在临界区内设置 updated_last_round。从理论上讲，这会加快写入速度，因为它现在是本地的，而不是缓存失效的共享变量。但同样，与关键部分的巨大开销相比，这无关紧要。

注意:如果 out_*neighbors 函数非常昂贵，您将从并行化中获得的唯一好处。但我假设它们只是返回一个固定 vector - 出于性能原因，您应该返回并由 const& 捕获。

如果您想有效地并行化此算法，您必须考虑以某种方式对数据进行分区以解决依赖关系。注意:不幸的是，搜索“Bellman-Ford OpenMP”会显示一些非常不正确的尝试，例如 this upvoted and accepted answer on SO .

除此之外，不要使用嵌套并行性(parallel 内的 parallel 除非你真的知道你在做什么)。并行化安全的最外层循环，如果它带来性能优势，则使用 collapse

在尽可能本地声明变量方面也做得很好——这使得对竞争条件的推理变得容易得多。这对于 vector 拷贝可能有点棘手 - 无论如何应该是 const&。