У вас есть основы, которые связывают параллелизм с частями программы. C ++ 17 получает многие из них (например, параллельные версии foreach, sort, find и friends, map_reduce, map, Reduce, prefix_sum ...). См. Расширения C ++ для параллелизма
Тогда у вас есть такие предметы, как продолжения. Подумайте std :: future , но продолжайте. Есть несколько способов их реализации (у boost есть хороший, так как у std нет метода next (...) или then (...), но большим преимуществом является то, что не нужно ждать, чтобы выполнить следующую задачу
auto fut = async([]( ){..some work...} ).then( [](result_of_prev ){...more work} ).then... ;
fut.wait( );
Отсутствие синхронизации между последующими задачами важно, так как связь между задачами / потоками / ... - это то, что замедляет параллельные программы.
Так что с этим параллелизмом на основе задач действительно приятно. С помощью планировщика задач вы просто пропускаете задачи и уходите. У них могут быть методы, такие как семафор, для обратной связи, но это не обязательно. Оба строительные блоки Intel Thread и Microsoft Parallel Pattern Library имеют средства для этого.
После этого у нас есть шаблон fork / join. Это не подразумевает создание N потоков для каждой задачи. Просто у вас есть эти N, идеально независимые вещи, которые нужно сделать (разветвление), и когда они сделаны, где-то есть точка синхронизации (объединение).
auto semaphore = make_semaphore( num_tasks );
add_task( [&semaphore]( ) {...task1...; semaphore.notify( ); } );
add_task( [&semaphore]( ) {...task2...; semaphore.notify( ); } );
...
add_task( [&semaphore]( ) {...taskN...; semaphore.notify( ); } );
semaphore.wait( );
Сверху вы можете начать видеть шаблон, что это потоковый график. Будущее - (A >> B >> C >> D), а Fork Join - (A | B | C | D). При этом вы можете объединить их, чтобы сформировать график. (A1 >> A2 | B1 >> B2 >> B3 | C1 | D1 >> D2 >> (E1 >> E2 | F1)) Где A1 >> A2 означает, что A1 должен предшествовать A2, а A | B означает, что A и B может работать одновременно. Медленные части находятся в конце графиков / подграфов, где все сходится.
Цель состоит в том, чтобы найти независимые части системы, которым не нужно общаться. Параллельные алгоритмы, как отмечалось выше, почти во всех случаях медленнее, чем их последовательные аналоги, пока рабочая нагрузка не станет достаточно высокой или размер не станет достаточно большим (при условии, что связь не слишком болтливая). Например сортировка. На 4-ядерном компьютере вы получите примерно в 2,5 раза большую или меньшую производительность, потому что слияние является болтливым, требует большой синхронизации и не работает со всеми ядрами после первого раунда слияния. На GPU с очень большим N можно использовать менее эффективную сортировку, такую как Bitonic, и в итоге получается очень быстро, потому что у вас много работников, чтобы справляться с работой, и все спокойно делают свое дело.
Некоторые приемы по сокращению коммуникации включают использование массива для результатов, чтобы каждая задача не пыталась заблокировать объект, чтобы выдвинуть значение. Зачастую уменьшение этих результатов может быть очень быстрым.
Но при всех типах параллелизма медлительность приходит от общения. Уменьшите его.