Новий підхід до побудови методів межпроцедурного аналізу програм
(Робота підтримана грантом РФФМ № 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 i inp, в кожній точці якої аргументом для входу A i є початкові дані. За визначенням даної області, для будь-якої точки JÎW i inp елемент масиву A i (P (J)) ніде в даному фрагменті не обчислюється, а береться з вхідних даних, тобто є елементом шуканого множини.
Cконструіруем допоміжний фрагмент, що містить вхід A 0 по змінної A:
DO I 1 = l 1, u 1
...
DO I d = l d, u d
... = ... A 0 (I 1, I 2, ..., I d) ...
END DO
...
END DO,
де d - це розмірність змінної A, а l k, u k - нижня і верхня межі k-го виміру масиву A відповідно, k = 1, d. Будемо вважати, що даний фрагмент досяжний з кожної точки програми і завжди спрацьовує останнім - цього завжди можна домогтися еквівалентним перетворенням фрагмента.
Візьмемо будь-яку точку J області W i inp. Ясно, що елемент масиву A i (P (J)) = A i (p 1 (J ),..., p d (J)) належить шуканого безлічі і треба знайти опис всіх подібних точок P (J) у просторі елементів масиву A.
Припустимо, що в кожній точці J області W i inp відбувається не використання, а визначення елемента A i (P (J)), тобто вхід A i буде грати роль виходу. Будемо вважати областю спрацьовування оператора, що містить A i, не область W J, а область W i inp. Область спрацьовування входу A 0 визначається тільки кордонами циклів допоміжного фрагмента, так як він безумовно досяжний з кожної точки програми.
У таких припущеннях вирішимо стандартне завдання побудови елементарного графа алгоритму A i ® A 0 і знайдемо область
Аналогічним чином дана задача вирішується для всіх входів, а шукане підмножина вхідних елементів масиву A є об'єднанням областей, отриманих при вирішенні даного завдання для кожного окремого входу.
Використання такого методу дозволяє отримати точний опис IN і OUT областей підпрограми. Наявність ефективних алгоритмів побудови графа алгоритму забезпечує можливість використання цього методу при аналізі реальних програм.
3 Опис вхідних та вихідних даних підпрограми в термінах фактичних параметрів
Перейдемо тепер до вирішення другого межпроцедурного аналізу - опису вхідних і вихідних даних підпрограми в термінах фактичних параметрів. Описуваний тут метод спирається на [9,16] і вимагає, щоб вхідні та вихідні дані підпрограми вже були описані у вигляді системи лінійних нерівностей.Нехай у програмі є дві підпрограми P і Q, такі, що:
SUBROUTINE P (...)
DIMENSION A p (lp 1: up 1 ,..., lp p: up p)
...
CALL Q (..., A p (op 1 ,..., op p ),...)
...
END
SUBROUTINE Q (..., A q ,...)
DIMENSION A q (lq 1: uq 1 ,..., lq q: uq q)
...
END
Нехай елементи масиву A q, що представляють частину вхідних і вихідних даних підпрограми Q, представлені у вигляді області W q, описаної за допомогою набору лінійних рівностей і нерівностей. Потрібно перерахувати цю область в термінах вирізки з відповідного фактичного параметра-масиву A p.
Запишемо умова Г pq того, що два елементи масивів A p (y 1 ,..., y p) і A q (j 1 ,..., 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 1.
Для того щоб цикл мав властивістю ParDo, необхідно і достатньо, щоб для будь-якої трійки (F k, D k, N k) графа алгоритму даного циклу включення D k Í G k було вірним на безлічі N k, де
G k - область, що задається рівністю f 1 k = i 1,
f 1 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 1 £ LQ і 1 £ j 2 £ MQ} і BQ: {1 £ j 1 £ LQ і 1 £ j 2 £ MQ}, а вихідні - багатогранником AQ: {1 £ j 1 £ LQ і 1 £ j 2 £ MQ}. Опишемо ці області в термінах фактичних параметрів.
Спочатку розглянемо перший виклик підпрограми Q. Описи перший розмірності формального і фактичного параметрів збігаються. Тому d = 2 і y 1 -1 = j 1 -1. Побудуємо функцію Г 2 pq: y 2 -1 + (y 3 -1) M-2-(K-1) M = j 2 -1. Навівши подібні, отримаємо j 2 = (y 3-K) M + y 2 -2. З опису областей вхідних і вихідних даних для підпрограми Q слід: 1 £ j 2 £ MQ = M-2, а з опису масиву А слід, що 1 £ y 2 £ M. Очевидно, що якщо y 3 ¹ K, то або j 2 <1, або j 2> M-2.
Значить, y 3 = K, отже Г 2 pq: j 2 = y 2 -2, і вхідні дані для першого виклику підпрограми Q видаються такими многогранниками: A: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = K} і (за аналогією) B: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = K-1}. Вихідні дані представляються багатогранником А: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = K}.
Аналогічно, для другого виклику отримаємо вхідні дані: A: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = K} і А: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = K-1}. Вихідні дані представляються багатогранником А: {1 £ y 1 £ L, 3 £ y 2 £ M і y 3 = 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] DE Maydan, JL Hennessy, MS 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] RW Scheifler. An Analysis of Inline Substitution for a Structured Programming Language. Communications of the ACM. Vol. 20. N 9. September 1977.
[15] DA 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.