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

                                    - 68 -


  3 Анализ алгоритмов с целью выявления параллелизма

   Кардинальным отличием выполнения программы на вычислительной сис-
теме параллельной архитектуры от такового последовательного компьютера
является возможность одновременного выполнения целой группы опера-
ций, друг от друга не зависящих (на последовательной машине в каждый мо-
мент времени выполняется только одна операция, другие могут находиться
только на стадии подготовки). На различных параллельных машинах эти
группы и последовательность их выполнения скорее всего будут разными.
Однако существует (естественное) требование повторяемости результатов
(алгоритм, приводящий к различным конечным результатам даже при оди-
наковых входных данных, вряд ли кому нужен – моделирование статистиче-
ских процессов не рассматриваем).
   В общем случае этап разработки параллельной программы должен предва-
ряться процессом выявления блоков (последовательностей исполняемых
предписаний), могущих быть выполненными независимо друг от друга и то-
чек (моментов) в программе, в которых необходима синхронизация выполне-
ния этих блоков (для ввода или обмена данными). Только для простейших
алгоритмов эта задача может быть выполнена ‘в уме’, в большинстве случае
требуется (достаточно сложный) анализ структуры алгоритма. В некоторых
случаях целесообразно провести эквивалентные преобразования алгоритма
(замена данного алгоритма – или его части – на алгоритм, гарантирующий
получение такого же конечного результата на всех наборах входных данных,
причем желательно без снижения точности расчетов).

 3.1 Представление алгоритма графовой структурой

   Принято и удобно представлять алгоритм в виде графовой структуры.
Граф G стандартно обозначается G=(V,E), где V – множество вершин
(vertex), E – множество дуг (edge), дуга между вершинами i и j обозначается
как e(i,j). В общем случае вершины графа соответствуют некоторым дейст-
виям программы, а дуги – отношениям между этими действиями.
   Простейший граф такого рода описывает информационные зависимости
алгоритма (вершины этого графа соответствуют отдельным операциям ал-
горитма, наличие дуги между вершинами i,j говорит о необходимости при
выполнении операции j наличия аргументов (операндов), выработанных опе-
рацией i; в случае независимости выполнения операций i и j дуга между вер-
шинами отсутствует). Такой граф называют графом алгоритма (вычисли-
тельной моделью ‘операторы - операнды’), [1,3]. Даже при отсутствии ус-
ловных операторов (что маловероятно) число выполненных операций (а сле-
довательно, и общее число вершин графа и, соответственно, число дуг) зави-
сит от размеров входных данных, т.е. граф алгоритма (ГА) является пара-