47747 (597354), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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 Заключение

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

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

Литература

[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.

Характеристики

Список файлов книги