2. О выборе расположения вершин графа алгоритма
При построении графа алгоритма глобально можно встретиться с условными операциями (это разобрано выше), с операторами циклов. Расположение вершин графа алгоритма, как показывает практика, очень важно при наличии вложенности циклов. Если глубина цикла не превосходит 3, то граф алгоритма можно строить в пространстве, размерность которого равна максимальной глубине вложености циклов данного алгоритма, при этом операции тела цикла очевидно имеет смысл располагать в узлах прямоугольной решетки этого пространства с целочисленными координатами, совпадающими со значениями управляющих переменных циклов для соответствующей операции.
Если же глубина вложености циклов превосходит 3, т.е. имеет вид:
Для
от 1 до
операторы
Для
от 1 до
............................
Для
от 1 до
операторы
Для
от 1 до
операторы
Для
от 1 до
Операторы
Конец цикла по
............................
Конец цикла по
то
строить граф алгоритма в пространстве,
размерность которого равна глубине
вложености -
,
очевидно крайне неудобно с учетом
решаемых при помощи этого графа задач.
В этом случае предлагается вообще не
строить целиком граф алгоритма, а
построить его подграфы, которые будут
определяться последовательной фиксацией
значений управляющих переменных всех
внешних циклов -
,...,
,
кроме трех самых внутренних -
,
,
.
Объединение всех построенных графов,
вообще говоря, определяет полный граф
алгоритма, а это значит, что даже не имея
графа алгоритма в явном виде, построив
топологические сортировки его подграфов,
а затем, воспользовавшись алгоритмом
построения топологической сортировки
объединения по топологическим сортировкам
подграфов, можно построить топологическую
сортировку графа алгоритма.
3. Особенности алгоритма решения системы линейных алгебраических уравнений
Пусть необходимо решить систему линейных алгебраических уравнений
,
(*1*)
где
- невырожденная треугольная
-матрица,
методом обратной подстановки. Обозначим
элементы матрицы
,
вектора правой части
и
вектора решения
соответственно. Пусть для определенности
- нижняя треугольная с единичными
диагональными элементами. Тогда (*1*)
конкретизируется в виде:
.
Тогда элементы вектора решения системы вычисляются следующим образом:
(*2*)
Формула
(*2*) не определяет алгоритм вычисления
неизвестных
однозначно, т.к. не определен порядок
суммирования. Рассмотрим два возможных
варианта.
1. Последовательное суммирование по возрастанию индекса . Соответствующий алгоритм имеет вид:
(4.7)
Основная
операция здесь имеет вид
.
При построении графа алгоритма
воспользуемся предложенными выше
рекомендациями о выборе расположения
вершин. В декартовой системе координат
с осями
построим прямоугольную координатную
сетку с шагом 1 и поместим в узлы сетки
при
вершины графа, соответствующие основным
операциям (вида
).
В граф алгоритма при построении включим
вершины, отвечающие вводу входных данных
(рис.12.2).
Рис.12.2.
Ярусы
одной из максимальных параллельных
форм, представленной на рис.12.2, отмечены
пунктирными линиями. Общее число ярусов,
содержащих операции типа
,
равно
.
2. Суммирование по убыванию индекса . Соответствующий алгоритм имеет вид:
(.)
Соответствующий
граф представлен на рис.12.3. Пытаясь
размещать вершины, соответствующие
операциям типа
по ярусам параллельной формы, обнаруживаем,
что теперь в каждом ярусе всегда может
находиться только одна вершина.
Объясняется это тем, что все вершины
графа на рис. */ лежат на одном пути. Этот
путь показан красной пунктирной линией.
Таким образом, общее число ярусов в
графе алгоритма (.), содержащих операции
типа
,
всегда равно
,
что значительно превосходит
ярус в графе алгоритма (4.7).
Рис.12.3.
Полученный результат трудно было ожидать: оба алгоритма предназначены для решения одной задачи, построены на одних и тех же формулах (*2*) и в отношении точных вычислений эквивалентны. Оба алгоритма совершенно одинаковы с точки зрения их реализации на однопроцессорных компьютерах, т.к. требуют выполнения одинакового числа операций умножения и вычитания и одинакового объема памяти. Тем не менее, графы обоих алгоритмов принципиально отличаются друг от друга. Если эти алгоритмы реализовать на параллельной вычислительной системе, имеющей универсальных процессоров, то алгоритм (4.7) можно реализовать за время, пропорциональное , а алгоритм (.) – за время, пропорциональное .
Таким образом, алгоритмы, совершенно одинаковые с точки зрения реализации на «обыкновенных» компьютерах, могут быть принципиально различными с точки зрения реализации на параллельных компьютерах.