Національний технічний університет України

"Київський політехнічний інститут"

КУЙВАШЕВ Дмитро Васильович

УДК 681.3.06

МЕТОДИКИ ПЕРЕНАЦІЛЮВАНОЇ ГЕНЕРАЦІЇ КОДУ

ДЛЯ МІКРОПРОЦЕСОРНИХ АРХІТЕКТУР

З НЕРЕГУЛЯРНИМ ДОВГИМ КОМАНДНИМ СЛОВОМ

01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Київ — 2002

Дисертацією є рукопис.

Робота виконана в Інституті програмних систем НАН України.

Науковий керівник: доктор фізико-математичних наук

ДОРОШЕНКО Анатолій Юхимович,

Інститут програмних систем НАН України,

заступник директора з наукової роботи

Офіційні опоненти: доктор технічних наук, професор

ПОГОРІЛИЙ Сергій Дем’янович,

Київський національний університет імені Тараса Шевченка,

заступник завідувача кафедри напівпровідникової

електроніки,

кандидат технічних наук, доцент

ПУСТОВАРОВ Володимир Ілліч,

Національний технічний університет України "Київський

політехнічний інститут", доцент кафедри обчислювальної техніки

Провідна установа: Інститут проблем моделювання в енергетиці імені Г. Є. Пухова

НАН України, відділ спеціалізованих засобів моделювання, м. Київ

Захист відбудеться "11" листопада 2002 р. о 14:30 годині на засіданні спеціалізованої вченої ради Д 26.002.02 при Національному технічному університеті України "Київський політехнічний інститут" за адресою: 03056, Київ_, пр. Перемоги, 37, корп.  ауд. 306.

З дисертацією можна ознайомитися в бібліотеці НТУУ "Київський політехнічний інститут".

Автореферат розісланий "07" жовтня 2002 р.

Учений секретар

спеціалізованої вченої ради ОРЛОВА  М.М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась у рамках плану фундаментальних наукових досліджень Інституту програмних систем НАН України за темами Ф3/02-99 "Дослідження теорії та методів паралельної обробки в мультиагентних системах на основі алгебродинамічних моделей обчислень" та 3/02-02 "Розробка теорії та методів програмування високопродуктивної обробки в метакомп'ютерних системах на основі координаційних моделей обчислень", а також в рамках договору про наукове співробітництво між Інститутом програмних систем НАН України (Київ) та Інститутом систем інформатики Сибірського відділення РАН (Новосибірськ).

Мета і задачі досліджень у дисертаційній роботі. Мета роботи –підвищення ефективності генерації коду для мікропроцесорів (МП) з нерегулярним довгим командним словом (у тому числі проблемно-орієнтованих) за допомогою розробки методик, методів та алгоритмів перенацілюваної генерації коду. Об’єктом дослідження є методи, алгоритми та методики розробки ефективного перенацілюваного програмного забезпечення для новітніх мікропроцесорних платформ. Предмет дослідження – методи, алгоритми та методики генерації оптимізованого коду в процесі компіляції для проблемно-орієнтованих мікропроцесорів з нерегулярним довгим командним словом. Методи дослідження – теорія графів, формальні методи опису архітектури мікропроцесорів та програм, методи, використовані у експертних системах та методи математичного аналізу. Поставлена мета визначила наступні завдання для її досягнення:

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

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

3. Удосконалення алгоритмів розподілу регістрів та розробка методів та методик генерації коду.

4. Розробка методу аналізу придатності мікропроцесорних архітектур до вирішення конкретних прикладних завдань.

5. Розробка мови опису цільової мікропроцесорної архітектури та експертних знань на базі тегової моделі мови розмітки гіпертексту XML.

Наукова новизна одержаних результатів:

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

2. Створено метод формалізації експертних знань у вигляді продукцій експертної системи для подальшого застосування у процесі інтелектуальної оптимізації, який дозволяє поліпшити характеристики генерації коду. Метод підтримується механізмом застосування експертних знань у процесі генерації коду за допомогою продукційної експертної системи.

3. Удосконалено методи й алгоритми розподілу регістрів, засновані на методі перетину графу потоку даних та запропоновано методи генерації розкладу команд для новітніх мікропроцесорів з архітектурою з довгим командним словом та великим кластеризованим регістровим файлом.

4. Запропоновано метод ітеративної оптимізації й генерації коду та метод вибору найліпшої мікропроцесорної архітектури для вирішення конкретних завдань користувача.

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

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

Достовірність результатів підтверджено експериментально – на базі запропонованих методів розроблено прототип перенацілюваного налагоджуваного компілятора НВРК-2 для МП цифрової обробки сигналів та МП з довгим командним словом, що дозволяє ефективно генерувати оптимізований код для однієї з поширених на ринку проблемно-орієнтованих мікропроцесорних архітектур ADSP-2106x SHARC. Досягнуті результати дають змогу будувати ефективні промислові версії перенацілюваних компіляторів на основі описаних у дисертаційній роботі методів.

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

Апробація роботи. Основні результати наукової роботи представлялися на 3-й Міжнародній науково-практичній конференції з програмування УкрПрог-2002, наукових семінарах Інституту програмних систем, Інституту кібернетики ім. В. М. Глушкова НАН України (2001-2002).

Публікації. За результатами дослідження опубліковано 6 наукових робіт, у тому числі 5 в українських наукових фахових журналах та одна як матеріали конференцій.

Структура та обсяг роботи. Робота складається з вступу, чотирьох основних розділів, висновків, трьох додатків та списку використаної літератури з 120 найменувань. Загальний обсяг роботи – 147 друкованих сторінок.

ЗМІСТ РОБОТИ

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

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

У перших двох пунктах розділу розглядаються сучасні мікропроцесорні архітектури (МП з довгим командним словом та МП цифрової обробки сигналів) та методи підвищення швидкодії МП за допомогою використання наявного у програмах паралелізму різних видів. Подається огляд класичних оптимізуючих перетворень, які використовуються для оптимізації процесу обчислень у програмі, та специфічних оптимізацій для процесорів цифрової обробки сигналів (ПЦОС).

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

Перенацілюваний компілятор (ПК) оперує як з програмою, так і з описом цільового МП у вигляді ресурсів пам’яті та можливих трансформацій змісту ресурсів. Перенацілюваність компілятора дозволяє: 1) отримати компілятор для нового МП лише за допомогою зміни формального опису цільового МП; 2) одночасно з розробкою МП отримати готовий компілятор. Недоліком перенацілюваних компіляторів на сьогодні є досить невеликі можливості опису цільової архітектури та залежність від ступеню регулярності її структури.

У розділі наведено огляд проектів з розробки новітніх методів перенацілюваної компіляції: а) систем одночасної розробки апаратного та програмного забезпечення (наприклад, система MIMOLA П. Марведела); б) перенацілюваних компіляторів загального призначення (система RECORD Р. Лейперса). Розглянуто формалізми, за допомогою яких розробляються описи цільового процесора – ISDL, nML та інші, також найбільш значні розробки (IMPACT, Trimaran, SUIF) компіляторів, створюваних для МП, підтримуючих суперскалярний паралелізм.

За результатами огляду зроблено важливі висновки. По-перше, існуючі компілятори краще пристосовані до регулярних архітектур МП, а сучасні ПЦОС характеризуються саме нерегулярністю архітектури. По-друге, для підвищення ефективності коду компілятори для таких архітектур потребують інтелектуальних процедур оптимізації з застосовуванням у процесі компіляції евристичних знань про процедури оптимізації та генерації коду, які безпосередньо не можна вивести з опису апаратної частини мікропроцесора.

У другому розділі роботи запропоновано формалізми для опису вхідної програми за допомогою ієрархічних графів та оптимізуючі перетворення програм у вигляді графових продукцій.

Ієрархічна графова модель запропонована В.А. Євстигнєєвим та В.М. Касьяновим для подання структури програми при її обробці компілятором. Ієрархічним графом (ІГ) називається двійка H=(G,T), де G – граф, T – кореневе дерево, вершини якого відповідають елементам деякої ієрархії в G. T називається деревом вкладеності H, а G – основним графом H. Для будь-якої вершини pT максимальне піддерево T з коренем p позначається T(p), а G(p) – фрагмент основного графа G, відповідний p, H(p)=(G(p),T(p)) – ієрархічний підграф H, асоційований з вершиною p. Поданням графової моделі програми є ІГ H=(G,T), де кожна вершина pT відповідає деякому підграфу основного графа G. T називається вершинним деревом вкладеності, вершини T відповідають певним підмножинам G. Вводяться мітки – множина об’єктів V, яка розпадається на попарно непересічні підмножини класів міток. Визначається множина об’єктів-"типів" міток W, для wW поставлена у відповідність множина міток V(w)=Vi1Vi2…Vis, де VijV – деякий клас міток для будь-якого j.

Ієрархічна графова модель (ІГМ) є трійка (H,M,L), де H – ієрархічний граф, M – функція типу, яка приписує кожному елементу (вершині, ребру і фрагменту) h ієрархічного графа H його тип M(h)W, а L – функція міток, яка приписує кожному елементу h графа H його мітку – деякий елемент L(h)V(M(h)). Семантична частина графової моделі задається за допомогою системи перетворень графових моделей, що зберігають їх еквівалентність (еквівалентних перетворень).

Графова граматика складається з множини правил (графових продукцій), які можуть ітеративно застосовуватися до графа, роблячи звичайно його локальні перетворення. Графова продукція є четвіркою (L,R,E,C), де L і R – два графи, які називаються лівою та правою частинами продукції, E – деякий механізм вбудовування, C – умови застосування продукції. Продукція p застосовується до оброблюваного графа G наступним чином:

1) знаходимо входження лівої частини L в G (за виконання умови застосування C);

2) видаляємо частину графа G, визначену вказаним входженням L, для одержання контекстного (або залишкового) графа D;

3) вбудовуємо в D праву частину (копію) R за допомогою механізму вбудовування E і отримуємо виведений граф H.

Вершини ІГ функцією типу M(h) поділяються на два основних класи: 1) перетворювачі, які мають не більш однієї вихідної дуги та являють собою одну або декілька інструкцій присвоєння значення змінній або виклику підпрограми; 2) розрізнювачі, що мають більш одного можливого наступника по керуванню, але не змінюють стан пам’яті (окрім змінних-лічильників), являють собою умовний оператор, оператор вибору, циклічні конструкції. На рис. 1 показано приклад структури гіпотетичної підпрограми x1 та її ІГМ (білим кольором показано перетворювачі, чорним — розрізнювачі).

Рис. 1. Приклад ієрархічної графової моделі.

Кожний перетворювач являє собою ІГ Hb(Tb,Gb), де дерево вкладеності Tb є променем; граф Gb є незв’язаним та складається з множини ациклічних орграфів Defi, (дерев), які визначають присвоєння. Кожен орграф Defi зіставлений деякій вершині Tb. Граф Hb – відображення лінійної ділянки програми, до якої не входять умовні або безумовні переходи, — базового блоку (ББ).

Орграфи, які визначають присвоєння, позначаються за допомогою дужкового запису Def(Var, Exp), де Var – змінна, яка присвоюється, Exp – значення виразу, яке присвоюється, Exp=Opn(Exp1,…,Expn)|Vari|Consti, де Opn – n-арна операція, Vari – змінна, Consti – константа. Вводиться множина змінних програми VAR={vari} та множина констант CONST={consti}. Вводяться множина типів (як базових, так і композитних) TYPES={typei}. Для множин VAR та CONST вводиться функція t=Type(vari|consti), tTYPES, яка повертає тип змінної або константи.

Дерево вкладеності ІГ програми визначає зв’язки по керуванню.

За допомогою перетворювачів відображаються зв’язки за даними в базових блоках. Скалярний оператор Si виконується раніше скалярного Sj (позначається SiSj), якщо оператор Si лексично передує Sj (i<j). Через OUT(Si) позначається множина екземплярів змінних, які модифікуються оператором Si, через IN(Si) — множина екземплярів змінних, які використовуються тим же оператором. Оператори Si та Sj знаходяться у потоковій залежності SiSj, якщо справедливі дві умови:

1) SiSj;

2) OUT(Si)IN(Sj).

Антизалежність між Si та Sj (позначається SiSj) визначається аналогічно потоковій, але умова (2) має вигляд IN(Si)OUT(Sj). Залежність за виходом між Si та Sj (позначається SiSj) визначається аналогічно потоковій, але з умовою (2): OUT(Si)OUT(Sj). На базі введених формалізмів розглядаються оптимізуючі продукції (оптимізації) для ББ і для глобальної оптимізації. При створенні ІГМ після локальних оптимізацій в графах ББ залишаються лише потокові залежності.

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

1. Поширення констант – посилання на змінну, яка дорівнює константі, замінюється на константу

Li iSi jDef(di,ConstK) jSi,ConstK).

2. Алгебраїчні спрощення, являють собою велику кількість продукцій типу

L = {'+','–'}(vari,0); R = ( vari ); для перетворення x+0x, x-0x.

3. Для видалення повторюваних виразів використовується наступний метод. Нехай існує L = Op(…,…), та Si, Sj, такі, що SiSi, LSi, LSj. Продукція вставляє новий оператор R=SR=Def(varTEMP,L), так що для будь-якого SkSi виконується SkSR і SRSi. Входження L в операторах Si і Sj заміняється на змінну varTEMP.

Усі розглянуті в роботі продукції для оптимізації ББ є машиннонезалежними.

Для застосування оптимізуючих продукцій у процесі глобальної оптимізації використовується аналіз потоку даних. Для ББ B вводиться функція передачі (ФП) FB(vari), де vari – будь-яка змінна, яка відображує значення змінної vari після виконання ББ. Результатом відображення є вираз у символьному вигляді – значення var-i- як функція від значень певних змінних перед початком виконання ББ.

Вводиться оператор композиції над двома ФП FB1(vari) та FB2(vari), нова ФП FB1B2(vari)=FB1(vari)FB2(vari) являє собою ФП – результат послідовного виконання базових блоків B1 та B2. Вводиться оператор перетину над двома ФП FB1(vari) та FB2(vari), нова ФП FB1B2(vari)=FB1(vari)FB2(vari) робить відображення тільки для тих змінних, які будуть змінені незалежно від того, який ББ – B1 або B2 буде виконаний. Для позначення виклику підпрограми використовується функція відображення FCALL(var1,…,varn,var), де vari – фактичні параметри процедури, n – їх кількість, var – змінна, для якої будується ФП. Для циклічної конструкції C вводяться дві ФП: ітерація FCI(vari) та замикання FC*(vari), де vari – скалярна змінна. Функція FCI(vari) вертає значення vari після виконання i ітерацій циклу, функція FC*(vari) – після виконання усіх ітерацій циклу (лише якщо відома кількість операцій або змінна не змінюється в тілі циклу), функції застосовуються до циклів, в яких розпізнана індексна змінна (змінна, яка лінійно залежить від номера ітерації циклу). Для оптимізації циклу використовуються визначення та видалення індексних змінних, пошук агрегативних змінних, які створюють міжітераційні залежності, чистка циклу від зайвих обчислень, пошук та видалення циркулярних змінних (що практично не реалізовано в штатних компіляторах для ПЦОС), перетворення виразів доступу до елементів масиву.

При аналізі виразів доступу до масивів використовуються продукції (L,R,E,C) вищезазначеним способом. Для кожної вершини p дерева T графа процедури H, якщо її тип M(p) є "цикл", проводиться аналіз підпорядкованого ІГ. Застосовуються декілька типів продукцій: 1) ті, які виділяють індексні та охоплюючі змінні (лінійно залежні від індексу циклу); 2) ті, які виділяють редукції; 3) ті, які перетворюють вирази доступу (індексні вирази) до елементів масивів.

Зокрема, індексні змінні з довільним кроком виділяються за допомогою продукції:

(varIDX,Op1(varIDX,ConstExp)) (varIDX)="ціле"  

FCC(ConstExp)="так",
де varIDX — необхідна індексна змінна, Op1={'+','–'}.

ФП "ітерація" для індексної змінної з довільним кроком має вигляд FCI(varIDX)=Ai+B, де A та В – константи, i – номер ітерації циклу.

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

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

У третьому розділі дисертації формалізовано опис цільової архітектури МП, опис знань про оптимізацію коду для цільової архітектури та запропоновано поліпшені методи, методики й алгоритми генерації коду для ПЦОС та мікропроцесорів з довгим командним словом (МП з ДКС).

Опис мікропроцесора складається з опису ресурсів та системи команд.

Базовими для опису ресурсів є регістри rgi та простори пам’яті MI. Регістри об’єднуються у регістрові регіони TRI={rgi}, банк регістрів є множиною регістрових регіонів RI={TRI}. Всі регістрові банки об’єднуються у множину R*={RI} регістрових банків. Визначається множина всіх просторів пам’яті M*={MI}. Вводиться множина типів даних, операції над якими апаратно реалізовані у МП: RTYPES, та функція перетворення TRT: TYPES , що відображає тип даних мови високого рівня у внутрішній апаратно підтриманий тип.

Для інструкцій МП вводиться множина атомарних команд AA*={I }. Атомарна команда визначена двійкою LAI = (AK, KG), де AK – множина локальних атрибутів команди (ідентифікатор, час та вартість виконання, змінювані прапорці, зв’язувані функціональні пристрої), KG – орграф команди, що подає функцію передачі команди. Для визначення функціональних пристроїв вводиться множина FU*={I }, кожний FUI має атрибути, які описують його апаратні характеристики. Атомарні команди об’єднуються в списки атомів (аналог вертикального кодування мікрокоманд в МП). Множина списків атомів визначається як LA* = {I }, за один раз може бути виконаний лише один елемент LAI, LAI = { AJ }, LAIA*, ¦LAI¦1. Всі атомарні команди AJLAI виконуються одночасно (аналог мікрогоризонтального кодування в МП).

Довгі команди (ДК) формуються з списків атомів. Множина ДК K*={ KI }, KI = ( KGI-, { (KAI, LAJ) } ), де KGI — спільний атрибут команди (наприклад, предикатне виконання ДК); {КАI, LAI) } — множина можливих секцій ДК, де KAI — атрибут секції ДК (окремий предикат, опціональність команди та інше), LA-I —виконуваний список атомів (секція ДК), ¦{КАI,I) }¦1. Якщо цільовий МП має інструкції класу "ОКМД в регістрі", коли довгий регістр (64-128-256 біт) поділяється на поля однакової ширини, над якими протягом одного такту виконується одна й та ж операція як над незалежними регістрами (як Intel MMX або SSE), такі інструкції природно описуються запропонованим формалізмом.

Інтелектуалізація генерації коду. Для ефективної роботи генератора коду компілятора необхідна інформація про загальні принципи генерації коду для цільового МП. Жодна обчислювальна система не може бути використана без наявності розроблених методів (знань) про її застосування у конкретному випадку. Термін "знання" використовується для позначення евристик, якими керується програміст-експерт при розробці програми мовою низького рівня. Експертні знання не є певною системою – кожне з правил (подане у формі "якщо-то") виконується за певних умов, часто окремо від інших правил.

Назвемо сукупність експертних знань експертними продукціями, позначимо їх множину як NPr*={I }, де PrI – певна експертна продукція, яка є четвіркою PrI=( NameI, DefI, CondI, ExecI), де NameI – ім’я продукції, DefI – значення по умовчанню, CondI – умова застосування продукції, ExecI – дії, що виконуються при істинності умови застосування продукції. Експертна продукція аналогічна продукціям продукційної експертної системи, але на відміну від останньої, де сукупність продукцій є цілісною інформаційною системою, експертні продукції в компіляторі обслуговують незалежні один від одного випадкі генерації коду.

Множина продукцій розширювана, але як мінімум, до неї належать такі типи:

1. Множина експертних змінних, кожна з яких має вигляд (Name, Value, , ), де Name – ім’я змінної, за яким відбувається доступ, Value – значення змінної; наприклад ("є предикатно виконувані команди", "так", , ).

2. Графові трансформації – оптимізуючі машинно-залежні перетворення, часто перетворення виразів на одну операцію МП – (Name, , , G), де Name – ім’я продукції, G – графова продукція. Наприклад, обчислення абсолютного значення суми: L=call(ABS(int,int) ( {'+'}(vari,j)); R= { 'ABS'(vari,varj).

3. Шаблони й макроси – перетворюють певні складні операції (отримання квадратного кореня, тригонометричні функції) у серію простіших операцій. Макрос визначається як (Name, , , G), де G – графова продукція з лівою частиною L=Op(x1,…,xn), де Op – замінювана операція, xj – операнди, та правою частиною R=fOp(x1,…,xn), де fOp – вираз, яким замінена операція Op, xj – ті ж самі операнди. Для більшості МП Op={ '/', '','1/x','1/' }.

4. Таблиці порад. Для генерації коду часто необхідно формувати таблиці, в яких перелічені процедури генерації коду, наприклад при звертаннях до складних структур даних або генерації кадру стеку. Таблиця порад визначається як (Name, , Cond, Table), де Name – ім’я продукції, Cond – вираз, який визначає номер поради у таблиці, Table – таблиця порад (G1, G2, …,Gn), кожна з яких є графовою продукцією, або оптимізуючою машиннозалежною продукцією, або макросом.

5. Множина прагм – вказівок програміста компілятору. Аналогічні експертним змінним, але їх значення може змінюватися під час компіляції програми за бажанням програміста.

Архітектура цільового МП повністю визначається як P={ M*, R*, TR*, RTYPES, AA*, LA*, K*, FU*). Знання про оптимізацію програми та генерацію коду уніфіковано описані множиною NPr*. Під формальним описом архітектури цільового процесора визначимо двійку D=( P, NPr*), яка повністю визначає поведінку ПК при генерації коду та архітектуру цільового МП.

Основні етапи генерації коду. Процес генерації коду для базового блоку складається з трьох етапів: 1) вибір інструкцій цільового МП – зіставлення певної інструкції операції з певного виразу; 2) розподіл регістрів – розміщення змінних у регістрах найефективнішим способом; 3) складання розкладу інструкцій – формування коду ББ з вибраних інструкцій з найменшим часом виконання.

Вибір інструкцій для зіставлення з ІГМ програми відбувається за допомогою повного покриття орграфа ББ графами команд одночасно з розподілом регістрів та складанням розкладу інструкцій. У процесі зіставлення для кожної змінної variVAR визначається її розміщення в пам’яті та множина регістрів для зберігання, виконуються оптимізації для зіставлення комбінованих та суміщених команд. Вводиться функція RT(t), де tRTYPES, RT(t)={ TRi }, ||{ TRi}||1, яка зіставляє апаратному типу МП множину регістрів МП, до яких його може бути завантажено (змінні можуть бути завантажені у декілька регіонів регістрів). Коли змінна є редукцією, їй зіставляються акумуляторні регістри, які оперують з подвійною точністю. Далі кожній команді ББ зіставляються всі можливі інструкції МП. Якщо існують різні інструкції, які виконують одну операцію, але над різними типами регістрів, то команді зіставляються всі можливі інструкції. Із зіставлених інструкцій при складанні розкладу команд вибирається лише одна оптимальна.

Більшість арифметико-логічних інструкцій МП не можуть оперувати безпосередньо із значеннями у пам’яті, тому компілятор генерує послідовність команд для завантаження значень змінних у регістри. Визначається час життя копій змінних пам’яті, розташованих у регістровому файлі в певний час – регістрових змінних (РЗ). У сучасних моделях МП з ДКС та ПЦОС ємність регістрового файла сягає 64 – 256 регістрів. При кількості одночасно виконуваних операцій у ДК від 4 до 8 (або більше) можливість подачі даних з пам’яті до регістрів обмежена. За такт може оновитися лише від 1/16 до 1/32 регістрового файла. Для сучасних МП проблема подачі даних до регістрів є критичною і необхідна розробка поліпшених методів розподілу регістрів, які дозволяють ефективно використовувати великі регістрові файли сучасних МП.

Аналогічно функціям передачі даних вводяться функції передачі регістрових змінних.

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

Орграф ББ визначається двійкою Kb=(Vb,Eb), де V={ vi} – множина вершин двох типів, які являють собою віртуальні регістри та команди, E – множина орієнтованих ребер, які є зв’язками за даними, E= {k }, ek=(i,j). На орграфі вводиться функція зв’язності fc=VV { ,1 }, і функція розмітки вершин fT(v){ресурс",команда"},vV. Вводиться обов’язкова умова: якщо fc(vi,j)=1, то fT(vi)fT(vj). Для Kb=(Vb,Eb) вводиться фіктивна початкова вершина v0, fT(v0)="команда", та дуги e=(v0,vi) для всіх vi, з fT(vi)="ресурс", та не існує такого vV, що fT(v)="команда", viOUT(v). Аналогічно вводиться кінцева вершина vE. Для Kb вводяться метрики: 1) v – довжина шляху з початкової вершини v0 у вершину v; 2) v – довжина шляху з вершини v у кінцеву вершину vE; 3) lij – довжина шляху з вершини vi до вершини vj; 4) b – довжина всього Kb (довжина шляху з v0 в vE). Для ek=(vi,vj), fT(vj)="команда", lij=0, а для em=(vi,vj), де fT(vj-)="ресурс", lij визначається часом виконання команди vj.

У процесі генерації коду для кожного ББ запроваджено час t, який при генерації коду для початкової вершини ББ дорівнює 0 та зростає на 1 з кожною згенерованою ДК. У циклі генерації довгої команди для Kb проглядаються готові до виконання команди (з доступними у регістрах операндами) viV. Із зіставлених операціям ББ інструкцій МП визначається множина LA'={m }, виходячи з якої довга команда Ki має максимальну функцію оцінки як суму шляхів атомарних команд cbest(LA')=I, де i – шлях до кінцевої вершини цієї команди. Для МП з ДКС на формування множини LA' впливає інформація про наявність вільних функціональних пристроїв FU*.

Розподіл регістрів. Метод розподілу регістрів впливає як на час виконання скомпільованої програми, так і на час компіляції програми. На сьогодні відомо декілька методів розподілу регістрів: розфарбування графа, аналіз графу потоку даних або вирішення задачі методами цілочисельного програмування. Традиційним методом є розфарбовування вершин-ресурсів vi графа ББ KB(VB,EB) у мінімальну кількість кольорів, кожний колір зіставляється з певним регістром регістрового файла (РФ). Метод має експоненціальну складність від кількості змінних у ББ, та тільки мінімізує потребу в апаратних регістрах, але не вирішує проблему ефективного використання великого регістрового файла сучасних МП.

Альтернативним до розфарбовування графів є використання евристичних алгоритмів, наприклад сканування орграфа ББ вперед при складанні спискового розкладу. Такий метод є реалізацією методу перетину графа потоку даних, запропонованого А.П. Єршовим, який мінімізує потребу в комірках пам’яті для зберігання значень. Метод не використовує алгоритми експоненційної складності, які значно погіршують часові характеристики за мінімального збільшення ефективності алгоритму. Основною рисою алгоритму є ефективність як для простих RISC-МП, так і для ПЦОС та МП з ДКС і суперскалярних процесорів.

Для використання у МП з простими та кластеризованими регістровими файлами запропоновано метод, заснований на евристиці пошуку на графі потоку даних. Для деякого моменту часу t при обробці орграфа ББ KB=(VB,EB) генерується ДК на базі визначеної множини LA'. Визначається поточний стан регістрової пам’яті як RGB={rgi}. Вибирається max — максимальне i для LAiLA', та min – мінімальне i для LAiLA'. Позначається максимальний час виконання команди, вводяться кількість регістрів NB=||RGB||, кількість вільних регістрів (вводиться атрибут для rgi: emp-I="вільний", якщо регістр не зайнятий значенням) NBE=||ERGB={rgi |i="вільний" }||. Вводиться атрибут inmemi={"так","ні"} для кожного rgi, який позначає, чи збігається значення змінної в регістрі й в відповідній комірці пам’яті (тобто чи потрібно зберегти значення у пам'яті), кількість таких регістрів є NBM=||MRGB={rgii="ні"}||. Розглядаються всі змінні viV, такі що minimax+C*, де 1C2 – змінні, задіяні при генерації ДК, які будуть формуватися в найближчий час (до С). Множина таких змінних позначається через VC, а реальний регістр, який відповідатиме vi – rgi. Для viVC та відповідним їм rg'iRGB послідовно під час генерації наступних ДК вивільнюються регістри, які містять змінні, що в найближчий час не знадобляться для здійснення операцій –"найбільш непотрібні значення".

Визначається множина CRGB=RGB-(SRGBMRGB) як множина змінних, продубльованих в регістрах. Знаходиться мінімальне I – час до найближчого звернення до значення, для всіх rg'iCRGB за допомогою простого перегляду вершин KB. Якщо деякі rg'i не зустрічаються в KB, то розглядаються всі наступники KB за керуванням. Якщо даний rg'i зустрічається в декількох наступниках, його i визначається так: B+min(i1,i2,…,in), де ij – знайдене i в j-му наступнику. В разі незнаходження rg'i в одному з наступників ББ B, процедура рекурсивно повторюється для цього наступника B, але якщо шлях від B до поточного ББ не перевищує мінімуму з вже обчислених значень i в інших базових блоках. Кожному rg'i зіставляється i – мінімальна відстань до наступного застосування змінної в rg'i. Після визначення i для всіх регістрів за необхідності вивільнення регістра визначається max=max(i) і для rg'i з i =max змінюється empi на значення "вільний". Метод розподілу регістрів у загальному випадку складається з таких правил:

1) якщо ||VC||>NBE та ||CRGB||<||VC||-NBE (нестача регістрів та більшість регістрів треба вивантажити у пам’ять) і в формованій ДК немає команди завантаження значення у регістр, в цю ДК необхідно вставити вивантаження rgiMRGB з максимальним часом i та вивільнити для нових змінних регістри, які зберігають найбільш непотрібні значення;

2) якщо ||VC||>NBE та ||CRGB||>||VC||-NBE (нестача регістрів, але можливо вивільнити деякі без вивантаження у пам’ять) можливо вивільнити регістри з найбільш непотрібними значеннями;

3) якщо ||VC||NBE (вистачає вільних регістрів), то можливе зайняття вільного регістра;

4) в іншому випадку, якщо завантаження каналу "регістри-пам’ять" було дуже щільним, необхідно: а) виконувати лише команди, в результаті виконання яких можливе вивільнення регістра, для якого час до найближчого звернення до збереженої в ньому змінної максимальний щодо інших змінних; б) вивантажити у пам’ять rg'iMRGB з максимальним часом i.

Урахування особливостей архітектури ПЦОС у генераторі коду. Для поліпшення якостей генерації коду для сучасних ПЦОС та МП з ДКС запропоновано наступні поліпшення:

1. використання реверсивної генерації розкладу команд (як з початкової вершини, так і з кінцевої) для застосування відкладених переходів;

2. застосування предикатних операцій для організації трас ББ;

3. впровадження генерації коду для двох послідовних ББ одночасно для використання команд, які включають у себе команди суміжних ББ;

4. використання кластеризованих регістрових файлів за допомогою віртуальних регістрів (розподілу з урахуванням структури РФ), регістрових регіонів та ітеративних уточнень з відкоченнями;

5. кластеризація команд ББ для випадків переключення режимів обчислень;

6. вирізнення операцій каналу "пам'ять-регістри" з ББ та рівномірний розподіл інструкцій завантаження/вивантаження регістрів по ДК генерованого ББ (спекулятивне завантаження змінних для більш ефективного використання каналу "регістри-пам’ять).

Програмна конвеєризація та визначення оптимальної структури МП. В прикладних завданнях часто необхідно оптимізувати виконання циклів, час виконання яких займає від 20 до 80 відсотків часу виконання усієї програми. Якщо є можливість вибору з декількох МП, то необхідно визначити який з них найшвидше виконає програму, або визначити оптимальну архітектуру гіпотетичного МП, який може було зроблено за допомогою програмованих логічних матриць. Для цього запропоновано використовувати метод програмної конвеєризації EPS К. Ебчоглу, який виділяє оптимальний програмний конвеєр для процесора з необмеженою кількістю ресурсів, удосконаливши метод для цільових МП з реальними архітектурними обмеженнями. Разом з ітеративною процедурою розгортки циклів метод дозволяє відшуковувати оптимальні програмні конвеєри для процесорів, результати генерації конвеєра можуть бути порівняні між собою для визначення кращого варіанту.

Ітеративна компіляція. Для оптимізації розміщення змінних по просторах пам'яті для гарвардської архітектури та кластеризації розміщення змінних запропоновано аналіз статистичної інформації про конфлікти при доступі до пам'яті (можливість вибору при генерації коду однієї з декількох команд доступу до пам’яті з однаковою функцією оцінки). Ця інформація є множиною MC={(i,j)N }, де mc(i,j) – кількість конфліктів між змінними vari та varj. За кожного конфлікту зовні тіла циклу значення mc(i,j) збільшується на 1, в разі конфлікту в тілі циклу значення збільшується експоненціально за глибиною вкладення тіла циклу. Пари змінних, які мають найбільші значення конфліктів, розміщуються по різних просторах пам’яті.

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

У четвертому розділі дисертації описано методики перенацілюваної компіляції, застосовані у прототипі перенацілюваного компілятора НВРК-2.

Компілятор НВРК-2 (опис якого доступний в мережі Інтернет http://hbpk2.euro.ru) складається з чотирьох частин: лексичного та синтаксичного аналізатора, глобального оптимізатора, генератора коду та аналізатора коду. Структура компілятора показана на рис. 2.

Рис. 2. Структура перенацілюваного компілятора НВРК-2.

Лексичний та синтаксичний аналізатори (ЛА та СА) перетворюють вхідну програму у внутрішнє подання у вигляді ІГМ програми. Глобальний оптимізатор (ГО) виконує машинно-незалежні глобальні та локальні оптимізації над ІГМ програми. В процесі глобальної оптимізації за допомогою гіпотетичного модуля П-MIMD методами математичного програмування можливо розпаралелювати вхідний код для багатопроцесорних кластерів. Генератор коду (ГК) виконує генерацію коду та машинно-залежні оптимізації. Аналізатор коду (АК) відповідає за оптимізацію на базі статистичної інформації про процес оптимізації коду та керує процесом ітеративної компіляції. Налагодження компілятора описуються за допомогою мови розмітки XML, яка вигідно відрізняється від спеціалізованих мов типу ISDL або nML простотою, структурованістю та ієрархічністю, розширюваністю базових елементів та придатністю до автоматичної обробки. Розглянуто підтримане НВРК-2 розширення мови Сі – DSP-C, яке використовується для ручної оптимізації програм цифрової обробки сигналів мовою Сі.

У розділі розглянуто методики оптимізації та генерації коду для архітектур ПЦОС та МП з ДКС на прикладі МП ADSP-2106x – ПЦОС з однією з найскладнішим систем команд та нейропроцесора Л1879ВМ1, де використовується один з найскладніших з точки зору компіляції векторних сопроцесорів. Показана генерація коду за допомогою експертної системи для складних випадків оптимізації циклів. Розглянуто методику використання алгоритму глибинно-проникаючої програмної конвеєризації EPS з розгорткою циклів, показано переваги використання цих методів при генерації коду та аналізі пристосованості архітектури процесора для вирішення конкретних задач.

Викладені результати тестування методів генерації коду за допомогою тестів DSPstone як для алгоритмів цифрової обробки, так і для типових конструкцій мов високого рівня. Зростання швидкодії особливо позначається у випадках компіляції алгоритмів, до яких адаптована архітектура ПЦОС, у випадках, коли задіяна експертна система компілятора. У таблиці наведені результати генерації коду НВРК-2 та штатними компіляторами ПЦОС ADSP-2106x та нейропроцесора Л1879ВМ1. Ліві колонки містить дані для ADSP-2106x, праві – для Л1879ВМ1.

Порівняльні характеристики ефективності НВРК-2 та штатних компіляторів.

Тестова

програма | Довжина коду (слів) для штатного компілятора | Швидкодія (машинних тактів) для штатного компілятора | Довжина коду (слів) для НВРК-2 | Швидкодія (машинних тактів) для НВРК-2 | Зменшення обсягу потрібної пам’яті для коду, % | Збільшення швидкодії, %

Real_update | 5 | 31 | 5 | 31 | 5 | 28 | 5 | 28 | 0 | 9,7 | 0 | 9,7

N_real_updates | 16 | 79 | 1006 | 8068 | 10 | 36 | 406 | 2605 | 37,5 | 54,4 | 59,6 | 67,7

Complex_update | 18 | 149 | 18 | 132 | 10 | 92 | 10 | 84 | 44,4 | 38,2 | 44,4 | 36,3

Complex_updates | 31 | 224 | 2110 | 21864 | 19 | 95 | 811 | 8316 | 38,7