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

                                        - 75 -


                   или распознавате- нению операторов не-         по тексту    про-
                   лей               посредственно один за        граммы
                                     другим)
  2   Информаци-   Cоответствуют     Информационные связи
      онный граф   экземплярам       между     операторами           То же самое
                   только преобразо- (это и есть ранее рас-
                   вателей           смотренный граф ал-
                                     горитма).
  3   Операционно- Cоответствуют     Cоответствуют переда-        Граф зависит от
      логическая   каждому срабаты- чам управления                входных данных и
      история      ванию (оно необя-                              требует для по-
                   зательно является                              строения отсле-
                   единственным)                                  живания выпол-
                   каждого операто-                               нения всех опера-
                   ра                                             торов
  4   История реа- Соответствуют     Соответствуют переда-
      лизации      каждому срабаты- чам информации                   То же самое
                   ванию оператора-
                   преобразователя

  На самом деле традиционные графы зависимостей устроены излишне
сложно - в каждую вершину входит слишком большое число дуг, к тому же
зависящее от значений внешних переменных. Для таких графов трудно полу-
чить приемлемое аналитическое представление и поэтому с их помощью
трудно решать сложные содержательные задачи.

     В НИВЦ МГУ ряд лет для изучения структуры алгоритмов используют т.н. мини-
  мальные графы зависимостей [1]. Эти графы являются подграфами традиционных гра-
  фов зависимостей, однако принципиально отличаются от последних тем, что в каждую
  вершину такого графа входит лишь конечное число дуг и число их не зависит от значе-
  ний внешних переменных программы. Для минимальных графов зависимостей получено
  их представление в виде конечного набора простейших функций, а оно, в свою очередь,
  позволяет решать широкий спектр задач в области исследования структуры алгорит-
  мов.
     Применение минимальных графов зависимостей позволило решить задачи (включая
  задачи, решение тесно связано с минимальными графами), [1]:

  • Определение параллельной структуры алгоритмов и программ на уровне отдельных
    операций.
  • Расчленение алгоритмов на крупные параллельно исполняемые фрагменты.
  • Восстановление по программе исходных математических формул.
  • Оптимизация использования внешней памяти.
  • Оценка параллельной сложности алгоритмов и программ.
  • Быстрое вычисление градиента сложных функций.
  • Исследование влияния ошибок округления.
  • Построение математических моделей систолических массивов.
  • Разработка портабельных библиотек программ.