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

(Работа поддержана грантом РФФИ №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], позволяет получить точное описание входных и выходных данных фрагмента программы.
Основная идея этого метода заключается в том, чтобы получить описание нужного множества в пространстве элементов массива средствами анализа пространства итераций программы. Если из всей области срабатывания оператора W_J [3] вычесть все области D_k из описания графа алгоритма фрагмента по входу A_i (напомним, что точки областей D_k являются конечными точками дуг графа алгоритма данного фрагмента), то полученная область W_inp будет описывать множество точек пространства итераций, в которых A_i потребляет входные для исследуемого фрагмента данные.
Теперь нужно получить описание области пространства итераций W_inp в пространстве элементов массива A. Рассмотрим задачу для входа A_i(P(J)) массива A, где P(J) - это векторная функция, определяющая индексные выражения данного входа. Будем предполагать, что для входа A_i найдена подобласть пространства итераций Wⁱ_inp, в каждой точке которой аргументом для входа A_i являются начальные данные. По определению данной области, для любой точки JÎWⁱ_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 области Wⁱ_inp. Ясно, что элемент массива A_i(P(J))=A_i(p₁(J),...,p_d(J)) принадлежит искомому множеству и надо найти описание всех подобных точек P(J) в пространстве элементов массива A.
Предположим, что в каждой точке J области Wⁱ_inp происходит не использование, а определение элемента A_i(P(J)), т.е. вход A_i будет играть роль выхода. Будем считать областью срабатывания оператора, содержащего A_i, не область W_J, а область Wⁱ_inp. Область срабатывания входа A₀ определяется только границами циклов вспомогательного фрагмента, так как он безусловно достижим из каждой точки программы.
В таких предположениях решим стандартную задачу построения элементарного графа алгоритма A_i®A₀ и найдем область , на которой определены дуги графа алгоритма. Особенность множества заключается в том, что, являясь многогранником в пространстве итераций, он одновременно является и описанием множества входных данных в пространстве элементов массива A для входа A_i.
Аналогичным образом данная задача решается для всех входов, а искомое подмножество входных элементов массива A является объединением областей, полученных при решении данной задачи для каждого отдельного входа.
Использование такого метода позволяет получить точное описание IN и OUT областей подпрограммы. Существование эффективных алгоритмов построения графа алгоритма обеспечивает возможность использования этого метода при анализе реальных программ.

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

Перейдем теперь к решению второй задачи межпроцедурного анализа - описанию входных и выходных данных подпрограммы в терминах фактических параметров. Описываемый здесь метод опирается на [9,16] и требует, чтобы входные и выходные данные подпрограммы уже были описаны в виде системы линейных неравенств.
Пусть в программе есть две подпрограммы P и Q, такие, что:
SUBROUTINE P(...)
DIMENSION A_p(lp₁:up₁,...,lp_p:up_p)
...
CALL Q(...,A_p(op₁,...,op_p),...)
...
END
SUBROUTINE Q(...,A_q,...)
DIMENSION A_q(lq₁:uq₁,...,lq_q:uq_q)
...
END
Пусть элементы массива A_q, представляющие часть входных и выходных данных подпрограммы Q, представлены в виде области W_q, описанной с помощью набора линейных равенств и неравенств. Требуется пересчитать эту область в терминах вырезки из соответствующего фактического параметра-массива A_p.
Запишем условие Г_pq того, что два элемента массивов A_p(y₁,..., y_p) и A_q(j₁,..., j_q) ссылаются на одну и ту же область памяти:

где .
Тогда пересечение трех областей W=W_qÇГ_pqÇ{lp_i£y_i£up_i, i =1,p} неявно задает область W_p массива A_p, соответствующую области W_q массива A_q. Для получения явного описания W_p необходимо получить проекцию (p+q)-мерной области W на p-мерное подпространство, соответствующее массиву A_p. Это можно сделать с помощью исключений Фурье-Моцкина [12,13], если равенство Г_pq линейно. Определение условий его линейности рассматривается дальше.
Если равенство Г_pq нелинейно, то при некоторых условиях можно получить более простое условие. Если массивы A_p и A_q имеют одинаковое число элементов в первых (d-1) размерностях (то есть {up_i - lp_i = uq_i - lq_i, 1 £ i £ d-1}), и {op_i=lp_i, 1 £ i £ d-1}, то добавим в описание области W равенства {y_i - lp_i=j_i - lq_i, 1 £ i £ d-1} и составим частичное уравнение ранга d:

где .
Это уравнение проще, чем Г_pq, и в реальных случаях может оказаться линейным, в то время как полное уравнение таковым не является. Если количество размерностей с одинаковым числом элементов равно q, но меньше p, то в описание области W вместо условия Г^d_pq нужно добавить равенства {y_i=op_i, | i=q+1,p }.
Для того, чтобы получить проекцию (p+q)-мерной области W на p-мерное пространство, необходимо исключить переменные, введенные для описания W_q, из всех равенств и неравенств. Это можно сделать методом Фурье-Моцкина [12,13], если все ограничения, содержащие эти переменные, линейны. Так как в описание W_q входят только линейные ограничения, нелинейность по данным переменным может возникнуть только в равенстве Г_pq (Г^d_pq). Кроме того, для проведения дальнейшего анализа программы важно, чтобы все получающиеся ограничения также были линейными. Поэтому нужно выделить условия на внешние переменные, при которых Г_pq (Г^d_pq) будет линейным по всем переменным.
Для этого берем равенство Г_pq (Г^d_pq), приводим в нем подобные, после чего приравниваем к нулю все нелинейные части. Если из получившихся равенств можно выразить переменные, введенные для описания W_q, через внешние переменные, и подстановка этих выражений в ограничения вместо переменных не входит в противоречие с заданными ограничениями на внешние переменные, то добавим к равенству Г_pq (Г^d_pq) с зануленными нелинейными частями ограничения {lp_i£y_i£up_i|1£i£p} и {lq_i£j_i£uq_i|1£i£q}. После этого исключаем из получившихся линейных ограничений все переменные, кроме внешних, и получаем искомые ограничения на внешние переменные.

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

Циклы, все итерации которых информационно независимы, будем называть PARDO циклами. Независимость итераций сразу говорит о возможности их выполнения в любом порядке, в частности, параллельно. Данный вид параллелизма исключительно важен на практике, прежде всего, в силу простоты использования.
Точное определение информационной структуры программ позволяет точно выделять все PARDO циклы расширенного базового класса программ с помощью следующего критерия. Предположим, что исследуется цикл с параметром i₁.
Для того чтобы цикл обладал свойством ParDo, необходимо и достаточно, чтобы для любой тройки (F_k, D_k, N_k) графа алгоритма данного цикла включение D_k Í G_k было верным на множестве N_k, где
G_k - область, задаваемая равенством f₁^k = i₁,
f₁^k - первая компонента векторной функции F_k из тройки.
Разработан эффективный алгоритм, позволяющий проверять указанное включение D_kÍG_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£j₁£LQ и 1£j₂£MQ} и BQ: {1£j₁£LQ и 1£j₂£MQ}, а выходные - многогранником AQ: {1£j₁£LQ и 1£j₂£MQ}. Опишем эти области в терминах фактических параметров.
Сначала рассмотрим первый вызов подпрограммы Q. Описания первой размерности формального и фактического параметров совпадают. Поэтому d=2 и y₁-1=j₁-1. Построим функцию Г²_pq: y₂-1+(y₃-1)M-2-(K-1)M=j₂-1. Приведя подобные, получим j₂=(y₃-K)M+y₂-2. Из описания областей входных и выходных данных для подпрограммы Q следует: 1£j₂£MQ=M-2, а из описания массива А следует, что 1£y₂£M. Очевидно, что если y₃¹K, то либо j₂<1, либо j₂>M-2.
Значит, y₃=K, следовательно Г²_pq: j₂=y₂-2, и входные данные для первого вызова подпрограммы Q представляются следующими многогранниками: A: {1£y₁£L, 3£y₂£M и y₃=K} и (по аналогии) B: {1£y₁£L, 3£y₂£M и y₃=K-1}. Выходные данные представляются многогранником А: {1£y₁£L , 3£y₂£M и y₃=K}.
Аналогично, для второго вызова получим входные данные: A: {1£y₁£L , 3£y₂£M и y₃=K} и А: {1£y₁£L , 3£y₂£M и y₃=K-1}. Выходные данные представляются многогранником А: {1£y₁£L , 3£y₂£M и y₃=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.