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

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

Достовірність результатів підтверджено експериментально – на базі запропонованих методів розроблено прототип перенацілюваного налагоджуваного компілятора НВРК-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. Для будь-якої вершини pT максимальне піддерево T з коренем p позначається T (p), а G (p) – фрагмент основного графа G, відповідний p, H (p) = (G (p), T (p)) – ієрархічний підграф H, асоційований з вершиною p. Поданням графової моделі програми є ІГ H= (G, T), де кожна вершина pT відповідає деякому підграфу основного графа G. T називається вершинним деревом вкладеності, вершини T відповідають певним підмножинам G. Вводяться мітки – множина об’єктів V, яка розпадається на попарно непересічні