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

                                      - 71 -


                                                       ставляет         ярусно-
                                                       параллельную      форму
                                                       (ЯПФ) алгоритма, при-
                                                       чем количество ярусов
                                                       определяет длину кри-
                                                       тического пути.
                                                         В ярусы собираются
                                                       операторы, требующие
                                                       для своего выполнения
                                                       значений (операндов),
                                                       которые    вычисляются
                                                       только на предыдущих
                                                       ярусах (всего на рис.20
                                                       выделено 6 ярусов); т.о.
                                                       параллельное выполне-
                                                       ние данного алгоритма
                                                       требует последователь-
                                                       ного 6-разового выпол-
                                                       нения блоков парал-
                                                       лельных операций (в
                                                       каждом из которых за-
                                                       пускаются     4,1,1,1,2,2
                                                       независимых процесса
Рисунок 20 — Граф алгоритма (зависимость ‘операции - соответственно, причем
  операнды’) для нахождения корней полного квадратного
  уравнения с группировкой операций по ярусам          ярусы 2,3,4 вырождают-
                                                       ся в последовательное
                                                       выполнение алгоритма).
  Граф рис.20 позволяет уже сделать некие конкретные выводы о альтерна-
тивах распараллеливания. Заметим, что ярус 1 перегружен операциями (3
умножения и 1 изменение знака), часть из них (кроме операции 2) можно пе-
ренести на более нижние ярусы (варианты: операцию 4 на ярус 2, операцию 3
на ярусы 2,3 или 4, операцию 1 на ярусы 2,3,4 или 5); конкретный вариант
должен выбираться исходя из дополнительных данных (например, время вы-
полнения конкретных операций, число задействованных вычислительных
модулей, минимизация времени обменов данными между модулями).
  Выявление этих ярусов представляет собой один из уровней анализа
внутренней структуры алгоритма. Нижеприведена упрощенная последова-
тельность действий по выявлению могущих выполняться параллельно ярусов
графа алгоритма (вдумчивый читатель самостоятельно произведет необходи-
мые уточнения и оптимизацию):