Параллельное программирование и C++

Сначала вам нужно выбрать между вычислениями с общей памятью и вычислениями без совместного использования. Общая память проще, но не так хорошо масштабируется - вы будете использовать ничего не разделяемое, если вы

а) иметь кластер, а не многопроцессорную систему, или

б) если у вас много процессоров (скажем,> 60) и высокая степень неоднородности памяти

Для разделяемой памяти обычным решением является использование потоков; их легко понять как концепцию и легко использовать в API (но сложно отлаживать).

Для ничего не поделенного вы используете какой-то обмен сообщениями. В высокопроизводительных вычислениях MPI устанавливается как промежуточное ПО для обмена сообщениями.

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

Выкройки:

• Производство / Потребитель

  • Один поток производит данные
  • Один поток потребляет данные

• Циклический параллелизм

  • Если вы можете показать, что каждый цикл независим каждая итерация может выполняться в потоке sperate

• Повторно нарисовать нить

  • Другие потоки работают и обновляют структуры данных, но один поток перерисовывает экран.

• Тема главного события

  • Несколько потоков могут генерировать события
  • Один поток должен обрабатывать события (так как порядок важен)
  • Следует попробовать разделить поток событий / перерисовать поток
    Это (помогает) предотвращает зависание пользовательского интерфейса
    Но может вызвать чрезмерное повторное вытягивание, если не будет сделано осторожно.

• Рабочая группа

  • Набор потоков ожидает задания в очереди.
  • Поток извлекает один рабочий элемент из очереди (ожидает, если ничего не доступно) .
    Тема работает над одним рабочим элементом до завершения
    После завершения поток возвращается в очередь.

Шаблоны параллельного выполнения

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

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

Есть много часто используемых шаблонов, таких как: Map-Reduce, Fork-Join, Pipeline или Parallel Loop ...

Статьи

«Структурированное параллельное программирование с детерминированными шаблонами» - это статья, в которой обсуждаются эти шаблоны. Вы также можете увидеть «MHPM: многомасштабная гибридная модель программирования: гибкая методология распараллеливания», в которой описывается реализация этого подхода на C++ под названием XPU.

Библиотека

XPU - это библиотека C++, основанная на задачах, состоящая из набора повторно используемых шаблонов выполнения. Это позволяет выразить несколько типов параллелизма на нескольких уровнях детализации внутри единой однородной модели программирования. Он прост в использовании и демонстрирует интерес к использованию шаблонов для разработки параллельных программ.

Например, он позволяет выражать:

1. Шаблон параллелизма задач:

   Простой или иерархический шаблон выполнения Fork / Join с некоторыми функциями, такими как как автоматическое обнаружение и защита общих данных.

2. Шаблон параллелизма данных:

   Шаблон параллельного цикла с масштабируемым разделением данных.

3. Шаблон временного параллелизма:

   Схема выполнения конвейера.

У вас есть основы, обеспечивающие параллелизм частям программы. C++ 17 получает много из них (например, параллельные версии foreach, sort, find и friends, map_reduce, map, reduce, prefix_sum ...) см. Расширения C++ для параллелизма

Затем у вас есть такие элементы, как продолжения. Подумайте std :: future, но с продолжением. Есть несколько способов их реализации (теперь у способствовать росту есть хороший, так как у std нет метода next (...) или then (...), но большое преимущество состоит в том, что не нужно ждать это для выполнения следующей задачи

auto fut = async([]( ){..some work...} ).then( [](result_of_prev ){...more work} ).then... ;
fut.wait( );

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

Таким образом, параллелизм, основанный на задачах, действительно хорош. С планировщиком задач вы просто передаете задачи и уходите. У них могут быть методы, такие как семафор, для обратной связи, но это не обязательно. И Строительные блоки Intel Thread, и Библиотека параллельных шаблонов Microsoft имеют для этого средства.

После этого у нас есть шаблон вилки / соединения. Это не подразумевает создание 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 могут работать одновременно. Медленные части находятся в конце графиков / подграфов, где все сходится.

Цель состоит в том, чтобы найти независимые части системы, которые не нуждаются в взаимодействии. Как отмечалось выше, параллельные алгоритмы почти во всех случаях работают медленнее, чем их последовательные аналоги, пока рабочая нагрузка не станет достаточно высокой или размер не станет достаточно большим (при условии, что общение не слишком болтливое). Например сортировка. На четырехъядерном компьютере вы получите примерно в 2,5 раза больше производительности, потому что слияние является болтливым, требует большой синхронизации и не работает со всеми ядрами после первого раунда слияния. На графическом процессоре с очень большим числом N можно использовать менее эффективную сортировку, например Bitonic, и в конечном итоге это будет очень быстро, потому что у вас есть много рабочих для выполнения работы, и каждый тихо делает свое дело.

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

Но при всех типах параллелизма медлительность возникает из-за коммуникации. Уменьшите это.