Параллельный алгоритм - модели

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

• Параллельная модель данных
• Модель графа задач
• Модель рабочего бассейна
• Модель главного раба
• Производитель потребитель или модель трубопровода
• Гибридная модель

Параллельные данные

В параллельной модели данных задачи назначаются процессам, и каждая задача выполняет аналогичные типы операций с разными данными. Data parallelism является следствием отдельных операций, применяемых к нескольким элементам данных.

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

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

Example - Плотное матричное умножение.

Модель графа задач

В модели графа задач параллелизм выражается task graph. Граф задач может быть тривиальным или нетривиальным. В этой модели корреляция между задачами используется для продвижения локальности или минимизации затрат на взаимодействие. Эта модель применяется для решения проблем, в которых количество данных, связанных с задачами, огромно по сравнению с количеством связанных с ними вычислений. Задачи назначаются, чтобы помочь снизить стоимость перемещения данных между задачами.

Examples - Параллельная быстрая сортировка, факторизация разреженной матрицы и параллельные алгоритмы, полученные с помощью подхода «разделяй и властвуй».

Здесь проблемы разделены на атомарные задачи и реализованы в виде графа. Каждая задача - это независимая единица задания, которая зависит от одной или нескольких предшествующих задач. После завершения задачи вывод предшествующей задачи передается зависимой задаче. Задача с предшествующей задачей начинает выполнение только после завершения всей предшествующей задачи. Окончательный вывод графа получается, когда последняя зависимая задача завершена (Задача 6 на рисунке выше).

Модель рабочего бассейна

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

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

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

Example - Параллельный поиск по дереву

Модель Мастер-Раб

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

• мастер может оценить объем задач, или
• случайное назначение может удовлетворительно сбалансировать нагрузку, или
• ведомым в разное время назначаются более мелкие задачи.

Эта модель в целом одинаково подходит для shared-address-space или же message-passing paradigms, поскольку взаимодействие естественно двухстороннее.

В некоторых случаях задача может быть выполнена поэтапно, и задача на каждой фазе должна быть завершена до того, как можно будет сгенерировать задачу на следующих этапах. Модель ведущий-ведомый можно обобщить наhierarchical или же multi-level master-slave model в котором мастер верхнего уровня передает большую часть задач мастеру второго уровня, который далее подразделяет задачи среди своих собственных подчиненных устройств и может выполнять часть самой задачи.

Меры предосторожности при использовании модели ведущий-ведомый

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

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

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

Модель трубопровода

Он также известен как producer-consumer model. Здесь набор данных передается через серию процессов, каждый из которых выполняет определенную задачу. Здесь поступление новых данных порождает выполнение новой задачи процессом в очереди. Процессы могут формировать очередь в форме линейных или многомерных массивов, деревьев или общих графов с циклами или без них.

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

Example - Параллельный алгоритм факторизации LU.

Гибридные модели

Модель гибридного алгоритма требуется, когда для решения проблемы может потребоваться более одной модели.

Гибридная модель может состоять либо из нескольких моделей, применяемых иерархически, либо из нескольких моделей, применяемых последовательно к различным этапам параллельного алгоритма.

Example - Параллельная быстрая сортировка