Анотація
Аналіз залежностей за даними є найважливішим етапом при розпаралелювання програм. Дана робота присвячена методам динамічного аналізу залежностей. Розглядаються два методи динамічного аналізу, а також практична реалізація одного з них. Отриманий динамічний аналізатор може стати в майбутньому частиною системи автоматизації розпаралелювання програм.
Зміст
1 Введення
1.1 Паралельне програмування
1.2 Автоматизація розпаралелювання
1.3 Статичний аналіз
1.4 Динамічний аналіз
1.5 Розпаралелювання під час виконання
1.6 Мета роботи
2 Постановка задачі
2.1 Залежності за даними
2.2 Система автоматизації розпаралелювання
2.3 Завдання аналізатора
3 Динамічний аналіз
3.1 Схема роботи динамічного аналізатора
3.2 Динамічний аналіз з використанням дерева контекстів
3.3 Динамічний аналіз з використанням глобальних номерів ітерацій.
3.4 Переваги і недоліки динамічного аналізу.
4 Практична реалізація
4.1 інструментація
4.2 Формат результатів
4.3 Внутрішній устрій аналізатора
4.4 Результати тестування
5 Висновок
6 Література
1. Введення
З моменту появи обчислювальних машин однієї з основних їх функцій є виконання трудомістких обчислень. При цьому складність поставлених завдань зростає швидше, ніж продуктивність окремого процесора. Багато сучасні обчислювальні завдання неможливо вирішити за допомогою однопроцесорних ЕОМ, оскільки програма буде виконуватися занадто довго або зажадає великий обсяг ресурсів таких, як, наприклад, пам'ять. Тому для збільшення швидкості обчислень застосовується також і інший шлях - створення багатопроцесорних ЕОМ.
1.1 Паралельне програмування
Паралельним програмуванням будемо називати процес написання програми для багатопроцесорної системи. Зрозуміло, паралельне програмування має ряд особливостей в порівнянні з традиційним послідовним програмуванням. Крім того, в залежності від типу багатопроцесорної системи застосовуються різні засоби програмування:
Системи із загальною пам'яттю (SMP) - набір паралельно працюючих процесорів, що мають доступ до загальної для всіх процесорів пам'яті, причому швидкість доступу до пам'яті однакова для всіх процесорів. Застосовується програмування в моделі загальної пам'яті, як правило, з використанням інтерфейсу OpenMP.
Системи з неоднорідним доступом (NUMA) - набір блоків, що містять кілька процесорів і загальну для них пам'ять. При цьому допускається звернення будь-якого процесора до віддаленої пам'яті, тобто пам'яті іншого блоку, але звернення відбувається повільніше, ніж звернення до локальної пам'яті. При програмуванні застосовується, наприклад, система Shmem.
Системи з розподіленою пам'яттю (MPP) - набір вузлів, що складаються з процесора і пам'яті, і комутаційної середовища для зв'язку між вузлами. Кожен процесор має безпосередній доступ тільки до своєї локальної пам'яті. При програмуванні застосовується модель передачі повідомлень, використовуються бібліотеки MPI, PVM та ін
Змішані системи - набір SMP-вузлів, з'єднаних комутаційної середовищем. Застосовується комбінація моделей передачі повідомлень і спільної пам'яті. Часто також використовується чиста модель передачі повідомлень, тоді кожен процесор в SMP-сайті трактується як незалежний вузол зі своєю локальною пам'яттю.
На жаль, фахівець в предметній області, здатний розробити алгоритм і запрограмувати його на якому-небудь мові програмування (наприклад, Сі чи Фортрані), далеко не завжди знайомий з прийомами написання паралельних програм і часто не може самостійно привести свою програму до вигляду, здійснимі на багатопроцесорної машині. Тому розпаралелюванням таких програм займаються окремі люди - фахівці з написання паралельних програм. Це призводить до збільшення необхідного числа програмістів, які працюють над програмою і втрати часу на хоча б мінімальне знайомство фахівця з предметної областю.
Проблема ускладнюється тим, що за десятиліття існування комп'ютерів було накопичено велику кількість бібліотек підпрограм для різних предметних областей. Ці бібліотеки широко застосовуються при написанні звичайних послідовних програм. Однак для використання можливостей багатопроцесорних ЕОМ необхідно написання паралельного варіанта кожної бібліотеки. У силу трудомісткості процесу розпаралелювання та великої кількості бібліотек масове створення паралельних варіантів бібліотек на основі існуючих послідовних варіантів не представляється можливим.
1.2 Автоматизація розпаралелювання
Можливе рішення описаної проблеми - створення системи автоматизації розпаралелювання програм. При наявності такої системи істотно полегшується робота фахівців з паралельного програмування, підвищується ефективність їх роботи, що сильно скорочує час, необхідний на розробку паралельної програми.
Процес розпаралелювання можна розділити на дві частини:
Аналіз вихідної програми.
Синтез паралельної програми.
Аналіз необхідний для виявлення прихованого паралелізму у вихідній послідовної програмі. Перш за все, сюди включається виявлення залежностей за даними між операторами програми. Така залежність виникає, наприклад, у випадку, якщо один оператор використовує значення змінної, обчислена деяким іншим оператором. Незалежні оператори можуть бути виконані паралельно на різних процесорах. Зазвичай цей принцип застосовується до циклів: якщо немає залежностей за даними між різними витками циклу, то витки можуть бути виконані паралельно різними процесорами. Також на етапі аналізу можуть збиратися відомості про необхідне розміщення даних у випадку, якщо використовується система з розподіленою пам'яттю. Крім того, можливий збір відомостей про час виконання різних ділянок програми з метою вибору найкращого варіанта розпаралелювання програми.
Синтез паралельної програми включає вибір схеми розподілу даних (якщо необхідно) і обчислень, а також безпосередньо генерацію тексту паралельної програми з використанням відповідних інструментів паралельного програмування. Детальний розгляд виникаючих при цьому питань виходить за межі цієї роботи.
Виявлення залежностей за даними у вихідному тексті програми є найважливішим етапом аналізу. Існують різні методи виявлення залежностей: статичні методи, що аналізують текст програми, динамічні методи, що досліджують хід виконання програми на деяких тестових даних, різні тести, проведені в ході виконання готової паралельної програми.
Крім аналізу програми система автоматизації розпаралелювання може отримувати різну інформацію від користувача. Так, наприклад, система ParaWise [] пропонує ітераційний процес аналізу: статичний аналіз вихідної програми і отримання додаткової інформації від користувача чергуються до отримання прийнятного результату.
Іншим прикладом системи автоматизації розпаралелювання може служити проект V-Ray []. Ця система включає статичний аналіз структури програми та інформаційних залежностей, присутніх у програмі, а також динамічний аналіз паралельних програм. Система дозволяє оптимізувати існуючі програми, а також отримати ефективні реалізації програм для різних апаратних платформ шляхом аналізу лежить в основі програм алгоритмічного підходу.
1.3 Статичний аналіз
Статичні методи аналізу засновані на дослідженні вихідного тексту програм. Основна ідея таких методів полягає в побудові по індексних виразів в операторах, що звертаються до масивів, систем рівнянь і нерівностей з невідомими, відповідними індексним змінним циклів. Наприклад, для наступного фрагмента програми:
for (i = 1; i <n; i + +)
a [i] = a [i-1] + 1;
на основі використання одного і того ж масиву «а» може бути отримано рівняння
<Інд. вир-е в лівій частині> = <інд. вир-е в правій частині на іншій ітерації>, тобто i1 = i2-1.
Вирішення даного рівняння покаже наявність залежності між сусідніми итерациями циклу: кожна наступна ітерація використовує значення, обчислене на попередній ітерації.
Існують різні методи статичного аналізу залежностей, що розрізняються методами побудови системи (можливо, неявно) по тексту програми і її рішення. У спірних ситуаціях, коли метод не може довести наявність або відсутність залежності, передбачається наявність залежності. Це консервативне припущення гарантує генерацію коректної паралельної програми, але пов'язане з втратою ефективності через недостатнє використання паралелізму, у разі, якщо реальної залежності в програмі немає.
За своєю природою статичні методи аналізу мають ряд обмежень. Одне з основних пов'язано з тим, що при аналізі тексту програми ніколи не відомі значення змінних, що використовуються в програмі. Особливо це відноситься до вхідних даних, одержуваних програмою з зовнішніх джерел. У разі, якщо такі змінні використовуються в індексних виразах при зверненнях до масивів або в граничних значеннях циклів, статичні методи аналізу не зможуть зробити якісь висновки і будуть змушені припустити наявність залежності. У ряді випадків ця проблема може бути вирішена за допомогою підказок з боку розробника вихідної програми, що вказують можливі значення деяких змінних.
Крім цього, більшість статичних методів здатні аналізувати лише лінійні відносно змінних циклів індексні вирази. Це обмеження не є надто сильним обмеженням, оскільки часто використовуються саме лінійні індексні вирази. Однак це перешкоджає проведенню аналізу в таких важливих випадках, як непряма індексація, а також виклики функцій в індексних виразах.
У мовах, подібних Сі, у статичних методів з'являється ще одна проблема: інтенсивне використання покажчиків. Як правило, статичні методи аналізу не можуть працювати з вказівниками, так само як і з досить складними виразами, які є в мові нормою. Можна зобов'язати програміста писати програми без використання відповідних конструкцій мови, але такі обмеження не застосовні при розпаралелювання бібліотек, оптимізованих для виконання на однопроцесорній машині.
Таким чином, статичні методи аналізу працюють тільки з текстом програми та з-за цього мають ряд обмежень, здатних перешкодити виявленню паралелізму в програмі. Тим не менш, цей тип методів аналізу широко застосовується в існуючих системах автоматизації розпаралелювання.
1.4 Динамічний аналіз
Динамічний аналіз програм заснований на вставці у вихідну програму додаткових операторів, які проводять аналіз. Отримана програма виконується на деякому тестовому наборі вхідних даних (або декількох наборах), і під час виконання збирається інформація про фактичні залежностях, присутніх у програмі на даному конкретному наборі даних.
Такий підхід дозволяє виробляти виявлення залежностей в багатьох ситуаціях, коли статичний аналіз неможливий. Оскільки аналіз відбувається під час виконання програми, аналізатору доступні значення всіх змінних, присутніх у програмі. Тому з'являється можливість проаналізувати будь-які посилання на елементи масивів: через індексні вирази будь-якої складності, включаючи виклики функцій, через покажчики. Динамічний аналізатор завжди може однозначно встановити елемент пам'яті, яка використовується в будь-якому операторі програми.
Недоліки динамічного аналізу також випливають з того, що він проводиться під час виконання. Динамічний аналіз показує тільки ті залежності, які виникають на даному конкретному запуску програми. Тому, використовуючи динамічний аналіз, ніколи не можна бути впевненим, що знайдено всі залежності в програмі. Деякі залежності можуть не проявитися на тестових даних. Це може призвести до генерації некоректною паралельної програми. Тому важливим завданням стає складання гарного набору тестів, досить повно покриває можливі поведінки програми.
1.5 Розпаралелювання під час виконання
У деяких випадках неможливо заздалегідь сказати, чи буде деякий цикл у програмі паралельним (наприклад, це залежить від вхідних даних). Як правило, в такій ситуації розпаралелювання вважається неможливим. Але іноді вдається сформулювати досить проста умова, при якому ймовірні залежності за даними зникають. Тоді застосовується наступне рішення: у паралельну програму включається два варіанти даного фрагмента програми: один паралельний, інший послідовний. Під час виконання програми перевіряється виконання умови, і залежно від результату виконується або один фрагмент, або іншої.
Аналогічно працює схема inspector-executor. Спірний цикл виконується 2 рази. Перший раз - для з'ясування, чи є цикл паралельним. При цьому ніяких обчислень не проводиться. Другий раз - вже реальне виконання обчислень з урахуванням результату першого проходу. Додатковий плюс такої схеми полягає в тому, що, коли один і той же цикл виконується багато разів, а його основні параметри залишаються одними і тими ж, інспекційний прохід можна робити тільки один раз, використовуючи отриманий результат при кожному новому виконанні циклу.
Таким чином, винесення деяких перевірок з етапу аналізу на етап виконання програми дозволяє пом'якшити обмеження методів, розглянутих вище.
1.6 Мета роботи
Дана робота присвячена методам динамічного аналізу. Ставиться мета створити робочу реалізацію динамічного аналізатора - бібліотеки, яка збирає інформацію про залежності за даними у вихідній програмі. У майбутньому цей аналізатор може стати частиною системи автоматизації розпаралелювання програм для систем зі спільною пам'яттю.
2. Постановка завдання
2.1 Залежності за даними
Залежність за даними утворюють будь-які два оператора програми, які звертаються до однієї комірки пам'яті, якщо хоча б один з них робить запис в цей осередок []. Існує 3 види залежностей за даними. Нехай s1 і s2 - оператори в програмі, які звертаються до однієї комірки пам'яті, і s2 виконується після s1. Оператори s1 і s2 можуть бути одним і тим же оператором програми. Залежно від порядку читання та запису використовуваної клітинки залежно поділяються наступним чином:
пряма залежність (true dependence) - s1 записує значення в комірку пам'яті, а s2 зчитує,
зворотна залежність (anti dependence) - s1 зчитує значення, а s2 записує,
залежність після виходу (output dependence) - обидва оператори s1 і s2 виробляють запис у клітинку.
У кожному з цих випадків оператор s2 зобов'язаний виконуватися після оператора s1, тому даний порядок необхідно зберегти при розпаралелювання програми. Якщо обидва оператори s1 і s2 зчитують дані з комірки пам'яті, то вони можуть виконуватися в будь-якому порядку один щодо одного, тобто залежність не виникає.
Нехай є кілька вкладених циклів. Нехай виконується певний оператор, що міститься в тілі цих циклів. Номери ітерацій осяжний циклів утворюють вектор ітерацій.
Нехай є залежність за даними між операторами s1 і s2 з відповідними векторами ітерацій i1 і i2. Передбачається, що вектори i1 і i2 мають однакову розмірність, і відповідні їх елементи відповідають одним і тим же циклам програми. Відстанню або кроком залежності назвемо вектор d = i2 - i1.
Надалі ми будемо говорити про розпаралелювання циклів програми. Тому значення набувають залежності між витками циклів. Такі залежності виникають, якщо оператори s1 і s2 виконувалися на різних ітераціях циклу, тобто d ≠ 0. Така залежність вимагає збереження порядку виконання ітерацій. Цикл, що не містить залежностей між витками, можна легко распараллеліть, оскільки витки можуть виконуватися незалежно в будь-якому порядку.
2.2 Система автоматизації розпаралелювання
Планована система автоматизації розпаралелювання складається з наступних складових частин:
інструментатор / перетворювач програми,
аналізатор,
експертні модулі з розпаралелюванню програми,
модуль-асистент, що дозволяє користувачеві працювати з системою.
Вихідна програма надходить на вхід інструментатору, який генерує внутрішнє представлення і модифікує програму для динамічного аналізу. Завдання аналізатора - зібрати інформацію про програму, необхідну експертними модулів для розпаралелювання програми. Користуючись цією інформацією, експертні модулі можуть прийняти рішення про розпаралелювання конкретних циклів, про розподіл даних (якщо необхідно отримати програму для машини з розподіленою пам'яттю). Асистент необхідний, щоб користувач міг побачити результати роботи аналізатора та експертних модулів, міг надати додаткову інформацію, а також міг самостійно приймати рішення про розпаралелювання програми. Після прийняття всіх рішень вся інформація направляється назад модулю, що працює з текстом програми, і він генерує текст паралельної програми.
Дана робота присвячена одному з компонентів такої системи - динамічному аналізатору. При цьому розглядається лише можливість розпаралелювання циклів, що є основним джерелом паралелізму в більшості завдань. Під циклами тут і далі розуміються цикли типу DO. Незважаючи на те, що аналізатор може визначати і визначає залежності між витками циклів інших типів, тільки цикли типу DO можуть бути легко распараллелена. У мові Сі циклом типу DO вважається цикл for з одного целочисленной індексного змінної і постійним кроком її зміни.
2.3 Завдання аналізатора
Завдання аналізатора в рамках системи автоматизації розпаралелювання полягає в отриманні з програми необхідної для розпаралелювання інформації. У даній роботі не розглядаються питання, пов'язані з розпаралелюванням програм для розподіленої пам'яті.
Тому найголовніше завдання аналізатора - зібрати інформацію про залежності за даними, що присутні в програмі. Ця інформація необхідна для того, щоб виділити паралельні цикли, а також цикли з регулярними залежностями, які теж, можливо, вдасться распараллеліть. Інформація про залежності за даними потрібна як при розпаралелювання в моделі загальної пам'яті, так і в моделі розподіленої пам'яті.
3. Динамічний аналіз
3.1 Схема роботи динамічного аналізатора
Загальна схема роботи динамічного аналізатора показано на Малюнку 1. На першому етапі у вихідний текст програми вставляються виклики трасувань функцій, які дозволяють аналізатору отримувати інформацію про хід виконання програми. Набір трасувань функцій може змінюватися в залежності від цілей і використовуваного алгоритму аналізу. Але як мінімум трасувальні виклики вставляються на всі доступи до пам'яті, входи і виходи циклів, зміни індексних змінних в циклах.
Далі отримана програма надходить на вхід стандартного компілятора і потім запускається на різних наборах вхідних даних. За отриманою трасування інформації аналізатор визначає залежності між операторами у вихідній програмі.
Можливий варіант, коли інструментіруется не вся програма, а лише певну частину. У цьому випадку в якості результатів будуть отримані тільки залежності між операторами, які потрапили в інструментованого частина програми. Це може бути корисно, якщо динамічний аналіз використовується для уточнення результатів, отриманих, наприклад, за допомогою статичного аналізатора.
Далі розглядаються два можливих алгоритму динамічного аналізу.
3.2 Динамічний аналіз з використанням дерева контекстів
Ця схема аналізу описана в роботі [] і в дещо зміненому вигляді наводиться тут.
Введемо наступну термінологію.
Дерево контекстів (context tree) CV (p) програми p - дерево, що складається з вершин наступних типів: функція, цикл, оператор виклику функції або доступу до пам'яті, умовний оператор, і інші типи операторів, присутні в мові. Між двома вершинами є ребро, якщо одна з них безпосередньо викликає іншу. Корінь дерева - функція main (), основне тіло програми або інше аналогічне поняття з використовуваної мови програмування.
Контекст - це шлях від кореня до будь-якої вершини дерева контекстів.
Нехай вершина S (a) відповідає оператору доступу до пам'яті a. Контекст CV (a) оператора a - шлях від кореня дерева контекстів до вершини S (a).
Контекст функції (циклу) - шлях від кореня дерева контекстів до вершини, що відповідає цій функції (циклу).
Розглянемо приклад.
int A [10], B [10];
void main () {
for (int i = 0; i <10; i ++)/* f1 * /
proc (i) / * st1 * /
}
void proc (int i) {
for (int m = 0; m <10; m + +) {/ * f2 * /
if (i% 2 == 0) / * if1 * /
A [m] = ...;/* st2 * /
else
... = A [m]; / * st3 * /
B [m] = ...;/* st4 * /
}
}
У цьому прикладі оператор st2 може мати контекст C (a) = (main f1 st1 proc f2 if1 st2). У разі наявності рекурсивної функції rfunc контекст міг би бути таким: C (a) = (... rfunc st1 rfunc st1 rfunc ...).
Ланцюжок векторів ітерацій (iteration vector chain) IVC (a) - це список номерів ітерацій для кожного вузла-циклу контексту C (a). Якщо контекст не містить циклів, то список не буде містити жодного елемента.
Ланцюжок векторів ітерацій відноситься до конкретного моменту виконання програми, тому кожен оператор може мати кілька різних IVC. Так, наприклад, для оператора st2 може бути IVC (a) = (1, 4) або IVC (a) = (4, 1).
Віртуальна точка доступу a (virtual point) - це пара VP (a) = (C (a), IVC (a)).
Для кожної комірки пам'яті аналізатор зберігає віртуальні точки останнього запису й всіх читань з моменту останнього запису. Це дозволяє виявити всі залежності за даними, що виникають у програмі.
Алгоритм знаходження прямих залежностей.
Для кожної операції читання ar:
Визначити елемент пам'яті, читану ar.
Визначити віртуальну точку VP (aw) останній запис aw в цей осередок.
Знайти контекст CL - довжелезний загальний подпуть контекстів C (ar) і C (aw).
Знайти контекст Cm - довжелезний контекст, який є подконтекстом контексту CL таким, що відповідні ланцюжки IVC (ar) і IVC (aw) містять однакові значення на відрізку, відповідному контексту Cm.
Нехай r і w - вектори, утворені відрізками ланцюжків IVC (ar) і IVC (aw), що не ввійшли в контекст Cm. Обчислити відстань d = r - w, якщо dim (r)> 0 і покласти d = [] інакше.
Нехай f1 - самий «глибокий» цикл в контексті СL. Додати залежність між итерациями циклу f1 (і обрамляють циклів) з відстанню d.
Замість п.6 можна записати залежність між конкретними операторами в тілі циклу. Нехай st1 і st2 - вершини C (ar) і C (aw), безпосередньо наступні за CL. Додати залежність st1 від st2 з відстанню d. Оскільки в даній роботі розглядається тільки розпаралелювання циклів, в поточному аналізаторі цього не робиться.
Схожі алгоритми потрібно застосовувати для знаходження зворотних і залежностей по виходу. При знаходженні залежностей по виходу треба для кожної операції запису шукати попередню операцію запису. Для знаходження зворотних залежностей необхідно для всіх операцій запису обробляти всі попередні їм читання комірки пам'яті з моменту останнього запису в ту ж клітинку.
3.3 Динамічний аналіз з використанням глобальних номерів ітерацій
Інший підхід до динамічного аналізу використовує поняття глобальних номерів ітерацій (GIN - Global Iteration Number) []. Це означає, що всі ітерації всіх циклів нумеруються по порядку. Наприклад, в наступному прикладі
for (i = 1; i <= 3; i + +)
for (j = 1; j <= 3; j + +)
A [f1 (i, j)] = ... A [f2 (i, j)] ...;
глобальні номери ітерацій будуть розподілені наступним чином:
(1, -)
1
(1,1)
2
(1,2)
3
(1,3)
4
(2, -)
5
(2,1)
6
(2,2)
7
(2,3)
8
(3, -)
9
(3,1)
10
(3,2)
11
(3,3)
12
Тут у кожній клітці в першому рядку показані значення індексів циклів (i, j), а в другій - відповідний глобальний номер ітерації. Запис (i, -) означає, що в момент початку ітерації зовнішнього циклу внутрішній цикл ще не активний.
Даний метод використовується для знаходження залежностей між итерациями циклів. При вході в цикл запам'ятовується GIN першої ітерації. Крім того, при вході в чергову ітерацію циклу запам'ятовується GIN поточної ітерації, а GIN попередньої ітерації додається в спеціальний буфер, в якому записані k останніх ітерацій цього циклу (k - це ємність буфера). При обчисленні відстаней для залежностей цей буфер буде проглядатися в пошуках підходящої ітерації, тому метод дозволяє визначити відстань, якщо воно не перевершує k, або встановити, що воно перевищує k. Для кожної комірки пам'яті запам'ятовується GIN останній запис для відстеження прямих залежностей і залежностей по виходу, а також попередніх читань, для того щоб відстежувати також і зворотні залежності.
Розглянемо випадок, коли деяка осередок масиву A записується на ітерації (2, 2), а потім читається на ітерації (2, 3). До моменту читання стан виконання програми буде таким:
Цикл
Початок циклу
Поточна ітерація
Буфер
i
1
5
1
j
6
8
7,6
Запис у клітинку масиву мала GIN = 7. Це було на тій же ітерації зовнішнього циклу. Переглянувши буфер циклу по j, можна обчислити відстань між записом і читанням, рівне 1.
Тепер нехай запис проводився на ітерації (1,1), а читання на ітерації (3,3). Стан програми в момент читання:
Цикл
Початок циклу
Поточна ітерація
Буфер
i
1
9
5,1
j
10
12
11,10
Запис у масив (GIN = 2) відбулася не в поточному циклі (2 <10), а в осяжний циклі (1 <= 2 <= 9). Переглядаючи буфер циклу за i в пошуках ітерації з GIN <= 2, ми визначаємо відстань, рівне 2.
По суті, даний метод дозволяє робити те ж саме, що і попередній, але тільки на рівні цілих ітерацій циклів, а не окремих операторів і використовує при цьому інші технічні рішення. Крім цього, попередній метод вводить зручне поняття дерева контекстів, яке може бути використане також і для інших цілей крім динамічного аналізу. Тому в рамках даної роботи реалізовувався метод дерева контекстів.
3.4 Переваги і недоліки динамічного аналізу
У порівнянні зі статичним аналізом динамічний аналіз має низку переваг:
динамічний аналіз ніяк не залежить від виду індексних виразів, що зустрічаються в програмі. Для будь-якого виразу обчислюється його значення, що неможливо при статичному аналізі. Як наслідок, динамічний аналіз може працювати з непрямою індексацією, викликами функцій в індексних виразах.
динамічний аналіз працює в термінах конкретних елементів пам'яті, що дозволяє проводити аналіз навіть при інтенсивному використанні покажчиків. Статичні ж методи, як правило, не можуть аналізувати програми, що працюють з покажчиками.
динамічний аналіз завжди дає повну картину залежностей для даного конкретного запуску програми саме з цим набором вхідних даних. Якщо хід виконання програми залежить тільки від вхідних даних (не використовується, наприклад, генератор випадкових чисел), то динамічний аналіз дає повну картину залежностей для будь-якого запуску програми з цим набором даних.
динамічний аналіз ніколи не вкаже на залежність операторів там, де її насправді немає.
Основні недоліки динамічного аналізу також обумовлені необхідністю виконання програми:
оскільки завжди повинні обчислюватись конкретні значення виразів, то навіть якщо нас цікавлять залежності в деякому невеликому фрагменті програми, ми повинні виконати всі попередні оператори програми, хай і без викликів функцій аналізуючої системи. Для фрагментів, близьких до кінця програми, такі втрати можуть істотно вплинути на час аналізу.
так як для кожної комірки пам'яті необхідно зберігати деякі дані, то ми змушені або збільшувати розміри цікавить нас осередки, знижуючи точність аналізу, або суттєво зменшувати розміри вихідних даних і параметри завдання, що, можливо, не цілком коректно відображає поведінку програми при вирішенні реальних завдань .
динамічний аналіз може дати картину залежностей тільки для даного набору вхідних даних. При виконанні програми на іншому наборі даних залежності можуть змінитися. У результаті динамічний аналіз може вказати на незалежність операторів, тоді як насправді вони є залежними. Це може призвести до генерації некоректною паралельної програми, що, безумовно, є найбільш значною проблемою при використанні динамічного аналізу.
Остання проблема призводить до необхідності складання системи тестів, досить повно відображає поведінку програми в різних ситуаціях. Після проведення аналізу на такій системі тестів необхідно об'єднати отримані залежності і вже об'єднані результати використовувати при прийнятті рішень про розпаралелювання програми.
4. Практична реалізація
Для роботи динамічного аналізатора за наведеною схемою необхідно реалізувати два компоненти системи:
програму-інструментатор (реалізована в рамках окремої роботи);
бібліотеку, яка містить реалізації функцій аналізатора.
Бібліотека-аналізатор була реалізована на мові C + +. Ця мова легко може бути використаний спільно з мовами Сі і Фортран, які широко використовуються для програмування обчислювальних завдань.
Для спільної роботи аналізатора з іншими компонентами системи автоматизації розпаралелювання необхідно сформувати інтерфейс аналізатора, який повинен використовувати інструментатор, а також формат видачі результатів аналізатором.
Крім цього має бути передбачено засіб, що дозволяє скомбінувати результати, отримані при різних запусках програми.
4.1 інструментація
Завдання інструментації полягає в тому, щоб вставити у вихідну послідовну програму виклики функцій аналізатора, що описують хід виконання програми. При цьому повинні дотримуватися такі вимоги:
необхідно повідомляти аналізатору час життя кожної змінної програми за допомогою реєстрації змінної на початку часу життя скасування реєстрації після його закінчення,
повинні інструментованого всі доступи до даних із зазначенням осередки та операції (читання або запис),
повинні інструментованого входи і виходи підпрограм, початок кожного циклу, його завершення, а також перехід до нової ітерації,
необхідно запровадити систему ідентифікації, що дозволяє співвідносити отриману інформацію з вихідним текстом програми.
Для майбутнього розвитку також корисно інструментованого всі наявні конструкції використовуваної мови програмування, в тому числі умовні оператори. Це дозволить виявляти відмінності в поведінці програми на різних гілках виконання.
Розробка інструментатора ведеться з використанням бібліотеки Sage + +, що реалізує синтаксичний розбір програм на мові Сі. Ця бібліотека вводить для кожного оператора програми унікальний ідентифікатор. Крім того, Sage створює внутрішнє представлення програми, яке можна використовувати при формуванні її змінених варіантів. Тому було прийнято рішення використовувати ідентифікатори Sage також і в аналізаторі. Також необхідно отримувати інформацію про номери рядків вихідної програми для забезпечення можливості зручного відображення результатів користувачеві.
Реєстрація змінних необхідна через існування локальних і динамічних змінних. Це означає, що в різні моменти часу одна й та ж комірка пам'яті може відноситися до різних змінним, причому звернення до новоствореної змінної не створюють залежно від звернень до іншої змінної, що розташовувалася раніше в тій же комірці пам'яті. При реєстрації аналізатору повідомляються адресу початкової комірки пам'яті, відведеної під масив, і розміри масиву по всіх вимірах. Скалярні змінні вважаються масивами з нульовим числом вимірів. Недінаміческіе (глобальні та локальні) змінні отримують номер-ідентифікатор, призначений бібліотекою Sage. Для динамічних змінних ідентифікатори аналізатор призначає самостійно, оскільки інформація про наявність і числі таких змінних з'являється тільки під час виконання.
Враховуючи вищесказане, було отримано наступний інтерфейс бібліотеки аналізатора.
DA_init () - ініціалізація бібліотеки аналізу, необхідно викликати до виклику будь-якої іншої функції.
DA_exit () - завершення аналізу і збереження результатів
DA_SagePos (long sageNumber) - повідомляє аналізатору про початок оператора з ідентифікатором sageNumber
DA_LinePos (long lineNumber, char * filename) - повідомляє аналізатору про поточному номері рядка і файлі.
DA_WriteBegin (void * addr, long size), DA_WriteEnd () - пара функцій, що відзначають початок і завершення оператора присвоювання - запис в осередок пам'яті
DA_Read (void * addr, long size) - читання комірки пам'яті
DA_LoopDo (), DA_LoopFor (), DA_LoopWhile (), DA_LoopDowhile () - початок відповідного циклу.
DA_LoopIter () - початок чергової ітерації циклу
DA_LoopEnd () - завершення циклу
RegArrId (long id, void * addr, long rank, long size [], long elemsize, const char * name) - реєстрація недінаміческого масиву в аналізаторі.
RegArr (void * addr, long rank, long size [], long elemsize, const char * name) - реєстрація динамічного масиву.
DA_UnregArrId (long id), DA_UnregArr (void * addr) - відповідні функції скасування реєстрації масивів.
4.2 Формат результатів
Як результат аналізатор надає дерево контекстів з додатковою інформацією, розміщеною в вершинах:
список залежностей між витками кожного з векторами відстаней, а також за змінним, звернення до яких створили ці залежності,
список масивів, що використовуються оператором, а також, якщо елементи масиву використовувалися лінійним чином, то параметри відповідної арифметичної прогресії
Також у вузлах накопичується профілювальних інформація, яка може бути корисною при прийнятті рішень про розпаралелювання:
кількість виконань піддерева з коренем в даному вузлі,
загальний час виконання піддерева з коренем в даному вузлі,
середнє, мінімальне і максимально час одноразового виконання піддерева з коренем в даному вузлі.
Крім того, аналізатор зберігає інформацію про всі зареєстровані змінних. Список масивів, використовуваних в операторі - це лише посилання на елементи списку всіх масивів, за якими можна отримати додаткову інформацію.
Для роботи з цією інформацією була реалізована спеціальна бібліотека. Аналізатор використовує цю бібліотеку для створення дерева контекстів і наповнення його інформацією. Інші модулі системи автоматизації розпаралелювання можуть використовувати бібліотеку для читання збережених результатів аналізу.
Основу бібліотеки роботи з результатами складає клас ContextNode, що представляє вершину дерева контекстів. У цьому класі передбачені методи для:
додавання безпосередніх нащадків,
навігації по дереву контекстів: перехід до батьківської вершини, до нащадків, до наступної вершини на тому ж рівні,
отримання і зміни ідентифікаційної інформації про вершину: Sage-номер, тип вершини, номер рядка вихідного файлу програми,
отримання і зміни інформації про залежності за даними, які зберігаються в даній вершині,
отримання і зміни профілювальних інформації,
збереження інформації у файл і завантаження інформації з файлу.
Для зберігання залежностей в бібліотеці передбачені класи:
Dependence - клас, що представляє одну залежність, що містить вектор відстані,
DependenceStore - клас, призначений для зберігання всіх залежностей одного типу.
Інформація про масивах, використовуваних у програмі, представляється класами CArrays і CArrayData. Клас CArrayData містить інформацію про один масиві:
ім'я масиву, номер рядка, в якому він був визначений,
Sage-номер або внутрішній ідентифікатор масиву для динамічних масивів,
число вимірювань масиву і розміри кожного виміру,
розмір одного елемента масиву.
При збереженні в файл дані записуються у форматі XML. Зручність даного формату полягає у тому, що він має деревоподібну структуру і, крім того, є текстовим форматом, а тому може бути безпосередньо прочитаний людиною. Слід також зазначити, що існують прості та зручні бібліотеки для роботи з XML.
Конкретне уявлення дерева контекстів у вигляді XML неістотно. Передбачається, що всі модулі, що вимагають для роботи результати аналізу, будуть використовувати призначену для цього бібліотеку.
4.3 Внутрішній устрій аналізатора
Внутрішня структура аналізатора показано на Малюнку 2.
Ядро є основною частиною динамічного аналізатора. Фактично, ядро - це реалізація алгоритмів, описаних у розділі, що використовує блок зовнішнього інтерфейсу для отримання інформації про хід виконання програми, а інші блоки як структури даних для зберігання інформації.
Малюнок 2 Внутрішня структура аналізатора
Ядро аналізатора використовує внутрішній інтерфейс, основні операції якого відповідають операціям інтерфейсу аналізатора, описаним у розділі. Є, тим не менш, незначні відмінності, зумовлені міркуваннями зручності і простоти. Блок зовнішнього інтерфейсу необхідний для перетворення викликів функцій аналізу у виклики інтерфейсу ядра. Історично таке перетворення було необхідно у зв'язку з тим, що перша версія аналізатора була реалізована на основі інтерфейсу отладчика системи DVM []. Цей відладчик призначений для перевірки коректності DVM-програми за допомогою моделювання її паралельного виконання, а також за допомогою накопичення і порівняння трас при її послідовному і паралельному виконанні. У його інтерфейс входять базові функції, необхідні динамічному аналізатору: читання і запис значень змінних, початок і завершення циклів, початок ітерацій циклів. Тому до появи спеціального інструментатора було можливо використовувати інструментатор, призначений для налагоджувача DVM. У даний момент наявність блоку зовнішнього інтерфейсу дозволяє при необхідності змінювати інтерфейс аналізатора, не зачіпаючи основну частину бібліотеки.
Дерево контекстів і список масивів - це частини бібліотеки роботи з результатами аналізу. Аналізатор використовує їх для зберігання інформації під час виконання програми і збереження результатів по закінченні аналізу. Інші модулі системи автоматизації розпаралелювання зможуть скористатися тією ж бібліотекою для читання збережених результатів. Додатково аналізатор створює дерево векторів ітерацій - структуру даних, що представляє ланцюжка векторів ітерацій для операторів програми. Усі бесіди, що виникають при аналізі, організовуються в дерево за наступним принципом: кожен елемент ланцюжка відповідає переходу на один рівень вниз по дереву, при цьому однаковим початків ланцюжків відповідають однакові шляхи від кореня по дереву. Тоді однакові ланцюжка векторів ітерацій представляються одним вузлом в дереві. Віртуальна точка доступу при цьому видається просто як пара посилань на відповідні вузли в дереві контекстів і дереві векторів ітерацій. Дерево векторів ітерацій не зберігається, оскільки після обчислення відстаней залежностей вектори ітерацій вже не потрібні.
На початку і при завершенні роботи аналізатор виробляє спеціальні дії. При виконанні команди ініціалізації ядро шукає результати попереднього запуску аналізатора і в разі успіху завантажує раніше отримані дерево контекстів і список масивів. У цьому випадку результати нового запуску додаються до вже наявних результатів, що необхідно при наявності кількох тестів. Коли аналізатор отримує команду завершення, вміст дерева контекстів і списку масивів зберігається у файл.
4.4 Результати тестування
Тестування аналізатора проводилося на програмах, що реалізують рішення рівняння Пуассона в тривимірному просторі класичними ітераційними методами: методом Якобі, методом послідовної верхньої релаксації (SOR), методом червоно-чорного впорядкування (RedBlack), а також на програмі, реалізує рішення системи лінійний алгебраїчних рівнянь методом Гауса .
Основні показники продуктивності показані на Таблиці 1. У методах Якобі, SOR і RedBlack використовувалася матриця розміру 16x16x8. У методі Гаусса вирішувалася система розміру 100x100.
Таблиця 1 - Показники продуктивності
Метод
Час виконання, сек
Використовувана пам'ять, Kb
без аналізатора
з аналізатором
без аналізатора
з аналізатором
Якобі
0,05
4,73
924
58136
SOR
0,05
2,23
908
25096
RedBlack
0,05
5,52
908
65752
Гаус
0,04
6,45
980
51756
З наведених результатів випливає, що поточна реалізація динамічного аналізатора уповільнює роботу програми в 100 і більше разів, використовуючи при цьому в десятки разів більший обсяг пам'яті. Це обмежує можливості застосування аналізатора, оскільки для того, щоб час аналізу залишалося в розумних межах, необхідно сильно зменшувати розмірність розв'язуваної задачі.
Слід зазначити, що на даний момент не було зроблено спроб оптимізації аналізатора. Тому отримані результати не можна вважати остаточними, і слід вважати вказівкою на необхідність подальшої роботи з поліпшення методу динамічного аналізу.
5. Висновок
Підіб'ємо деякі підсумки даної роботи. Динамічний аналіз залежностей за даними володіє рядом переваг в порівнянні з традиційними статичними методами аналізу. Оскільки аналіз проводиться під час виконання програми, доступна вся інформація про вироблені доступах в пам'ять. Це дозволяє одержати абсолютно точну інформацію про залежності за даними незалежно від складності індексних виразів масивів, наявності непрямої індексації або покажчиків.
Основним недоліком даного методу є відсутність гарантії того, що всі можливі залежності за даними виявлені. Це означає, що для проведення аналізу необхідно наявність набору тестів, досить повно покриває різні варіанти поведінки програми. Крім того, суттєві витрати ресурсів аналізатором при кожному запуску програми на виконання змушують зменшувати розмірність завдань для аналізу, що, можливо, не завжди можливо.
У рамках даної роботи один з методів динамічного аналізу був реалізований у вигляді бібліотеки на мові С + + (близько 2500 рядків вихідного коду). Проведено тестування аналізатора на наборі програм на мові Сі, що представляють собою реалізації класичних ітераційних методів (Якобі, SOR, RedBlack) і методу Гаусса. Тим самим показана можливість застосування динамічного аналізу для пошуку залежностей у програмах, які вимагають розпаралелювання.
6. Література
ParaWise. The Computer Aided Parallelization Toolkit [HTML, PDF] (http://www.parallelsp.com).
Проект V-Ray [HTML] (http://parallel.ru/v-ray).
Jacobson T., Stubbendieck G. Dependency Analysis of FOR-Loop Structures for Automatic Parallelization of C Code [PDF] (http://www.css.edu/depts/cis/mics_2003/MICS2003_Papers/Jacobson.PDF).
Karkowski I., Corporaal H. Overcoming the Limitations of the Traditional Loop Parallelization / / Journal of Future Generation Computer Systems. 1998. № 13. P. 407-416.
Petersen PM Evaluation of Programs and Parallelizing Compilers Using Dynamic Analysis Techniques. Champaign, IL, USA: University of Illinois at Urbana-Champaign, 1993. 164 p.
DVM-система [HTML] (http://www.keldysh.ru/dvm).