Как OpenMP использует атомарную инструкцию внутри предложения сокращения?

Как OpenMP использует атомарные инструкции внутри сокращения? Разве это не вообще полагаться на атомную?

Поскольку стандарт OpenMP не указывает, как должно (или не должно) быть реализовано предложение reduction (например, на основе atomic операций или нет), его реализация может варьироваться в зависимости от каждой конкретной реализации стандарта OpenMP.

Например, является ли сумма переменных в приведенном ниже коде суммой с атомный + оператор?

Тем не менее, из стандарта OpenMP можно прочитать следующее:

Предложение сокращения может использоваться для выполнения некоторых форм повторения расчеты (...) параллельно. Для параллельных и совмещенных конструкций создается частная копия каждого элемента списка, по одной для каждой неявной задачи, как если бы было использовано приватное предложение. (...) Частная копия затем инициализируется, как указано выше. В конце области для которой было указано предложение сокращения, исходный элемент списка обновляется путем объединения исходного значения с окончательным значением каждого частных копий, используя объединитель указанного сокращение-идентификатор.

Таким образом, исходя из этого, можно сделать вывод, что переменные, используемые в предложении сокращения, будут частными и, следовательно, не будут обновляться атомарно. Тем не менее, даже если бы это было не так, было бы маловероятно, чтобы конкретная реализация стандарта OpenMP полагалась на операцию atomic (для инструкции sum += v[i];), поскольку (в данном случае) это была бы не самая эффективная стратегия. Для получения дополнительной информации о том, почему это так, проверьте следующие темы SO:

1. Почему мой параллельный код с использованием openMP atomic занимает больше времени, чем последовательный код?;
2. Почему я должен использовать сокращение, а не атомарную переменную?.

Проще говоря, более эффективным подходом, чем использование atomic, было бы, если бы каждый поток имел собственную копию переменной sum, а в конце parallel region каждый поток сохранял бы свою копию в ресурсе, совместно используемом потоками — теперь, в зависимости того, как реализовано сокращение, операции atomic могут использоваться для обновления этого общего ресурса. Затем этот ресурс будет выбран основным потоком, который уменьшит его содержимое и соответственно обновит исходную переменную sum.

Более формально из OpenMP Reductions Under the Hood:

Подробно изучив параллельные редукции, вы, возможно, есть некоторые открытые вопросы о том, как OpenMP на самом деле преобразует ваш последовательный код в параллельный код. В частности, вы можете задаться вопросом как OpenMP определяет ту часть тела цикла, которая выполняет сокращение. В качестве примера можно использовать этот или аналогичный фрагмент кода. часто можно найти в примерах кода:

 #pragma omp parallel for reduction(+:x)
 for (int i = 0; i < n; i++)
     x -= some_value;

Вы также можете использовать - как оператор сокращения (который на самом деле избыточен к +). Но как OpenMP изолирует шаг обновления x-= some_value? Неудобный ответ заключается в том, что OpenMP вообще не определяет обновление! Компилятор обрабатывает тело для цикла, как это:

#pragma omp parallel for reduction(+:x)
     for (int i = 0; i < n; i++)
         x = some_expression_involving_x_or_not(x);

В результате модификация x также может быть скрыта за непрозрачным вызовом функции >. Это приемлемое решение с точки зрения компилятора разработчик. К сожалению, это означает, что вы должны убедиться, что все обновления x совместимы с операцией, определенной в оговорка о сокращении.

Общий поток выполнения сокращения можно резюмировать как следует:

1. Создайте группу потоков и определите набор итераций, которые должен выполнить каждый поток j.
2. Каждый поток объявляет приватизированный вариант редукционной переменной x, инициализированной нейтральным элементом e соответствующего моноид.
3. Все потоки выполняют свои итерации независимо от того, включают ли они обновление приватизированной переменной и каким образом.
4. Результат вычисляется как последовательное сокращение по (локальным) частичным результатам и глобальной переменной x. Наконец, результат записано обратно в х.

Иногда бывает полезно проверить сгенерированную сборку. Например, GCC сгенерировал для меня следующие инструкции (live demo):

  ...
  add rcx, rax
  xor eax, eax
  lea rcx, [rsi+4+rcx*4]
.L4:
  add eax, DWORD PTR [rdx]
  add rdx, 4
  cmp rdx, rcx
  jne .L4
  mov ecx, eax
.L3:
  lock add DWORD PTR [rbx+12], ecx
  ...

Эти инструкции выполняются всеми потоками внутри параллельной области. Метка .L4: представляет часть цикла, выполняемую фактической нитью. Результат локальной частичной суммы потока накапливается в eax (по add eax, DWORD PTR [rdx]), которая сначала обнуляется (xor eax, eax). Наконец, результат перемещается в ecx и из ecx в ячейку памяти, которая представляет переменную sum.

Обратите внимание, что приращение этой ячейки памяти является атомарным из-за префикса lock инструкции add.

С GCC ответ на ваш вопрос, таким образом, ДА — он использует атомарное приращение, но каждый поток делает это только один раз в конце. (Теоретически можно было бы использовать атомарное приращение общего результата в каждой итерации, но это было бы ужасно неэффективно. Даже с отключенными оптимизациями GCC этого не делает.)

В предложении сокращения могут быть спрятаны атомарные элементы, но, вероятно, не там, где вы ожидаете их увидеть.

Во-первых, sum += v[i]; не реализуется с использованием атомарных операций, потому что в этом нет необходимости. Спецификация OpenMP довольно четко указывает, что переменные сокращения — это не что иное, как частные переменные со следующей дополнительной семантикой:

• в отличие от обычных частных переменных, переменные редукции инициализируются нулевым значением оператора редукции; для + это значение равно 0;
• отдельные частные значения переменной сокращения объединяются (сокращаются) в значение исходной переменной в конце конструкции OpenMP, к которой привязано сокращение.

Это та вторая часть, где реализация может использовать атомарные операции. Как объяснил @dreamcrash, спецификация OpenMP не предписывает, как (или даже когда) именно происходит уменьшение отдельных значений. В любом случае то, что делает reduction, эквивалентно преобразованию

int sum = 0;

#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < m; i++)
  sum += v[i];

в

int sum = 0;

#pragma omp parallel
{
  int sum_priv = 0;

  #pragma omp for
  for (int i = 0; i < m; i++)
    sum_priv += a[i];

  // BEGIN actual reduction
  #pragma omp atomic update
  sum += sum_priv;
  // END actual reduction
}

Обозначенная часть — это место, где происходит фактическое сокращение, т. е. переменная sum обновляется значениями отдельных частных копий. Это можно реализовать с помощью atomic, как показано на рисунке, но есть и более эффективные способы, например попарное сокращение дерева, и это может быть даже вызов функции.