Про деякі завдання аналізу і трансформації програм

С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маліков, Д.М. Мельник, А.В. Меньшикова

Анотація.

В цій статті обговорюються деякі перспективні напрями досліджень, що проводяться у відділі компіляторних технологій Інституту системного програмування РАН. Методи аналізу і трансформації програм, раніше що застосовувалися в основному в оптимізують компіляторах, в даний час знаходять застосування при рішенні багатьох суміжних завдань, таких як забезпечення безпеки програм, генерація тестів для програм і т. д.

1. Введення

В цій статті обговорюються деякі перспективні напрями досліджень, що проводяться у відділі компіляторних технологій Інституту системного програмування РАН. Методи аналізу і трансформації програм, раніше що застосовувалися в основному в оптимізують компіляторах, в даний час знаходять застосування при рішенні багатьох суміжних завдань, таких як забезпечення безпеки програм, генерація тестів для програм і т. д.

В відділі ведеться робота і в традиційній області оптимізації програм. Упор робиться на розробку нових методів аналізу покажчиків в програмах на мові Сі. Також проводяться дослідження так званих "полустатіческіх" (profile-based) методів оптимізації програм. Такі методи полягають у використанні на стадії оптимізації коду інформації, накопиченої з попередніх її запусків.

Дана робота присвячена розгляду трьох напрямків. По-перше, це так звана маскування програм, яка має на меті, повністю зберігши користувальницьке поведінку програми, змінити її текст так, що зворотна інженерія або повторне використання її фрагментів або програми цілком стає складним. По-друге, це завдання автоматичної оптимізації програми для роботи на багатопроцесорних системах зі спільною пам'яттю шляхом розбиття її на нитки. По-третє, це завдання автоматичного виявлення вразливостей в програмі.

Для підтримки робіт з дослідження методів аналізу і трансформації програм у відділі розроблена інтегрована інструментальне середовище (Integrated Research Environment, IRE), яка містить велику кількість різних алгоритмів аналізу і трансформації програм і надає зручний інтерфейс користувача.

Дана робота має наступну структуру: у розділі 2 ми розглядаємо завдання автоматичного розбиття програми на нитки, в розділі 3 розглядаються завдання маскування програм, а в розділі 4 завдання автоматичного виявлення вразливостей. Далі в розділі 5 коротко описується інтегрована середа IRE, її склад і внутрішнє подання MIF, що використовується всіма компонентами IRE. Нарешті, в розділі 6 ми формулюємо висновки даної роботи і даємо напрямки подальших досліджень.

2. Розбиття програм на нитки і підвищення локальності

В даний час широко поширені робочі станції і персональні комп'ютери, що містять кілька центральних процесорів. Масові багатопроцесорні системи зазвичай містять 2, 4 або 8 процесорів, що працюють над загальною пам'яттю з однаковим для всіх процесорів часом доступу (SMP). Для максимального використання можливостей SMP-систем в обчислювально-інтенсивних додатках необхідно максимально використовувати "легковагі" процеси (нитки). У цьому випадку накладні витрати на комунікацію мінімізовані, тому що всі нитки розділяють один адресний простір, а синхронізаційними операції виконуються простіше і швидше, ніж для звичайних ( "важких") процесів.

Відомо, що більшість програм при роботі демонструють гарну локальність, тобто працюють над близько розташованими в пам'яті даними, або виконують одні й ті ж інструкції. На цьому спостереженні заснована робота процесорних кешей. Для найбільш повного використання можливостей кеша необхідно покращувати локальність програми.

В даному розділі ми представимо новий алгоритм для поділу програми на нитки, який покращує локальність програми в цілому. Отримані експериментальні результати показують виправданість застосування нового алгоритму для розбиття на нитки програм без чіткої циклічної структури, які не можуть бути розбиті на нитки традиційними методами. Основним висновком роботи є те, що міркування локальності повинні братися до уваги при розподілі програми на нитки для невеликої кількості процесорів.

Системи з пам'яттю, що розділяється найбільш зручні для програміста паралельних програм. Більше того, частина роботи по розпаралелюванню послідовного коду може бути виконана компілятором. Існує багато досліджень з автоматичного розпаралелюванню циклів і рекурсивних процедур на таких системах. Деякі розробки реалізовані в промислових компіляторах, наприклад, IBM Visual Age C + +, Intel C + + Compiler, SGI MIPSPro, REAPAR та інших.

В Останнім часом проводяться дослідження з автоматичного распарал-леліванію будь-якого послідовного коду. Запропоновано кілька підходів, таких, як управління виконанням ниток (thread-level speculation) [6], комутативність аналіз, динамічний розподіл завдань на нитки (dynamic task scheduling) [5], автоматичне відділення на нитки на етапі компіляції. Частина запропонованих алгоритмів перевірена авторами на емуляторах, частина реалізована в існуючих дослідних компіляторах, наприклад, в компіляторі SUIF Стенфордського університету [7].

Формалізація поняття локальності проведена в [8]. Розглядається два види подій локальності:

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

Подія просторової локальності відбувається при доступі до комірки пам'яті, розташованої в блоці, вже завантаженому в кеш при зверненні до будь-якої іншої комірці.

Для збільшення кількості подій локальності останнім часом запропоновано велике кількість оптимізують перетворень програми. Основними методами є:

Угруповання інструкцій, які використовують одні й ті ж дані (locality grouping), для збільшення кількості подій тимчасової локальності.

Упаковка даних в пам'яті (data packing) для збільшення кількості подій просторової локальності.

Перестановка процедур, базових блоків і т.п.

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

2.1. Алгоритм розбиття програми на нитки

В цьому розділі розглядається побудова проміжного представлення програми, над яким працює алгоритм, а також детально описується сам алгоритм розбиття програм на нитки. Детальний опис алгоритму можна знайти в [3]. Алгоритм складається з трьох частин:

Побудова цінової моделі, що відбиває властивості локальності

Розбиття програми на нитки

Додаткові оптимізації

Рис. 1. Приклад функції та її DDG.

2.1.1. Граф залежностей по даними

При поділі програми на нитки перш за все потрібно враховувати залежності по даними. Тому природно вимагати, щоб проміжне представлення програми містило легкодоступну інформацію про залежності за даними між різними частинами програми. У той же час необхідно максимально відобразити відомості про "природному" паралелізм програми, причому на різних рівнях - від окремих інструкцій, до більш великих програмних блоків.

Виставою, що володіє всіма необхідними нам властивостями, є ієрархічний граф залежностей за даними, що використовується в [9] (data dependence graph, DDG). Вузлом такого графа може бути:

Простий оператор (додавання, множення, порівняння, присвоювання і т.д.)

Більше складний оператор (умовний оператор, оператор циклу і т.д.)

Граф залежностей за даними наступного рівня, інкапсулі-ючий властивості відповідного програмного блоку

Дуги графа DDG представляють собою залежності за даними між вузлами. Більш формально, хай u і v - вузли DDG, причому в послідовній програмі u передує v. Дуга (u, v) входить до граф тоді і тільки тоді, коли між u і v є залежність за даними одного з трьох типів:

"запис-читання" (у вузлі v необхідні результати обчислень вузла u),

"читання-запис" (у вузлі v записується змінна, значення якої зчитується в u),

"запис-запис" (обидва вузла записують одну й ту ж пере-менную).

Наявність одній з вказаних залежностей за даними між вузлами говорить про те, що при паралельному виконанні програми для отримання результатів, які відповідають послідовної версією, необхідно виконати u раніше, ніж v.

Легко помітити, що граф залежностей за даними є орієнтованим ациклічні графом. Це пояснюється тим, що цикли в DDG означають наявність циклічних залежностей за даними, можливі, в свою чергу, тільки в операторах циклу вихідної програми. Але цикли, як і інші складні оператори, розкриваються на більш низькому рівні ієрархії, забезпечуючи розрив таких залежностей за даними. Ця властивість графа буде використовуватися нами в подальшому.

Приклад функції та її графа залежностей за даними наведено на Рис. 1. DDG складається з трьох вузлів: двох простих вузлів і оператора циклу, що розкривається в DDG другу рівня.

Граф залежностей за даними будується для кожної функції програми. Алгоритм побудови складається з наступних етапів:

Побудова графа потоку управління програми.

Вибір програмних блоків, які будуть вузлами поточного рівня ієрархії DDG.

Знаходження залежностей за даними між цими вузлами за допомогою алгоритму досягають визначень.

Якщо необхідно, просунутися на наступний рівень ієрархії і добудувати граф.

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

2.1.2. Цінова модель

Нашої метою є побудова розбиття програми на нитки, максимально використовує виникають події локальності. Щоб мати можливість судити про ступеня оптимальності того чи іншого розбиття, необхідно ввести деяку модель ціноутворення. Так як ми оптимізуємо час виконання програми, то природно ввести ваги вузлів графа залежності за даними, рівні часу виконання вузла в послідовній програмі.

Час виконання вузла може бути знайдене за допомогою профілювання програми. Для цього необхідно інструментіровать вихідний код програми, вставляючи виклики функцій з бібліотеки підтримки, вираховувати час виконання інструкцій, і виконати програму на декількох наборах типових вхідних даних. Для отримання більш точних результатів можна скористатися високоточними апаратними лічильниками, наявними на більшості сучасних архітектур (наприклад, інструкцією RDTSC для Pentium III і вище). Ця оцінка часу виконання точно показує реальний час виконання програми, але утруднює емуляцію кешу на етапі поділу на нитки, тому що складно визначити, наскільки зменшиться час виконання вузла при попаданні в кеш (можливо, за профілюванні це попадання вже відбулося).

Цінова модель повинна також відображати події локальності, що відбуваються під час виконання програми. Статичних ваг для вузлів DDG для цієї мети недостатньо. Необхідна емуляція кеша в процесі поділу на нитки і відповідна коректування часу виконання вузла.

2.1.3. Розбиття на нитки

На цьому кроці проводиться власне розбиття графа залежностей за даними на нитки. Кількість ниток є параметром алгоритму. Так як метою розбиття є отримання виграшу за часом, що виникає через збільшення кількості подій локальності в кожній нитки, то необхідно прив'язати кожну нитка до одного конкретного процесора або, точніше, до конкретного кешу. Тому кількість ниток, на які проводиться розбиття, зазвичай дорівнює кількості процесорів в системі.

Алгоритм розбиття полягає в Ітерірованіе списку вузлів графа, ще не призначених конкретної нитки, і визначення нитки для будь-якого з вузлів (групи таких алгоритмів зазвичай називаються list scheduling). На кожному кроці такий алгоритм робить локально оптимальний вибір. Це означає, що при виборі чергового вузла зі списку робиться спроба привласнити його кожної з наявних ниток, після чого вибирається найкраща.

Для того, щоб мати можливість оцінювати варіанти присвоєння вузла нитки, необхідно ввести деяку оціночну функцію. У нашому випадку така функція містить час виконання нитки, а також середньоквадратичне відхилення часів виконання всіх ниток. Це випливає з того міркування, що в оптимальному розбивання часи виконання ниток повинні бути досить близькі один до одного. Можливе включення та інших параметрів.

При включення вузла в будь-яку нитку необхідно провести перерахунок вре-мени виконання цієї нитки. Алгоритм перерахунку складається з наступних кроків:

Облік часу, необхідного на синхронізацію з іншими нитками, якщо вона потрібна.

Облік що виникають подій локальності.

Розглянемо більш детально кожен з цих кроків.

2.1.3.1. Облік часу на синхронізацію

Оброблювані на поточному етапі вузол може залежати за даними від деяких інших. У цьому випадку необхідно дочекатися виконання кожної нитки, які містить такі вузли. Порядок обходу вузлів у списку має бути такий, щоб гарантувалося, що всі такі вузли вже були розподілені на нитки. Для цього можна обходити вузли в природному порядку, тобто так, як вони розташовані в послідовній програмі, або виконати Тополя-ня сортування графа залежностей по даними. Ще раз підкреслимо, що ієрархічність графа забезпечує те, що він є ациклічні.

Таким чином, на момент обробки деякого вузла всі вузли, від яких він залежить по даними, вже розподілені на нитки. Якщо які-небудь з таких вузлів знаходяться в інших нитках, то перед виконанням поточного вузла необхідно провести синхронізацію з усіма такими нитками. Для того, щоб здійснити таку синхронізацію, потрібно завести за однією загальною змінної для кожної нитки. Присвоєння значення i такої змінної для деякої нитки j означає, що ця нитка виконала вузол i. Нитка, що чекає результатів обчислення вузла i, повинна чекати, поки відповідна загальна мінлива не прийме потрібного значення. Приклад такої синхронізації показаний на Рис. 2.

Часи виконання кожної з ниток, які проводять синхронізацію, повинні бути збільшені відповідним чином. Нитка, що пише в загальну змінну про результати виконання вузла, додатково працює час t1. Нитка, що чекає даних від декількох вузлів, очікує останній з виконуються вузлів, після чого витрачає час t2. Ці часи є параметрами алгоритму.

Рис. 2. Приклад сінзронізаціі

Для обліку подій локальності для кожної нитки необхідно емулювати кеш процесора, на якому вона виконується. При розподілі поточного вузла на будь-яку нитку необхідно перевірити всі змінні, які читаються або пишуться вузлом, на потрапляння в кеш. Якщо попадання відбулося, то час виконання вузла повинно бути зменшено на інтервал часу t3, що також є параметром алгоритму.

Рис. 3. Приклад емулювання кеша

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

Приклад моделювання подій локальності зображений на Рис. 3.

2.2. Експериментальні результати

Ми застосували нашу реалізацію алгоритму до тестової ф?? нкціі, що вирішує алгебраїчне рівняння четвертого ступеня x4 + ax3 + bx2 + cx + d = 0.

Функція не містить циклів і не може бути распараллелена традиційними способами. Отримана багатопотокова версія функції була реалізована за допомогою бібліотеки pthread під операційною системою Linux. Експериментальні запуски були проведені на чотирипроцесорні Intel Itanium, на яких встановлена ОС RedHat Linux 7; використовувалися компілятори GCC 3.3.1 та ICC 8.00b. Програма запускалася 100 раз, час її виконання вимірювався за допомогою високоточних апаратних лічильників. Обчислювалося середнє значення часу виконання