Новый подход к построению методов межпроцедурного анализа программ (стр. 2 из 2)
где
.Это уравнение проще, чем Г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 ParallelismEnhancing Transformation. In Proceedings of the 1989 ACM SIGPLAN Conference on Programming LanguageDesign 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 ProgrammingEnvironment. 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 ParallelComputing. 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 LanguageDesign and Implementation.
[13] W. Pugh.A Practical Algorithm for Exact Array Dependence AnalysisCommunications of the ACM. Vol. 35, N 8. pp. 102-114. August 1992.
[14] R. W. Scheifler. An Analysis of Inline Substitution for a Structured ProgrammingLanguage. Communications of the ACM. Vol. 20. N 9. September 1977.
[15] D. A. Schouten. An Overview of Interprocedural Analyses Techniques forHigh 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.