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

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

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

 

 

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

 

УДК 681. 3. 06

 

 

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

 

Автореферат

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

 

Київ – 2002

 

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

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

Науковий керівник: доктор фізико-математичних наук ДОРОШЕНКО Анатолій Юхимович, Інститут програмних систем НАН України, заступник директора з наукової роботи. 

Офіційні опоненти: доктор технічних наук, професор ПОГОРІЛИЙ Сергій Дем’янович, Київський національний університет імені Тараса Шевченка, заступник завідувача кафедри напівпровідникової електроніки, кандидат технічних наук, доцент ПУСТОВАРОВ Володимир Ілліч, Національний технічний університет України «Київський політехнічний інститут», доцент кафедри обчислювальної техніки.

Провідна установа: Інститут проблем моделювання в енергетиці імені Г. Є. Пухова НАН України, відділ спеціалізованих засобів моделювання, м. Київ.

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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