Как алгоритмы С++ STL (ExecutionPolicy) определяют, сколько параллельных потоков использовать?

С++ 17 обновил 69 алгоритмов STL для поддержки parallelism, используя необязательный параметр ExecutionPolicy (как 1-й аргумент). например.

std::sort(std::execution::par, begin(v), end(v));

Я подозреваю, что стандарт С++ 17 сознательно ничего не говорит о как для реализации многопоточных алгоритмов, оставляя его для авторов библиотек, чтобы решить, что лучше (и позволяет им изменять их умы, позже). Тем не менее, я очень хочу понять на высоком уровне, какие проблемы рассматриваются при реализации параллельных алгоритмов STL.

Некоторые вопросы, на мой взгляд, включают (но не ограничиваются ими!):

  • Как максимальное количество используемых потоков (приложением С++) связано с количеством ядер процессора и/или GPU на машине?
  • Какие различия существуют в количестве потоков, используемых каждым алгоритмом? (Будет ли каждый алгоритм использовать любое количество потоков в каждом случае?)
  • Есть ли какое-либо отношение к другим параллельным вызовам STL для других потоков (в одном приложении)? (например, если поток вызывает std:: for_each (par,...), будет ли он использовать больше/меньше/одинаковых потоков в зависимости от того, будет ли std:: sort (par,...) уже запущен на каком-то другом потоке (s)? Возможно ли пул потоков?)
  • Рассматривается ли какое-либо отношение к тому, насколько заняты ядрами из-за внешних факторов? (например, если 1 ядро ​​очень занято, скажем, анализируя сигналы SETI, будет ли приложение С++ уменьшать количество потоков, которое оно использует?)
  • В некоторых алгоритмах используются только ядра ЦП? или только ядра GPU?
  • Я подозреваю, что реализация будет отличаться от библиотеки к библиотеке (компилятор для компилятора?), даже подробности об этом будут интересны.

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

Ответы

Ответ 1

На сегодняшний день большинство этих вопросов не могут быть удовлетворены стандартом. Однако ваш вопрос, как я понимаю, смешивает две концепции:

С1. Ограничения на параллельные алгоритмы

С2. Выполнение алгоритмов

Все параллельные STL файлы C++ имеют значение C1: он устанавливает ограничения на то, как команды и/или потоки могут чередоваться/трансформироваться в параллельном вычислении. С другой стороны, C2 - это стандартизация, ключевое слово - executor (подробнее об этом позже).

Для C1 существует 3 стандартных политики (в std::execution::seq par_unseq std::execution::seq, par и par_unseq), которые соответствуют каждой комбинации параллелизма задач и команд. Например, при выполнении целочисленного накопления можно использовать par_unseq, так как порядок не важен. Однако, для поплавочной арифметики, где сложение не ассоциативно, лучше подходят бы seq, чтобы, по крайней мере, получить детерминированный результат. Короче: политики устанавливают ограничения на параллельные вычисления, и эти ограничения могут потенциально использоваться интеллектуальным компилятором.

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

На сегодняшний день C1 находится в стандарте, но не C2, поэтому, если вы используете C1 с совместимым компилятором, вы не сможете указать, какой профиль выполнения вы хотите, и реализация библиотеки решит для вас (возможно, через расширения).

Итак, чтобы ответить на ваши вопросы:

(Что касается ваших первых 5 вопросов) По определению, параллельная библиотека STL C++ 17 не определяет какие-либо вычисления, просто зависимость данных, чтобы допускать возможные преобразования потока данных. На все эти вопросы будет ответить (надеюсь) executor, вы можете увидеть текущее предложение здесь. Это будет выглядеть примерно так:

executor = get_executor();
sort( std::execution::par.on(executor), vec.begin(), vec.end());

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

(Для 6-го) Существует множество библиотек, которые уже реализуют подобные концепции (executor C++ был вдохновлен некоторыми из них действительно), AFAIK: hpx, Thrust или Boost.Compute. Я не знаю, как реализованы последние два, но для hpx они используют легкие потоки, и вы можете настроить профиль выполнения. Кроме того, ожидаемый (еще не стандартизованный) синтаксис кода выше для C++ 17 по существу тот же, что и в (сильно вдохновлен) hpx.

Рекомендации:

  1. C++ 17 Параллельные алгоритмы и Beyond by Bryce Adelstein lelbach
  2. Будущее ISO C++ Неоднородные вычисления Майкла Вонга
  3. Основные исполнители C++ для включения гетерогенных вычислений в завтра C++ сегодня Майклом Вонгом
  4. Исполнители для C++ - длинная история Детлефа Вольмана

Ответ 2

Предварительный проект С++ 17 ничего не говорит о том, " как реализовать многопоточные алгоритмы ", это правда. Владельцы реализации сами решают, как это сделать. Например, Parallel STL использует TBB как потоковый сервер и OpenMP в качестве векторизации. Я предполагаю, что для того, чтобы узнать, как эта реализация соответствует вашей машине, вам нужно прочитать документацию по реализации