Как уменьшить значение внутри критической секции внутри цикла for в OpenMP?

Question

Редактировать

Давайте повторим все. Я внедряю Bellman-Ford на OpenMP. Насколько я понимаю, шаг compare и настройка dist должны выполняться в критическом блоке, поскольку обновление dist может потенциально изменить результат шага compare - здесь существует гонка данных.

Моя проблема в том, что переменную updated_last_round не нужно обновлять в критическом блоке. Здесь есть гонка данных, но единственным значением для обновления является 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 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 все еще является условием гонки , , даже если вы пишете только одно и то же значение .

Однако небеспокоиться о записи на updated_last_round.По сравнению с общей нагрузкой на критическую секцию это маловероятно. Не беспокойтесь о накладных расходах критической секции внутри каждой крошечной итерации внутреннего цикла.Учитывая зависимость чтения и записи для dist[v] и dist[u], я не вижу способа разрешить критическую секцию.

Как можно добавить сокращение и при этом установить updated_last_round в пределах критическойраздел.Теоретически это ускорило бы эту запись, поскольку теперь она локальная, а не общая переменная с аннулированием кэша.Но опять же, это не будет иметь значения по сравнению с огромными накладными расходами критической секции.

Примечание. Единственное преимущество, которое вы получили бы от распараллеливания, - это если бы функции out_*neighbors были очень дорогими.Но я предполагаю, что они просто возвращают фиксированный вектор - который вы должны вернуть и захватить const& по соображениям производительности.

Если вы хотите эффективно распараллелить этот алгоритм, вам нужно подумать о том, чтобы каким-то образом разделить ваши данные, чтобы разрешитьзависимость.Будьте осторожны: к сожалению, поиск " Bellman-Ford OpenMP " приводит к некоторым очень неправильным попыткам, таким как этот одобренный и принятый ответ на SO .

Кроме того, донне используйте вложенный параллелизм (parallel внутри parallel, если вы действительно не знаете, что делаете).Распараллеливание самого внешнего цикла, который является безопасным для этого, и использование collapse, если это приносит выигрыш в производительности

Также хорошо справляется с объявлением переменных как можно локально - это значительно упрощает рассуждение о состоянии гонки.Это может быть немного сложно с векторными копиями - в любом случае это должно быть const&.

Answer 2

Должно быть понятно, что есть возможность дать критическому разделу только делать критические вещи, а затем приступить к установке потока локального 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
    bool updated_this_iteration = false;

    if (should_update(vars_to_decide_with)) 
     { 
       #pragma omp critical
       {
          // do the important critical update
       }
       // Set local, per-iteration, value
       updated_this_iteration = true;
    }
    updated_last_round = updated_last_round ||  updated_this_iteration;
  }
}