Граф, представляющий ярусно-параллельную форму (ЯПФ) алгоритма.

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

Количество ярусов определяет длину критического пути.

Последовательность действий по выявлению ярусов графа алгоритма, способных выполняться параллельно:

1. Задать список вершин, зависящих  только от входных данных; занести его в список 1.
2. Найти вершины, зависимые по дугам от вершин, входящих только в список 1, и занести их в список 2.
3. Если список 2 не пуст, скопировать его в список 1 и перейти к пункту 2; иначе – завершить работу.

Время tj выполнения операций каждого яруса определяется временем исполнения наиболее длительной операции из расположенных на данном ярусе (tj = max(tji), где j – номер яруса, i – номер оператора в данном ярусе).

При планировании выполнения параллельной программы необходимо учитывать ограничение на число процессоров       (P ≤ Pmax), поэтому может быть выгодно объединение двух или более быстро выполняемых операторов для последовательного исполнения в рамках одного яруса.

Распараллеливание на уровне отдельных операторов в реальности почти не используется.

Рациональнее рассматривать целые группы операторов, выполняющихся последовательно и не требующих обмена данными с другими группами яруса. Выявить такие гранулы (или зерна) параллелизма (вручную или автоматически) очень непросто (NP-полная задача).

Одним из эмпирических методов проектирования алгоритмов наименьшей высоты (с минимальным числом ярусов) является процесс сдваивания.

Концепция неограниченного параллелизма.

Абстрагирование от числа процессоров и параметров коммуникационной среды конкретной вычислительной системы ограничивает практическую применимость алгоритма: для рассмотренного примера при n ≈1000 на первом ярусе необходимо будет задействовать 500 процессоров, на последнем – всего 2 (!).

Подход, основанный на игнорировании архитектуры МВС и ее количественных параметров, получил название концепции неограниченного параллелизма.

Такой подход, как правило, приводит к неравномерности загрузки процессоров и снижает эффективность использования МВС (не решает проблему балансировки загрузки процессоров).

eTXT