Разница между политиками выполнения и тем, когда их использовать

Ответ 1

seq означает "выполнить последовательно" и является тем же самым, что и версия без политики выполнения.

par означает "выполнить параллельно", что позволяет выполнять реализацию по нескольким потокам параллельно. Вы несете ответственность за то, чтобы в течение f не происходило никаких скачков данных.

par_unseq означает, что в дополнение к разрешению выполнения в нескольких потоках реализация также допускает чередование отдельных итераций цикла в пределах одного потока, то есть загрузка нескольких элементов и выполнение f для всех из них только после этого. Это необходимо для разрешения векторизации.

Ответ 2

В чем разница между seq и par/par_unseq?

std::for_each(std::execution::seq, std::begin(v), std::end(v), function_call);

std::execution::seq означает последовательное выполнение. Это значение по умолчанию, если вы вообще не укажете политику выполнения. Это заставит реализацию последовательно выполнять все вызовы функций. Также гарантируется, что все выполняется вызывающим потоком.

Напротив, std::execution::par и std::execution::par_unseq подразумевают параллельное выполнение. Это означает, что вы обещаете, что все вызовы данной функции можно безопасно выполнять параллельно, не нарушая никаких зависимостей данных. Реализации разрешено использовать параллельную реализацию, хотя она не вынуждена это делать.

В чем разница между par и par_unseq?

par_unseq требует более сильных гарантий, чем par, но допускает дополнительные оптимизации. В частности, par_unseq требует опции чередования выполнения нескольких вызовов функций в одном потоке.

Проиллюстрируем разницу с примером. Предположим, вы хотите распараллелить этот цикл:

std::vector<int> v = { 1, 2, 3 };
int sum = 0;
std::for_each(std::execution::seq, std::begin(v), std::end(v), [&](int i) {
  sum += i*i;
});

Вы не можете напрямую распараллелить вышеприведенный код, так как он будет вводить зависимость данных для переменной sum. Чтобы этого избежать, вы можете ввести блокировку:

int sum = 0;
std::mutex m;
std::for_each(std::execution::par, std::begin(v), std::end(v), [&](int i) {
  std::lock_guard<std::mutex> lock{m};
  sum += i*i;
});

Теперь все вызовы функций можно безопасно выполнять параллельно, и при переключении на par код не прерывается. Но что произойдет, если вы вместо этого используете par_unseq, где один поток может потенциально выполнять несколько вызовов функций не в последовательности, а одновременно?

Это может привести к тупиковой ситуации, например, если код переупорядочен следующим образом:

 m.lock();    // iteration 1 (constructor of std::lock_guard)
 m.lock();    // iteration 2
 sum += ...;  // iteration 1
 sum += ...;  // iteration 2
 m.unlock();  // iteration 1 (destructor of std::lock_guard)
 m.unlock();  // iteration 2

В стандарте термин "векторизация-небезопасный". Цитировать из P0024R2:

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

Один из способов сделать код выше векторизации безопасным, заключается в замене мьютекса на атомный:

std::atomic<int> sum{0};
std::for_each(std::execution::par_unseq, std::begin(v), std::end(v), [&](int i) {
  sum.fetch_add(i*i, std::memory_order_relaxed);
});

Каковы преимущества использования par_unseq над par?

Дополнительные оптимизации, которые реализация может использовать в режиме par_unseq, включают в себя векторизованное выполнение и миграцию работы по потокам (последнее имеет значение, если задача parallelism используется с планировщиком родительского кража).

Если векторизация разрешена, реализации могут внутренне использовать SIMD parallelism (Single-Instruction, Multiple-Data). Например, OpenMP поддерживает его через #pragma omp simd аннотации, что может помочь компиляторам генерировать лучший код.

Когда я предпочитаю std::execution::seq?

• правильность (исключая расы данных)
• избежание параллельных накладных расходов (затраты на запуск и синхронизация)
• простота (отладка)

Не редкость, что зависимости данных будут обеспечивать последовательное выполнение. Другими словами, используйте последовательное выполнение, если параллельное выполнение добавит расы данных.

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

Parallelism также не предоставляется бесплатно. Если ожидаемое общее время выполнения цикла очень низкое, последовательное выполнение, скорее всего, будет лучшим даже с точки зрения чистой производительности. Чем больше данных и более дорогостоящий каждый шаг вычисления, тем менее важны служебные данные синхронизации.

Например, использование parallelism в приведенном выше примере не имеет смысла, поскольку вектор содержит только три элемента и операции очень дешевы. Также обратите внимание, что исходная версия - до введения мьютексов или атома - не содержала накладных расходов на синхронизацию. Общей ошибкой в ​​измерении ускорения параллельного алгоритма является использование параллельной версии, работающей на одном ЦП в качестве базовой линии. Вместо этого вы всегда должны сравнивать с оптимизированной последовательной реализацией без накладных расходов на синхронизацию.

Когда я предпочитаю std::execution::par_unseq?

Во-первых, убедитесь, что он не жертвует правильностью:

• Если при выполнении шагов параллельно с разными потоками есть раскладки данных, par_unseq не является параметром.
• Если код является векторизованным небезопасным, например, поскольку он получает блокировку, par_unseq не является опцией (но par может быть).

В противном случае используйте par_unseq, если это критически важная часть производительности, а par_unseq улучшает производительность над seq.

Когда я предпочитаю std::execution::par?

Если этапы могут выполняться безопасно параллельно, но вы не можете использовать par_unseq, потому что это векторизация-небезопасная, она является кандидатом на par.

Как и seq_unseq, убедитесь, что это критически важная часть производительности, а par - улучшение производительности по сравнению с seq.

Источники:

• cppreference.com(политика выполнения)
• P0024R2: Стандарт parallelism должен быть стандартизован