Методики перенацілюваної генерації коду для мікропроцесорних архітектур з нерегулярним довгим командним словом

Размещено на http://www.allbest.ru/

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

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

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

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

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

Куйвашев Дмитро Васильович

УДК 681.3.06

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

Київ -- 2002

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на http://www.allbest.ru/

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

мікропроцесорний архітектура гіпертекст

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась у рамках плану фундаментальних наукових досліджень Інституту програмних систем НАН України за темами Ф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 та її ІГМ (білим кольором показано перетворювачі, чорним -- розрізнювачі).

Кожний перетворювач являє собою ІГ 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. Поширення констант - посилання на змінну, яка дорівнює константі, замінюється на константу

L = di  diSi  SjDef(di,ConstK)  SjSi, R = (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 після виконання ББ. Результатом відображення є вираз у символьному вигляді - значення vari як функція від значень певних змінних перед початком виконання ББ.

Вводиться оператор композиції над двома ФП 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) ті, які перетворюють вирази доступу (індексні вирази) до елементів масивів.

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

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

FCC(ConstExp)="так",

де varIDX -- необхідна індексна змінна, Op1={'+','-'}.

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

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

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

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

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

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

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

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

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

Назвемо сукупність експертних знань експертними продукціями, позначимо їх множину як NPr*={ PrI }, де 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, varj)); 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= { ek }, ek=( vi, vj). На орграфі вводиться функція зв'язності fc=VV { 0,1 }, і функція розмітки вершин fT(v){ "ресурс", "команда"},vV. Вводиться обов'язкова умова: якщо fc(vi, vj)=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'={ LAm }, виходячи з якої довга команда 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: empI="вільний", якщо регістр не зайнятий значенням) NBE=||ERGB={rgi | empi="вільний" }||. Вводиться атрибут inmemi={"так","ні"} для кожного rgi, який позначає, чи збігається значення змінної в регістрі й в відповідній комірці пам'яті (тобто чи потрібно зберегти значення у пам'яті), кількість таких регістрів є NBM=||MRGB={rgi | inmemi="ні"}||. Розглядаються всі змінні 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={ mc(i,j)N }, де mc(i,j) - кількість конфліктів між змінними vari та varj. За кожного конфлікту зовні тіла циклу значення mc(i,j) збільшується на 1, в разі конфлікту в тілі циклу значення збільшується експоненціально за глибиною вкладення тіла циклу. Пари змінних, які мають найбільші значення конфліктів, розміщуються по різних просторах пам'яті.

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

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

Компілятор НВРК-2 (опис якого доступний в мережі Інтернет http://hbpk2.euro.ru) складається з чотирьох частин: лексичного та синтаксичного аналізатора, глобального оптимізатора, генератора коду та аналізатора коду. Структура компілятора показана на рис. 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	57,5	61,5	61,9
Dot_product	20	102	31	175	8	29	8	51	60	71,5	74,1	70,8
FIR	20	148	91	968	11	38	20	276	45	74,3	78	71,4
Convolution	18	103	126	760	10	24	19	71	44,4	76,7	84,9	90,6
Matrix	44	265	11618	102964	20	61	1844	6253	54,5	76,9	84,1	93,9
Matrix_1x3	32	158	137	912	13	43	37	247	59,3	72,7	72,9	72,9
FIR2DIM	63	387	12147	19194	21	61	2906	2919	66,6	84,2	76	84,7
IIR_one_biquad	23	189	23	181	12	135	12	118	47,8	28,5	47,8	34,8
IIR_n_biquad	26	343	211	2669	17	139	80	842	34,6	59,4	62	68,4
LMS	30	243	111	1832	20	62	35	213	33,3	74,4	68,4	88,3
FFT	54	817	2271	55555	33	144	1178	7827	38,9	82,3	48,1	85,9

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

ОСНОВНІ РЕЗУЛЬТАТИ ДИСЕРТАЦІЙНОЇ РОБОТИ

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

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

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

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

4. Виконано удосконалення методу програмної конвеєризації EPS, що дозволяє визначати придатність конкретної апаратної платформи для виконання певних алгоритмів.

5. Для опису апаратної платформи та експертних знань розроблена мова на базі тегової моделі мови розмітки XML, так як властивості мов опису гіпертексту дозволяють природно подавати ієрархічні дані.

За результатами досліджень побудовано прототип перенацілюваного компілятора НВРК_2 для мікропроцесорів ADSP-2106х SHARC та Л1879ВМ1. Розроблений компілятор може використовуватися для оптимізованої генерації коду для процесорів цифрової обробки сигналів та мікропроцесорів з архітектурою з нерегулярним довгим командним словом.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1. Дорошенко А. Ю., Куйвашев Д. В. Архiтектура модульного крос-компiлятора для мiкропроцесорiв з дуже довгим командним словом // Проблемы программирования.- 2000.- № 3-4.- С. 122-134. (Дисертантом розроблено основні положення для побудови архітектури перенацілюваного компілятора.)

2. Дорошенко А. Ю., Куйвашев Д. В. Iнтелектуалiзацiя векторизуючих компiляторiв для мiкропроцесорiв з довгим командним словом // Проблемы программирования.- 2001.- №1-2.- С. 138-151. (Дисертантом розроблено систему налагоджень та описів для перенацілюваного компілятора для провадження інтелектуалізованої генерації коду, формалізовано описи цільової архітектури обчислювальної системи.)

3. Куйвашев Д. В. Ефективність проекцій алгоритмів на архітектури процесорів цифрової обробки сигналів з довгим командним словом // Проблемы программирования.- 2001.- №3-4.- С. 174-188.

4. Казимир В. В., Куйвашев Д. В. Використання мови програмування Форт як засобу реалізації динамічної системи керування // Управляющие системы и машины.- 1999. - №6.- С. 49-55. (Дисертантом розроблено засади організації динамічної системи керування на основі мереж Петрі для вбудованих систем, процедури якої необхідно обробляти оптимізуючим компілятором для досягнення ефективної роботи системи.)

5. Казимир В. В., Куйвашев Д. В. Компонентна система побудови системи Форт для завдань керування. // Вісн. Чернігівського. держ. технол. ун-ту.- 2000.- №10.- С. 177-182. (Дисертантом запропоновано використання операційної системи реального часу на базі мови програмування Форт, з вбудованим оптимізуючим компілятором та іншим системним програмним забезпеченням.)

6. Дорошенко А. Ю., Куйвашев Д. В. Інтелектуалізація перенацілюваної оптимізуючої компіляції для мікропроцесорів цифрової обробки сигналів. // Проблемы программирования: Материалы 3-й междунар. науч.-практ. конф. по программированию.-- 2002.- №1-2.- С. 477-488. (Дисертантом запропоновано використання ієрархічних графових моделей програми у перенацілюваних компіляторах, подано формалізації функцій перетворення потоку даних та основні алгоритми генерації коду.)

Куйвашев Д. В. Методики перенацілюваної генерації коду для мікропроцесорних архітектур з нерегулярним довгим командним словом. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин та систем. - Інститут програмних систем НАН України, Київ, 2002.

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

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

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

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

Куйвашев Д. В. Методики перенацеливаемой генерации кода для микропроцессорных архитектур с нерегулярным длинным командным словом. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Институт программных систем НАН Украины, Киев, 2002.

Диссертация посвящена разработке средств системного программного обеспечения для новых микропроцессорных архитектур, в частности разработке оптимизирующего перенацеливаемого компилятора для микропроцессоров цифровой обработки сигналов и микропроцессоров с длинным командным словом.

При постановке задачи диссертационного исследования описаны основные направления исследований по тематике построения эффективных компиляторов для проблемно-ориентированных микропроцессорных архитектур. Описаны современные микропроцессорные архитектуры с нерегулярным длинным командным словом и существующие решения для повышения эффективности компиляторов для таких микропроцессоров. Описаны наиболее известные разработки в области перенацеливаемой компиляции и одновременной разработки программных и аппаратных средств MIMOLA, RECORD, SUIF-2/AVIV, GCC/LCC, Trimaran, основывающиеся на различных подходах к решению проблемы.

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

Предложен формализм описания целевой процессорной архитектуры, включающей как описание архитектуры, так и описание знаний про парадигму оптимизации кода для микропроцессора. Методика позволяет включить в комбинационные алгоритмы генерации расписания команд эвристики, присущие человеку, с помощью продукционной экспертной системы. Интегрированная экспертная система позволяет легко расширять компилятор машинно-специфичными оптимизациями. Приведена систематизация знаний об архитектуре целевой платформы для использования в экспертной системе в виде унифицированных продукций. Предложены улучшения алгоритмов составления расписаний команд для кластеризированых регистровых файлов, переключения режимов вычислений, равномерного распределения нагрузки на канал доступа к памяти. Предложен адаптированный для процессоров с большим регистровым файлом метод распределения регистров, основанный на сканировании вперёд графа потока данных.

...