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

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

Введение

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

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

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

Одним из первых методов разрешения проблемы межпроцедурного анализа была предложена подстановка тела подпрограммы на место вызова (inline expansion [14]), но она сильно затруднена, если в графе вызовов есть контуры, что приводит к значительному увеличению размера кода и времени анализа. В известных обзорах [5,15] большое внимание уделялось методам межпроцедурного анализа без учета индексных переменных. Но такой анализ является весьма грубым и недостаточным для реальных программ, поскольку в большинстве случаев необходима информация о существовании зависимости между ссылками на отдельные элементы массивов.

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

В большинстве работ, посвященных межпроцедурному анализу, входные и выходные данные аппроксимируются вырезками массивов, используемыми или изменяемыми в анализируемой подпрограмме. Следуя [9], будем называть такие области READ и WRITE областями. Все методы описания READ и WRITE областей можно разделить на два класса: неточные и точные методы. Неточные методы проще, но, в отличие от точных, описывают только некоторую аппроксимацию необходимой области. Точные же методы могут потребовать много памяти и времени для анализа программ. В некоторых случаях используются комбинированные методы, например, приближенное описание объединения точно описанных областей.

Среди неточных методов получения READ и WRITE областей можно отметить ограниченные регулярные секции (restricted regular sections [8]), описания с помощью триплетов (bounded regular sections [11]), простые секции (simple sections [6]), описание в виде минимальной выпуклой оболочки (convex hull) [9,17]. Из точных методов можно указать подход Бурке-Сайтрона [7] и построение совокупного образа (merged image) [16].

Однако знания READ и WRITE областей недостаточно для полноценного анализа, так как READ области могут содержать данные, вычисленные ранее в исследуемой подпрограмме, а, следовательно, они не будут представлять входных данных анализируемой процедуры. WRITE области могут содержать данные, которые не потребуются нигде в дальнейшем тексте программы, что также не соответствует выходным данным подпрограммы. Для более точного анализа вводятся IN и OUT области, которые представляют именно входные и выходные данные подпрограммы, то есть данные, необходимые для выполнения подпрограммы, и данные, вычисляемые в исследуемой подпрограмме и используемые где-либо далее. Метод получения IN и OUT областей из READ и WRITE областей подробно описан в [9,10].

Методы описания входных и выходных данных подпрограммы в терминах фактических параметров описаны в работах [9,16].

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

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

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

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

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

DO I1 = l1, u1

...

DO Id = ld, ud

... = ... A0(I1, I2, ..., Id) ...

END DO

...

END DO ,

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

Возьмем любую точку J области Wiinp. Ясно, что элемент массива Ai(P(J))=Ai(p1(J),...,pd(J)) принадлежит искомому множеству и надо найти описание всех подобных точек P(J) в пространстве элементов массива A.

Предположим, что в каждой точке J области Wiinp происходит не использование, а определение элемента Ai(P(J)), т.е. вход Ai будет играть роль выхода. Будем считать областью срабатывания оператора, содержащего Ai, не область WJ, а область Wiinp. Область срабатывания входа A0 определяется только границами циклов вспомогательного фрагмента, так как он безусловно достижим из каждой точки программы.

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

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

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

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

Перейдем теперь к решению второй задачи межпроцедурного анализа - описанию входных и выходных данных подпрограммы в терминах фактических параметров. Описываемый здесь метод опирается на [9,16] и требует, чтобы входные и выходные данные подпрограммы уже были описаны в виде системы линейных неравенств.

Пусть в программе есть две подпрограммы P и Q, такие, что:

SUBROUTINE P(...)

DIMENSION Ap(lp1:up1,...,lpp:upp)

...

CALL Q(...,Ap(op1,...,opp),...)

...

END

SUBROUTINE Q(...,Aq,...)

DIMENSION Aq(lq1:uq1,...,lqq:uqq)

...

END

Пусть элементы массива Aq, представляющие часть входных и выходных данных подпрограммы Q, представлены в виде области Wq, описанной с помощью набора линейных равенств и неравенств. Требуется пересчитать эту область в терминах вырезки из соответствующего фактического параметра-массива Ap.

Запишем условие Гpq того, что два элемента массивов Ap(y1,..., yp) и Aq(j1,..., jq) ссылаются на одну и ту же область памяти:

где .

Тогда пересечение трех областей W=WqЗГpqЗ{lpiЈyiЈupi, i =1,p} неявно задает область Wp массива Ap, соответствующую области Wq массива Aq. Для получения явного описания Wp необходимо получить проекцию (p+q)-мерной области W на p-мерное подпространство, соответствующее массиву Ap. Это можно сделать с помощью исключений Фурье-Моцкина [12,13], если равенство Гpq линейно. Определение условий его линейности рассматривается дальше.

Если равенство Гpq нелинейно, то при некоторых условиях можно получить более простое условие. Если массивы Ap и Aq имеют одинаковое число элементов в первых (d-1) размерностях (то есть {upi - lpi = uqi - lqi, 1 Ј i Ј d-1}), и {opi=lpi, 1 Ј i Ј d-1}, то добавим в описание области W равенства {yi - lpi=ji - lqi, 1 Ј i Ј d-1} и составим частичное уравнение ранга d:

где .

Это уравнение проще, чем Гpq, и в реальных случаях может оказаться линейным, в то время как полное уравнение таковым не является. Если количество размерностей с одинаковым числом элементов равно q, но меньше p, то в описание области W вместо условия Гdpq нужно добавить равенства {yi=opi, | i=q+1,p }.

Для того, чтобы получить проекцию (p+q)-мерной области W на p-мерное пространство, необходимо исключить переменные, введенные для описания Wq, из всех равенств и неравенств. Это можно сделать методом Фурье-Моцкина [12,13], если все ограничения, содержащие эти переменные, линейны. Так как в описание Wq входят только линейные ограничения, нелинейность по данным переменным может возникнуть только в равенстве Гpq (Гdpq). Кроме того, для проведения дальнейшего анализа программы важно, чтобы все получающиеся ограничения также были линейными. Поэтому нужно выделить условия на внешние переменные, при которых Гpq (Гdpq) будет линейным по всем переменным.

Для этого берем равенство Гpq (Гdpq), приводим в нем подобные, после чего приравниваем к нулю все нелинейные части. Если из получившихся равенств можно выразить переменные, введенные для описания Wq, через внешние переменные, и подстановка этих выражений в ограничения вместо переменных не входит в противоречие с заданными ограничениями на внешние переменные, то добавим к равенству Гpq (Гdpq) с зануленными нелинейными частями ограничения {lpiЈyiЈupi|1ЈiЈp} и {lqiЈjiЈuqi|1ЈiЈq}. После этого исключаем из получившихся линейных ограничений все переменные, кроме внешних, и получаем искомые ограничения на внешние переменные.

4 Определение параллелизма по графу алгоритма

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

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

Для того чтобы цикл обладал свойством ParDo, необходимо и достаточно, чтобы для любой тройки (Fk, Dk, Nk) графа алгоритма данного цикла включение Dk Н Gk было верным на множестве Nk, где

Gk - область, задаваемая равенством f1k = i1,

f1k - первая компонента векторной функции Fk из тройки.

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

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Ј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. Построим функцию Г2pq: 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, следовательно Г2pq: 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 Заключение

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

Авторы выражают искреннюю благодарность В.М.Репину, П.А.Церетели и А.Н.Андрееву за помощь при подготовке данной работы.

Литература

[1] В.В. Воеводин. Математические основы параллельных вычислений. М., 1991.

[2] Вл.В. Воеводин. Статический анализ и вопросы эффективной реализации программ. Вычислительные процессы и системы (Под. ред. Г.И. Марчука). М., 1992. N 9. С. 249-301.

[3] Вл.В. Воеводин. Теория и практика исследования параллелизма последовательных программ. Программирование. 1992. N 3. С. 38-53.

[4] Вл.В. Воеводин. Описание входных и выходных данных фрагментов программ. Вестник Московского университета. Серия 15. 1997. N 1. С. 41-44.

[5] В.А. Евстигнеев, В.А. Серебряков. Методы межпроцедурного анализа (обзор). Программирование. 1992. N 3. С. 4-15.

[6] V. Balasundaram, K. Kennedy. A Technique for Summarizing Data Access and Its Use in Parallelism Enhancing Transformation. In Proceedings of the 1989 ACM SIGPLAN Conference on Programming Language Design and Implementation. Vol. 24. N 7. pp. 41-53. Portland, Orgen. June 1989.

[7] M. Burke, R. Cytron. Interprocedural Dependence Analysis and Parallelisation. ACM SIGPLAN'86 Symposium on Compiler Construction. Vol. 21. N 7. pp. 162-175. June 1986.

[8] D. Callahan, K. Kennedy. Analysis of Interprocedural Side Effects in a Parallel Programming Environment. Journal of Parallel and Distributed Computing. Vol. 5. pp. 517-550. Oktober 1988.

[9] B. Creusillet, F. Irigoin. Interprocedural Array Region Analyses. Eighth International Workshop on Languages and Compilers for Parallel Computing. pp.4-1 to 4-15. Colombus (Ohio), USA. August 1995.

[10] B. Creusillet. IN and OUT Array Region Analyses. Fifth Workshop on Compilers for Parallel Computers. Malaga, Spain. June 1995.

[11] P. Havlak, K. Kennedy. An Implementation of Interprocedural Bounded Regular Section Analysis. IEEE Transactions on Parallel and Distributed Systems. Vol. 2. N 3. pp. 350-360. July 1991.

[12] D. E. Maydan, J. L. Hennessy, M. S. Lam. Efficient and Exact Data Dependence Analysis. Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation.

[13] W. Pugh. A Practical Algorithm for Exact Array Dependence Analysis Communications of the ACM. Vol. 35, N 8. pp. 102-114. August 1992.

[14] R. W. Scheifler. An Analysis of Inline Substitution for a Structured Programming Language. Communications of the ACM. Vol. 20. N 9. September 1977.

[15] D. A. Schouten. An Overview of Interprocedural Analyses Techniques for High Performance Parallelizing Compilers. Univ. of Illinois at Urbana-Champaign. CSRD Tech. Rep. 1005. May 1990.

[16] P. Tang. Exect Side Effects for Interprocedural Dependence Analysis. Australian National University. Tech. Rep. TR-CS-92-15. November 1992.

[17] R. Triolet, F. Irigoin, P. Feautrier. Direct Parallelism of Call Statements. In Proceedings of the ACM SIGPLAN'86 Symposium on Compiler Construction. SIGPLAN Notices. Vol. 21. N 7. pp. 176-185. June 1986.