Параллельные вычисления. Баканов В.М. - 74 стр.

                                                    - 74 -


     ярус 1: ( a1 × a 2 ) ( a 3 × a 4 ) ( a 5 × a6 ) ( a7 × a 8 )
     ярус 2: ( a1 a 2 ) × ( a 3 a 4 ) ( a 5 a6 ) × ( a7 a 8 )
     ярус 3: ( a1 a 2 a 3 a 4 ) × ( a 5 a6 a7 a 8 )

  Высота такой схемы равна 3, ширина – те же самые 4. Для произвольного n
(в этом случае высота равна ceil( log 2 n ) такой алгоритм реализуется на
ceil(n/2) процессорах (но загрузка процессоров бинарно уменьшается от яру-
са к ярусу). Процесс сдваивания (известен и применяется также процесс ре-
куррентного сдваивания) позволяет проектировать алгоритмы минимальной
высоты для любой ассоциативной (сочетательной) операции, но ширина по-
лученного алгоритма чрезмерна (на первых ярусах).
  Для рассмотренных алгоритмов размер гранулы (определенный трудоем-
костью выполнения операций высокоуровневого языка программирования)
столь мизерен, что его применение оправдано только для SMP-систем (мно-
гопроцессорных вычислительных систем с общей памятью); эффективное
распараллеливание в МВС с локальной памятью требуют использование гра-
нул параллелизма намного большего размера.
  Подобный подход к проектированию параллельных схем выполнения ал-
горитмов является изящным, однако абстрагирование от числа процессоров
и параметров коммуникационной среды конкретной вычислительной систе-
мы делает его практическую применимость весьма ограниченной (напр., для
рассмотренного примера при n ≈ 10 3 на первом ярусе необходимо задейство-
вать 500 процессоров, а на последнем – всего 2!). Подход, основанный на иг-
норировании архитектуры МВС и количественных параметров ее компо-
нентов, получил название концепции неограниченного параллелизма.
  При операторном подходе в любой программе различают два типа дейст-
вия – преобразователи       (осуществляют переработку информации, напр.,
операторы присваивания) и распознаватели (определяют последовательность
срабатывания преобразователей при работе программы, напр., условные опе-
раторы, переключатели и др.). Всего имеются четыре основные (традицион-
ные) модели (см. табл.5) представления алгоритмов в виде графов (*):

    Таблица 5 — Основные модели графового представления алгоритмов.

    №№   Название   Вершины графа                          Дуги графа           Примечание
     1 Граф управ- Соответствуют                     Передача управления     Граф не зависит
       ления       экземплярам опе-                  (наличие направленной   от входных дан-
                   раторов-                          дуги между вершинами    ных и создается
                   преобразователей                  соответствует выпол-    непосредственно

*
    Ершов А.П. Современное состояние теории схем управления. // Проблемы кибернетики,
     -М.: 1973, № 27, c.87 ÷ 110.