Модель параллельного алгоритма разрабатывается путем рассмотрения стратегии разделения данных и метода обработки и применения подходящей стратегии для сокращения взаимодействий. В этой главе мы обсудим следующие модели параллельных алгоритмов:
- Параллельная модель данных
- Модель графа задач
- Модель рабочего бассейна
- Мастер раб модель
- Производитель потребитель или модель трубопровода
- Гибридная модель
Параллель данных
В параллельной модели данных задачи назначаются процессам, и каждая задача выполняет аналогичные типы операций с различными данными. Параллелизм данных является следствием отдельных операций, которые применяются к нескольким элементам данных.
Параллельная с данными модель может быть применена к общим адресным пространствам и парадигмам передачи сообщений. В модели, параллельной данным, накладные расходы на взаимодействие можно уменьшить, выбрав разложение, сохраняющее локальность, с помощью оптимизированных процедур коллективного взаимодействия или путем наложения вычислений и взаимодействия.
Основная характеристика проблем параллельной модели данных заключается в том, что интенсивность параллелизма данных увеличивается с увеличением размера проблемы, что, в свою очередь, позволяет использовать больше процессов для решения более крупных задач.
Пример — плотное матричное умножение.
Модель графа задач
В модели графа задач параллелизм выражается графом задач . Граф задач может быть тривиальным или нетривиальным. В этой модели корреляция между задачами используется для продвижения местности или минимизации затрат на взаимодействие. Эта модель применяется для решения проблем, при которых количество данных, связанных с задачами, огромно по сравнению с количеством вычислений, связанных с ними. Задачи назначены, чтобы помочь улучшить стоимость перемещения данных между задачами.
Примеры — параллельная быстрая сортировка, разреженная матричная факторизация и параллельные алгоритмы, полученные с помощью подхода «разделяй и властвуй».
Здесь задачи делятся на элементарные задачи и реализуются в виде графика. Каждая задача — это независимая единица работы, которая зависит от одной или нескольких предыдущих задач. После завершения задачи выходные данные предыдущей задачи передаются зависимой задаче. Задача с предшествующей задачей начинает выполняться только после завершения всей предшествующей задачи. Окончательный вывод графика получается, когда завершается последняя зависимая задача (задача 6 на рисунке выше).
Модель рабочего бассейна
В модели рабочего пула задачи динамически назначаются процессам для балансировки нагрузки. Поэтому любой процесс может потенциально выполнить любую задачу. Эта модель используется, когда количество данных, связанных с задачами, сравнительно меньше, чем вычисление, связанное с задачами.
Нет желаемого предварительного назначения задач на процессы. Назначение задач является централизованным или децентрализованным. Указатели на задачи сохраняются в физически общем списке, в очереди приоритетов, или в хэш-таблице или дереве, или они могут быть сохранены в физически распределенной структуре данных.
Задача может быть доступна в начале или может быть сгенерирована динамически. Если задача генерируется динамически и выполняется децентрализованное назначение задачи, то требуется алгоритм обнаружения завершения, чтобы все процессы могли фактически обнаружить завершение всей программы и перестать искать другие задачи.
Пример — поиск параллельного дерева
Мастер-Раб Модель
В модели «ведущий-ведомый» один или несколько мастер-процессов генерируют задачу и распределяют ее по подчиненным процессам. Задачи могут быть распределены заранее, если —
- мастер может оценить объем заданий, или
- случайное назначение может удовлетворительно справиться с балансировкой нагрузки, или
- рабам назначают меньшие части задачи в разное время.
Эта модель в целом одинаково подходит для парадигм общего адресного пространства или передачи сообщений, поскольку взаимодействие, естественно, происходит двумя способами.
В некоторых случаях задача может потребоваться выполнить поэтапно, и задача на каждом этапе должна быть завершена до того, как задача будет создана на следующих этапах. Модель «ведущий-ведомый» может быть обобщена на иерархическую или многоуровневую модель «ведущий-ведомый», в которой мастер верхнего уровня передает большую часть задач ведущему устройству второго уровня, который дополнительно подразделяет задачи между своими собственными ведомыми устройствами и может выполнять часть самой задачи.
Меры предосторожности при использовании модели «ведущий-ведомый»
Следует позаботиться о том, чтобы хозяин не стал точкой затора. Это может произойти, если задачи слишком малы или рабочие работают сравнительно быстро.
Задачи должны выбираться таким образом, чтобы стоимость выполнения задачи доминировала над стоимостью связи и стоимостью синхронизации.
Асинхронное взаимодействие может помочь перекрывать взаимодействие и вычисления, связанные с генерацией работы мастером.
Модель трубопровода
Он также известен как модель производитель-потребитель . Здесь набор данных передается через серию процессов, каждый из которых выполняет определенную задачу. Здесь поступление новых данных генерирует выполнение новой задачи процессом в очереди. Процессы могут образовывать очередь в форме линейных или многомерных массивов, деревьев или общих графов с циклами или без них.
Эта модель представляет собой цепочку производителей и потребителей. Каждый процесс в очереди может рассматриваться как потребитель последовательности элементов данных для процесса, предшествующего ему в очереди, и как производитель данных для процесса, следующего за ним в очереди. Очередь не обязательно должна быть линейной цепочкой; это может быть ориентированный граф. Наиболее распространенным методом минимизации взаимодействия, применимым к этой модели, является перекрывающееся взаимодействие с вычислениями.
Пример — алгоритм параллельной LU-факторизации.
Гибридные модели
Гибридная модель алгоритма требуется, когда для решения проблемы может потребоваться более одной модели.
Гибридная модель может состоять из нескольких моделей, применяемых иерархически, или нескольких моделей, применяемых последовательно к различным фазам параллельного алгоритма.
Пример — параллельная быстрая сортировка