Новыйподход к построению методов межпроцедурного анализа программ
(Работа поддержана грантом РФФИ№96-01-01433)
А.С.Антонов,Вл.В.ВоеводинВведение
Необходимость выполнения межпроцедурного анализа очень частовозникает на практике, в частности, прианализе параллельных свойств программ. Можно привести множество примеров задач,решаемых с использованием техники межпроцедурного анализа: определениенезависимости вхождений в тело подпрограммы параметров и глобальных переменных,распараллеливание циклов, содержащих вызовы подпрограмм, определениенеобходимых пересылок данных для вызова распределяемой подпрограммы прииспользовании компьютеров с распределенной памятью, поддержка корректностиданных в кэш-памяти многопроцессорных систем и многие другие. Безмежпроцедурного анализа придется предположить, что все фактические параметры ивнешние переменные как используются, так и переопределяются в вызываемойподпрограмме, поэтому многие полезные свойства программы не будут использованы.
В данной работе рассматривается новый подход, основанный наанализе свойств графа алгоритма [1,2,3] впервые описанный в [4].
1 Обзор существующих методовмежпроцедурного анализа
Одним из первых методов разрешения проблемы межпроцедурногоанализа была предложена подстановка тела подпрограммы на место вызова (inlineexpansion [14]), но она сильно затруднена, если в графе вызовов есть контуры,что приводит к значительному увеличению размера кода и времени анализа. Визвестных обзорах [5,15] большое внимание уделялось методам межпроцедурногоанализа без учета индексных переменных. Но такой анализ является весьма грубыми недостаточным для реальных программ, поскольку в большинстве случаевнеобходима информация о существовании зависимости между ссылками на отдельныеэлементы массивов.
Последующее развитие методов межпроцедурного анализа шло подвум направлениям: с одной стороны, уточнение методов нахождения входных и выходных данных подпрограмм, а с другой — описание найденных данных втерминах фактических параметров (обратная подстановка).
В большинстве работ, посвященных межпроцедурному анализу,входные и выходные данные аппроксимируются вырезками массивов, используемымиили изменяемыми в анализируемой подпрограмме. Следуя [9], будем называть такиеобласти READ и WRITE областями. Все методы описания READ и WRITE областей можноразделить на два класса: неточные и точные методы. Неточные методы проще, но, вотличие от точных, описывают только некоторую аппроксимацию необходимойобласти. Точные же методы могут потребовать много памяти и времени для анализа программ.В некоторых случаях используются комбинированные методы, например, приближенноеописание объединения точно описанных областей.
Среди неточных методов получения READ и WRITE областей можноотметить ограниченные регулярные секции (restricted regular sections [8]),описания с помощью триплетов (bounded regular sections [11]), простые секции(simple sections [6]), описание в виде минимальной выпуклой оболочки (convexhull) [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, то либо j2M-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-MPC90. Программа 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.8c., 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 DataAccess and Its Use in Parallelism Enhancing Transformation. In Proceedings of the 1989 ACM SIGPLAN Conference on Programming Language Design and Implementation. Vol. 24. N7. pp. 41-53. Portland, Orgen. June 1989.
[7] M. Burke, R. Cytron. Interprocedural Dependence Analysisand Parallelisation. ACMSIGPLAN'86 Symposium on Compiler Construction. Vol. 21. N 7. pp. 162-175. June 1986.
[8] D. Callahan, K. Kennedy. Analysis of Interprocedural SideEffects 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 onLanguages 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 forParallel Computers. Malaga, Spain. June 1995.
[11] P. Havlak, K. Kennedy. An Implementation of InterproceduralBounded 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 DataDependence Analysis. Proceedingsof the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation.
[13] W. Pugh. A Practical Algorithm for Exact ArrayDependence Analysis Communicationsof the ACM. Vol. 35, N 8. pp. 102-114. August 1992.
[14] R. W. Scheifler. An Analysis of Inline Substitutionfor a Structured Programming Language.Communicationsof the ACM. Vol. 20. N 9. September 1977.
[15] D. A. Schouten. An Overview of InterproceduralAnalyses Techniques for High Performance Parallelizing Compilers. Univ. of Illinois atUrbana-Champaign. CSRD Tech. Rep. 1005. May 1990.
[16] P. Tang. Exect Side Effects forInterprocedural 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'86Symposium on Compiler Construction. SIGPLAN Notices. Vol. 21. N 7. pp. 176-185. June 1986.