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

UptoLike

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

Рубрика:

Лекция 6

Выявление параллелизма алгоритмов

на основе анализа графов

6.1 Постановка задачи распараллеливания

Рассматриваемые в настоящем и нескольких последующих разделах мето-

ды и алгоритмы актуальны в случае, когда распараллеливаемый алгоритм не

декомпозируется по данным. Если алгоритм характеризуется лишь параллелиз-

мом задач, выявление взаимно независимых операторов, которые могут вы-

полняться параллельно и независимо, оказывается не столь очевидным, как это

имеет место для задач, декомпозируемых по данным.

Параллелизм задач может проявляться различным образом. В частности,

если алгоритм реализуется путем выполнения разных операций над одним и

тем же набором данных (обработка последовательности запросов к информаци-

онным базам данных, вычисления с одновременным применением разных алго-

ритмов расчета и т.п.), говорят о существовании функционального параллелиз-

ма. Функциональная декомпозиция используется, например, для организации

конвейерной обработки данных.

Общий подход к построению параллельных алгоритмов заключается в их

представлении в виде одного или нескольких взаимодействующих процессов.

Процессы – это логически завершенные, преимущественно значительные по

объему работы, на которые можно и целесообразно разбить выполняемый алго-

ритм. Процессы выступают в роли элементарных работ, а структура общего ал-

горитма должна устанавливать правила взаимодействия процессов. При фор-

мировании процессов основная проблема – выделение элементарных работ,

выполнение которых в вычислительной системе подлежит распараллеливанию.

С точки зрения простоты организации параллельных вычислений, конечно,

удобнее делить задачу на «крупные» подзадачи, однако это может оказаться