Новый подход к построению методов межпроцедурного анализа программ

(Работа поддержана грантом РФФИ №96-01-01433)

А.С. Антонов, Вл.В. Воеводин

Введение

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

В данной работе рассматривается новый подход, основанный на анализе свойств графа алгоритма [1,2,3] впервые описанный в [4].

1 Обзор существующих методов межпроцедурного анализа

2 Получение входных и выходных данных подпрограмм с помощью графа алгоритма

Использование графа алгоритма, введенного в [1,2,3], позволяет получить точное описание входных и выходных данных фрагмента программы.

Основная идея этого метода заключается в том, чтобы получить описание нужного множества в пространстве элементов массива средствами анализа пространства итераций программы. Если из всей области срабатывания оператора _J [3] вычесть все области _k из описания графа алгоритма фрагмента по входу A_i (напомним, что точки областей _k являются конечными точками дуг графа алгоритма данного фрагмента), то полученная область _inp будет описывать множество точек пространства итераций, в которых A_i потребляет входные для исследуемого фрагмента данные.

Теперь нужно получить описание области пространства итераций _inp в пространстве элементов массива A. Рассмотрим задачу для входа A_i(P(J)) массива A, где P(J) - это векторная функция, определяющая индексные выражения данного входа. Будем предполагать, что для входа A_i найдена подобласть пространства итераций ⁱ_inp, в каждой точке которой аргументом для входа A_i являются начальные данные. По определению данной области, для любой точки Jⁱ_inp элемент массива A_i(P(J)) нигде в данном фрагменте не вычисляется, а берется из входных данных, т.е. является элементом искомого множества.

Cконструируем вспомогательный фрагмент, содержащий вход A₀ по переменной A:

DO I₁ = l₁, u₁

...

DO I_d = l_d, u_d

... = ... A₀(I₁, I₂, ..., I_d) ...

END DO

...

END DO ,

где d - это размерность переменной A, а l_k, u_k - нижняя и верхняя границы k-го измерения массива A соответственно, k=1,d. Будем считать, что данный фрагмент достижим из каждой точки программы и всегда срабатывает последним - этого всегда можно добиться эквивалентным преобразованием фрагмента.

Возьмем любую точку J области ⁱ_inp. Ясно, что элемент массива A_i(P(J))=A_i(p₁(J),...,p_d(J)) принадлежит искомому множеству и надо найти описание всех подобных точек P(J) в пространстве элементов массива A.

Предположим, что в каждой точке J области ⁱ_inp происходит не использование, а определение элемента A_i(P(J)), т.е. вход A_i будет играть роль выхода. Будем считать областью срабатывания оператора, содержащего A_i, не область _J, а область ⁱ_inp. Область срабатывания входа A₀ определяется только границами циклов вспомогательного фрагмента, так как он безусловно достижим из каждой точки программы.

В таких предположениях решим стандартную задачу построения элементарного графа алгоритма A_iA₀ и найдем область , на которой определены дуги графа алгоритма. Особенность множества заключается в том, что, являясь многогранником в пространстве итераций, он одновременно является и описанием множества входных данных в пространстве элементов массива A для входа A_i.

Аналогичным образом данная задача решается для всех входов, а искомое подмножество входных элементов массива A является объединением областей, полученных при решении данной задачи для каждого отдельного входа.

Использование такого метода позволяет получить точное описание IN и OUT областей подпрограммы. Существование эффективных алгоритмов построения графа алгоритма обеспечивает возможность использования этого метода при анализе реальных программ.

3 Описание входных и выходных данных подпрограммы в терминах фактических параметров

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

Точное определение информационной структуры программ позволяет точно выделять все PARDO циклы расширенного базового класса программ с помощью следующего критерия. Предположим, что исследуется цикл с параметром i₁.

Для того чтобы цикл обладал свойством ParDo, необходимо и достаточно, чтобы для любой тройки (F_k, _k, N_k) графа алгоритма данного цикла включение _k G_k было верным на множестве N_k, где

G_k - область, задаваемая равенством f₁^k = i₁,

f₁^k - первая компонента векторной функции F_k из тройки.

Разработан эффективный алгоритм, позволяющий проверять указанное включение _kG_k, и, следовательно, определять независимость итераций циклов.

5 Пример применения техники межпроцедурного анализа

В качестве примера рассмотрим и проанализируем с использованием описанных методов следующий небольшой фрагмент программы:

SUBROUTINE P(L, M, N)

DIMENSION A(L, M, N), B(L, M, N)

...

DO K = 2, N-1

CALL Q(L, M-2, A(1, 3, K), B(1, 3, K-1))

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₁LQ и 1₂MQ} и BQ: {1₁LQ и 1₂MQ}, а выходные - многогранником AQ: {1₁LQ и 1₂MQ}. Опишем эти области в терминах фактических параметров.

Сначала рассмотрим первый вызов подпрограммы Q. Описания первой размерности формального и фактического параметров совпадают. Поэтому d=2 и ₁-1=₁-1. Построим функцию Г²_pq: ₂-1+(₃-1)M-2-(K-1)M=₂-1. Приведя подобные, получим ₂=(₃-K)M+₂-2. Из описания областей входных и выходных данных для подпрограммы Q следует: 1₂MQ=M-2, а из описания массива А следует, что 1₂M. Очевидно, что если ₃K, то либо ₂<1, либо ₂>M-2.

Значит, ₃=K, следовательно Г²_pq: ₂=₂-2, и входные данные для первого вызова подпрограммы Q представляются следующими многогранниками: A: {1₁L, 3₂M и ₃=K} и (по аналогии) B: {1₁L, 3₂M и ₃=K-1}. Выходные данные представляются многогранником А: {1₁L , 3₂M и ₃=K}.

Аналогично, для второго вызова получим входные данные: A: {1₁L , 3₂M и ₃=K} и А: {1₁L , 3₂M и ₃=K-1}. Выходные данные представляются многогранником А: {1₁L , 3₂M и ₃=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 Заключение