Реферати

Учбова допомога: Новий підхід до побудови методів межпроцедурного аналізу програм

Прогнозування й удосконалювання керування грошовими потоками організації. ЗМІСТ Уведення......31. Керування і прогнозування грошових потоків організації......4 1.1 Сутність і фактори формування грошових потоків організації....4 1.2 Принципи керування грошовими потоками організації......8 2. Аналіз грошових потоків ТОВ "Призма"......11 2.1 Загальна характеристика організації......11 2.2 Аналіз фінансових показників діяльності ТОВ "Призма"......13 2.3 Аналіз руху коштів організації......19 3.

Образ автора в романі А. С. Пушкіна Євгеній Онєгін. Реферат по літературі Учениці 10 "У" класу Школи № 962 Трубициной Полини 1999 р. План. 1. Євгеній Онєгін - виразник особливостей змісту життя російського суспільства 20-х років XIX століття.

Туристичні поїздки. Туризм (від франц. - прогулянка, поїздка) - це подорож у вільний час, один з видів активного відпочинку, що перетворився в даний час у целую галузь, світову індустрію.

Оцінка впливу татаро-монгольського ярма на розвиток Русі. Зміст. План 3 I. Уведення. 4 II. Навала татаро-монголів на Русь. 6 2.1. ПЕРЕДУМОВИ ЗАВОЮВАНЬ МОНГОЛІВ 6 2.2. ЗАВОЮВАННЯ МОНГОЛІВ 7 2.3. НАВАЛА МОНГОЛІВ НА РУСЬ 9

Амурська експедиція Г. И. Невельського 1851-1855рр. Сахалінський державний університет Інститут історії, соціології і керування Кафедра російської історії Реферат по історії регіону на тему:

(Робота підтримана грантом РФФИ №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], дозволяє отримати точний опис вхідних і вихідних даних фрагмента програми.

Основна ідея цього методу полягає в тому, щоб отримати опис потрібної безлічі в просторі елементів масиву коштами аналізу простору ітерацій програми. Якщо з всієї області спрацювання оператора WJ[3] відняти всі області Dkиз опису графа алгоритму фрагмента по входу Ai(нагадаємо, що точки областей Dkявляются кінцевими точками дуг графа алгоритму даного фрагмента), то отримана область Winpбудет описувати безліч точок простору ітерацій, в яких Aiпотребляет вхідні для досліджуваного фрагмента дані.

Тепер треба отримати опис області простору ітерацій Winpв просторі елементів масиву A. Рассмотрім задачу для входу Ai(Р(J)) масиву А, де Р(J) - це векторна функція, що визначає індексні вирази даного входу. Будемо передбачати, що для входу Aiнайдена подобласть простору ітерацій Wiinp, в кожній точці якої аргументом для входу Aiявляются початкові дані. По визначенню даної області, для будь-якої точки JÎWiinpелемент масиву Ai(Р(J)) ніде в даному фрагменті не обчислюється, а береться з вхідних даних, т. е. є елементом шуканої безлічі.

Сконструюємо допоміжний фрагмент, вмісний вхід A0по змінної А:

DO I1= l1, u1.

..

DO Id= ld, ud.

.. = ... A0(I1, I2,. .., Id) ...

END DO.

..

END DO,

де d - це розмірність змінної А, а lk, uk- нижня і верхня межі k-го вимірювання масиву А відповідно, k=1, d. Будемо вважати, що даний фрагмент досяжний з кожної точки програми і завжди спрацьовує останнім - цього завжди можна добитися еквівалентним перетворенням фрагмента.

Візьмемо будь-яку точку J області Wiinp. Ясно, що елемент масиву Ai(Р(J))=Ai(p1(J),...,pd(J)) належить шуканій безлічі і треба знайти опис всіх подібних точок Р(J) в просторі елементів масиву е. вхід Aiбудет грати роль виходу. Будемо вважати областю спрацювання оператора, вмісного Ai, не область WJ, а область Wiinp. Область спрацювання входу A0определяется тільки межами циклів допоміжного фрагмента, оскільки він безумовно досяжний з кожної точки програми.

У таких припущеннях вирішимо стандартну задачу побудови елементарного графа алгоритму AiоA0и знайдемо область, на якій визначені дуги графа алгоритму. Особливість безлічі полягає в тому, що, будучи многогранником в просторі ітерацій, він одночасно є і описом безлічі вхідних даних в просторі елементів масиву А для входу Ai.

Аналогічним образом дана задача вирішується для всіх входів, а шукана підмножина вхідних елементів масиву А є об'єднанням областей, отриманих при рішенні даної задачі для кожного окремого входу.

Використання такого методу дозволяє отримати точний опис IN і OUT областей підпрограми. Існування ефективних алгоритмів побудови графа алгоритму забезпечує можливість використання цього методу при аналізі реальних програм.

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

Перейдемо тепер до рішення другої задачі межпроцедурного аналізу - опису вхідних і вихідних даних підпрограми в термінах фактичних параметрів. Метод, що Описується тут спирається на [9,16] і вимагає, щоб вхідні і вихідні дані підпрограми вже були описані у вигляді системи лінійних нерівностей.

Нехай в програмі є дві підпрограми Р і Q, такі, що:

SUBROUTINE Р(...)

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, р} неявно задає область Wpмассива Ap, відповідну області Wqмассива Aq. Для отримання явного опису Wpнеобходимо отримати проекцію (р+q)-мірної області W на р-мірне подпространство, відповідне масиву Ap. Це можна зробити за допомогою виключень Фурье-Моцкина [12,13], якщо рівність Гpqлінейно. Визначення умов його линейности розглядається далі.

Якщо рівність Гpqнелінейно, то при деяких умовах можна отримати більш просту умову. Якщо масиви Арі 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, але менше р, то в опис області W замість умови Гdpqнужно додати рівність {yi=opi, ¦ i=q+1, р }.

Для того, щоб отримати проекцію (р+q)-мірної області W на р-мірний простір, необхідно виключити змінні, введені для опису Wq, з всієї рівності і нерівностей. Це можна зробити методом Фурье-Моцкина [12,13], якщо всі обмеження, вмісні ці змінні, лінійні. Оскільки в опис Wqвходят тільки лінійні обмеження, нелинейность за даними змінним може виникнути тільки в рівності Гpq(Гdpq). Крім того, для проведення подальшого аналізу програми важливо, щоб обмеження, що все виходять також були лінійними. Тому треба виділити умови на зовнішні змінні, при яких Гpq(Гdpq) буде лінійним по всіх змінних.

Для цього беремо рівність Гpq(Гdpq), приводимо в ньому подібні, після чого прирівнюємо до нуля всі нелінійні частини. Якщо з рівності, що вийшла можна виразити змінні, введені для опису Wq, через зовнішні змінні, і підстановка цих виразів в обмеження замість змінних не входить в суперечність із заданими обмеженнями на зовнішні змінні, то додамо до рівності Гpq(Гdpq) із зануленними нелінійними частинами обмеження {lpi£yi£upi¦1£i£р} і {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 Р(L, M, N)

DIMENSION А(L, M, N), В(L, M, N).

..

DO K = 2, N-1

CALL Q(L, M-2, А(1, 3, K), В(1, 3, K-1))

END DO.

..

DO K = 2, N-1

CALL Q(L, M-2, А(1, 3, K), А(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представляются наступними многогранниками:А: {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}.

Аналогічно, для другого виклику отримаємо вхідні дані: А: {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}.

Побудувавши граф алгоритму підпрограми Р, з використанням описаного в попередньому пункті критерію параллельности отримуємо, що перший цикл володіє властивістю 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 з., NNL - 63 з., QSLH - 50 з.). Після перетворення час роботи 1 ітерації становив 65.6 з. (QSL - 11.8 з., NNL - 5 з., 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. А 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 а 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 а 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.