2

以下循环遍历图的所有边，确定末端节点是否属于同一组，然后将边权重添加到该组的总边权重中。

// TODO: parallel
FORALL_EDGES_BEGIN((*G)) {
    node u = EDGE_SOURCE;
    node v = EDGE_DEST;
    cluster c = zeta[u];
    cluster d = zeta[v];
    if (c == d) {
        // TODO: critical section
        intraEdgeWeight[c] += G->weight(u, v);
    } // else ignore edge
} FORALL_EDGES_END();

我想将它与OpenMP并行化。我认为 if 语句中的代码是一个关键部分，如果线程在中间被中断，可能会导致竞争条件和错误结果（对吗？）。

如果+=可以原子地进行操作，我相信问题已经解决（正确吗？）。但是，我查看了该atomic指令，其中指出：

不幸的是，原子性设置只能指定给通常可以编译为单个处理器操作码的简单表达式，例如递增、递减、异或等。例如，它不能包含函数调用、数组索引、重载运算符、非 POD 类型或多个语句。

我应该用什么来正确地并行化这个循环？

4

3 回答 3

3

实际上接受的语法atomic update是：

x ++;

x——；

++ x ;

-- x ;

x binop= expr ;

x = x binop expr ;

其中x是一个标量左值表达式，而expr是任何表达式，包括函数调用，唯一的限制是它必须是标量类型。编译器会注意将中间结果存储在临时变量中。

有时最好查阅标准文档而不是阅读 Internet 上的教程。遵守 OpenMP 3.1 标准示例 A.22.1c：

float work1(int i)
{
  return 1.0 * i;
}
...
#pragma omp atomic update
x[index[i]] += work1(i);
于 2012-12-13T11:51:08.763 回答
1

您可以将表达式分为两部分：将结果分配给临时的函数调用，以及将该临时添加到累加器。omp atomic在这种情况下，假设加法本身不是自定义类型的复杂重载运算符，则第二个表达式将非常简单易用。当然，您只能在G->weight(u,v)线程安全调用的情况下这样做，否则您必须使用omp critical或互斥锁。

于 2012-12-13T10:57:45.503 回答
1

我也认为你的 if 块是一个关键部分，你不应该在没有序列化写入的情况下从多个线程编写向量。您可以使用#pragma omp critical将 if 块中 += 的执行一次限制为单个线程。

于 2012-12-13T10:26:58.093 回答