Лекции по параллельным вычислениям. Гергель В.П - 67 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

67
подзадачи обладают высокой степенью информационной взаимозависимости.
Если число подзадач меньше числа доступных процессоров, выполняют деком-
позицию. Масштабирование облегчается, если правила агрегации и декомпози-
ции параметрически зависят от числа процессоров.
Распределение подзадач между процессорами очевидно, если количество
областей данных совпадает с числом имеющихся процессоров, а топология сети
передачи данных – полный граф (все процессоры связаны между собой). Если
это не так, подзадачи, имеющие информационные взаимодействия, целесооб-
разно размещать на процессорах, между которыми существуют прямые линии
передачи данных. Требование минимизации информационных обменов между
процессорами может вступить в противоречие с условием равномерной загруз-
ки. Решение вопросов балансировки вычислительной нагрузки значительно ус-
ложняется, если схема вычислений изменяется в ходе решения задачи. При
этом необходимо перераспределение базовых подзадач между процессорами
(динамическая балансировка) в ходе выполнения программы.
Центральной проблемой, как уже неоднократно указывалось выше, являет-
ся выделение базовых подзадач на этапе декомпозиции. Эта проблема имеет
много аспектов, в следующем разделе кратко рассматриваются лишь некоторые
важнейшие.
Описанная выше схема этапов может использоваться также и для построе-
ния параллельного алгоритма, который характеризуется параллелизмом задач.
При этом содержание этапов может существенно отличаться. В частности, цен-
тральной проблемой в этом случае является выявление взаимно независимых
операторов, которые могут выполняться параллельно и независимо. Эти вопро-
сы будут обсуждаться в следующей лекции.
5.4 Декомпозиция в задачах с параллелизмом по данным
Способ разделения вычислений на независимые части зависит от того, на-
сколько полно решаемая задача обладает свойством декомпозируемости по
данным, определяемого местом алгоритма в классификации, приведенной в

Страницы