Учебное пособие: Новый подход к построению методов межпроцедурного анализа программ
END DO
...
DO K = 2, N-1
CALL Q(L, M-2, A(1, 3, K), A(1, 3, K-1))
END DO
...
END
SUBROUTINE Q(LQ, MQ, AQ, BQ)
DIMENSION AQ(LQ, MQ), BQ(LQ, MQ)
...
DO J = 1, MQ
DO I = 1, LQ
AQ(I, J) = AQ(I, J) + BQ(I, J)
END DO
END DO
...
END
Для подпрограммы Q входные данные представляются многогранниками:AQ: {1£j1 £LQ и 1£j2 £MQ} и BQ: {1£j1 £LQ и 1£j2 £MQ}, а выходные - многогранником AQ: {1£j1 £LQ и 1£j2 £MQ}. Опишем эти области в терминах фактических параметров.
Сначала рассмотрим первый вызов подпрограммы Q. Описания первой размерности формального и фактического параметров совпадают. Поэтому d=2 и y1 -1=j1 -1. Построим функцию Г2 pq : y2 -1+(y3 -1)M-2-(K-1)M=j2 -1. Приведя подобные, получим j2 =(y3 -K)M+y2 -2. Из описания областей входных и выходных данных для подпрограммы Q следует: 1£j2 £MQ=M-2, а из описания массива А следует, что 1£y2 £M. Очевидно, что если y3 ¹K, то либо j2 <1, либо j2 >M-2.
Значит, y3 =K, следовательно Г2 pq : j2 =y2 -2, и входные данные для первого вызова подпрограммы Qпредставляются следующими многогранниками:A: {1£y1 £L, 3£y2 £M и y3 =K} и (по аналогии) B: {1£y1 £L, 3£y2 £M и y3 =K-1}. Выходные данные представляются многогранником А: {1£y1 £L ,3£y2 £M и y3 =K}.
Аналогично, для второго вызова получим входные данные: A: {1£y1 £L ,3£y2 £M и y3 =K} и А: {1£y1 £L ,3£y2 £M и y3 =K-1}. Выходные данные представляются многогранником А: {1£y1 £L ,3£y2 £M и y3 =K}.
Построив граф алгоритма подпрограммы P, с использованием описанного в предыдущем пункте критерия параллельности получаем, что первый цикл обладает свойством PARDO, а второй - нет.
Таким образом, на данном примере показана вся последовательность действий, осуществляемых при анализе реальных программ. Нужно отметить, что все этапы строго формализованы и (при некоторых предположениях) эффективно реализуемы.
6 Использование методов межпроцедурного анализа при оптимизации программ
В данном разделе мы покажем, как можно использовать изложенную технику для оптимизации программы LIU_FTC для компьютера CRAY Y-MP C90. Программа LIU_FTC представляет из себя моделирование устойчивости плазмы в установках управляемого термоядерного синтеза (General Atomics, San-Diego, USA; данные с действующей установки D III-D). Она состоит из 490 подпрограмм и функций, общим объемом более 37000 строк на языке Фортран. Небольшой фрагмент графа вызовов этой программы приведен на следующем рисунке. Прямоугольники соответствуют подпрограммам, стрелками указывается последовательность вызовов, а скобочки внутри прямоугольников показывают вложенность циклических гнезд, охватывающих вызовы подпрограмм.
Анализ данной программы показал, что единственно доступный для эффективного использования параллелизм находится во внешних циклах подпрограмм QSL, NNL, QSLH и им подобных (эти подпрограммы имеют примерно одинаковую структуру). Сделать такой вывод невозможно без использования эффективных методов межпроцедурного анализа. Оптимизация программы производилась для одного процессора векторно-конвейерного компьютера CRAY Y-MP C90, поэтому использовать этот найденный параллелизм возможно только при условии, что эти циклы станут самыми внутренними в листовых подпрограммах. Это преобразование и было выполнено, после чего были получены следующие результаты.
Время работы 1 итерации исходного варианта составляло 437 с. (для основных поддеревьев графа вызовов: QSL - 257 c., NNL - 63 c., QSLH - 50 с.). После преобразования время работы 1 итерации составило 65.6 с. (QSL - 11.8 c., NNL - 5 c., QSLH - 6.4 с.).
Таким образом, полученное значительное ускорение сложной реальной программы (6.7 раза, а по отдельным подпрограммам до 21.8 раза) показало эффективность нашего подхода к межпроцедурному анализу.
7 Заключение
Описанный в данной работе метод позволяет провести межпроцедурный анализ программ с точностью до отдельных элементов массивов. Использование этого метода совместно с исследованием графа алгоритма позволяет определять параллельную структуру циклов, включающих вызовы других подпрограмм. Эффективная реализация описанных алгоритмов и успешный опыт анализа реальных программ доказывают высокую продуктивность предложенного подхода.