Как распараллелить суммы обновления с OpenMP

Question

Как распараллелить суммы обновления с OpenMP

Следующий цикл выполняет итерации по всем ребрам графа, определяет, принадлежат ли конечные узлы одной и той же группе, а затем добавляет вес ребра к общему весу ребра этой группы.

// 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 директива и там говорится, что:

К сожалению, параметр атомарности может быть указан только для простого
выражения, которые обычно могут быть скомпилированы в один процессор
код операции, такой как приращение, уменьшение, xors и тому подобное. За
Например, он не может включать вызовы функций, индексирование массивов, перегружены
операторы, не POD-типы или несколько операторов.

Что я должен использовать, чтобы правильно распараллелить этот цикл?

2

c++critical-section openmp parallel-processing

Решение

Другие решения

Я также думаю, что ваш блок if является критическим разделом, вы не должны записывать вектор из нескольких потоков без сериализации записей. Ты можешь использовать #pragma omp critical ограничить выполнение + = в вашем блоке if одним потоком за раз.

1

Вы можете разделить выражение на две части: вызов функции, которая присваивает результат временному, и добавление этого временного к аккумулятору. В этом случае второе выражение будет достаточно простым для использования omp atomic, предполагая, что само сложение не является сложным перегруженным оператором для пользовательского типа. Конечно, вы можете сделать это только в случае, если G->weight(u,v) это потокобезопасный вызов, в противном случае вы должны использовать omp critical или мьютекс.

1

Источник

Accepted Answer

На самом деле принятый синтаксис для atomic update является:

Икс++;

Икс—;

++Икс;

—Икс;

Икс = бинарный оператор выраж;

Икс знак равно Икс бинарный оператор выраж;

где Икс это скаляр л-значение выражение и выраж является любым выражением, включая вызовы функций, с единственным ограничением, что оно должно быть скалярного типа. Компилятор позаботится о сохранении промежуточного результата во временной переменной.

Иногда лучше ознакомиться со стандартными документами, а не читать учебники в Интернете. Соблюдайте стандарт OpenMP 3.1 Пример A.22.1c:

float work1(int i)
{
return 1.0 * i;
}
...
#pragma omp atomic update
x[index[i]] += work1(i);

3