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

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

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

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

УДК 004.27;004.436.2

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

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

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

05.13.05 - комп'ютерні системи та компоненти

Сало Андрій Миколайович

Львів-2008

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

Робота виконана в Національному університеті “Львівська політехніка” Міністерства освіти і науки України

Науковий керівник -доктор технічних наук, професор Мельник Анатолій Олексійович, Національний університет “Львівська політехніка”, завідувач кафедри електронних обчислювальних машин

Офіційні опоненти -доктор технічних наук, професор Харченко В'ячеслав Сергійович, Національний аерокосмічний університет ім. Жуковського М.Є. “ХАІ”, завідувач кафедри комп'ютерних систем і мереж (м. Харків)

доктор технічних наук, професор Николайчук Ярослав Миколайович, Тернопільский національний економічний університет, завідувач кафедри СКС (м. Тернопіль)

Захист відбудеться “ 28 ” листопада 2008 р. o 16³⁰ годині на засіданні спеціалізованої вченої ради Д 35.052.08 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул. С.Бандери, 12, ауд. 226 головного корпусу).

З дисертацією можна ознайомитись у бібліотеці Національного університету “Львівська політехніка” (79013, Львів, вул. Професорська, 1)

Автореферат розісланий “ 27 ” жовтня 2008 р.

Вчений секретар спеціалізованої вченої ради, д.т.н., проф. Я.Т.Луцик

комп'ютерний архітектура базовий процесор

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

Актуальність теми. Протягом останніх років технології проектування комп'ютерних пристроїв зазнали кардинальних змін. Було розроблено мови типу VHDL та Verilog, які стали основними інструментами опису комп'ютерних апаратних засобів. Також створено низку потужних САПР НВІС, які підтримують їх розробку, починаючи з опису на названих мовах до створення кристалу. В той же час, завдяки досягненням у галузі інтегральної технології суттєво зріс рівень інтеграції мікросхем, і з'явилась можливість реалізації в них надзвичайно складних комп'ютерних пристроїв. У зв'язку з цим існуючі методи проектування комп'ютерних пристроїв, які передбачають проведення розробки від самого початку (постановки задачі) до реалізації стали неефективними, оскільки для створення комп'ютерного пристрою великої складності вони вимагають невиправдано багато часу, що негативно впливає на конкурентоспроможність створеного продукту.

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

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

Значними є досягнення у галузі проектування спеціалізованих процесорів таких вітчизняних вчених: Я.М. Николайчука, В.П. Тарасенка, Г.М. Луцького, М.В. Черкаського, І.А. Жукова, В.С. Глухова.

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

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

Зв'язок роботи з науковими програмами, планами і темами. Дисертаційна робота виконувалась згідно з планом науково-дослідних робіт кафедри електронних обчислювальних машин Національного університету “Львівська політехніка” протягом 2001-2007 р. Дисертаційна робота безпосередньо пов'язана з держбюджетними темами, де автор був одним з виконавців робіт: ДБ.17.МЕЛЬ “Інтелектуальні реконфігуровані нарощувані вимірювально-обчислювальні мережі екологічного моніторингу: принципи структурної самоорганізації та функціонування”, 2002-2003 р. (номер державної реєстрації 0100U000530); ДБ/АВАГ “Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища”, 2004-2006 р. (номер державної реєстрації 0104U002284).

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

Для досягнення поставленої мети в роботі розв'язано такі задачі:

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

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

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

4. Дослідження та розроблення методів конфігурування базової архітектури з використанням опису алгоритму мовою високого рівня.

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

6. Реалізація НВІС спеціалізованих процесорів з використанням розроблених засобів конфігурування моделі базової архітектури.

Об'єкт дослідження: комп'ютерні засоби системного проектування програмованих спеціалізованих процесорів.

Предмет дослідження: методи та засоби конфігурування програмованих спеціалізованих процесорів.

Методи дослідження: В дисертаційній роботі використано: методи математичного та імітаційного моделювання, основи теорії комп'ютерних систем, теорію графів, обчислювальну математику, методи проектування комп'ютерних систем, прикладну теорію цифрових автоматів, основи теорії алгоритмів, теорію складності та прикладного програмування.

Наукова новизна одержаних результатів полягає в наступному:

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

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

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

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

Практичне значення одержаних результатів.

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

- одержані в дисертаційній роботі наукові результати реалізовано у вигляді програмного забезпечення для проектування спеціалізованих пристроїв на основі конфігурування VHDL-моделі базової архітектури процесора;

- одержані на спроектованих у роботі засобах процесори випереджають аналогічні взірці процесорів, одержаних за допомогою існуючих на ринку засобів майже в два рази за продуктивністю та майже на 1/3 за затратами обладнання.

Використання результатів. Одержані в дисертаційній роботі результати використані в наступних організаціях:

· Національний університет “Львівська політехніка”, кафедра “Електронні обчислювальні машини”, в рамках виконання науково-дослідних робіт по темах, ДБ.17.МЕЛЬ “Інтелектуальні реконфігуровані нарощувані вимірювально-обчислювальні мережі екологічного моніторингу: принципи структурної самоорганізації та функціонування”, 2002-2003 рр., ДБ/АВАГ “Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища”, 2004-2006 рр.

· Національний університет „Львівська політехніка”, кафедра "Електронні обчислювальні машини", в рамках лекційного курсу “Архітектура спеціалізованих комп'ютерних систем”.

· На ДП “Арсенал” в рамках створення периферійної плати канального адаптера “КА100М”.

· На ДАХК “Артем” в рамках створення периферійної плати канального адаптера “КА100М”.

· На науково - виробничому підприємстві “Інтрон” при розробці системи «Хамелеон» для автоматизованого проектування спеціалізованих процесорів.

Практична цінність результатів роботи підтверджується актами про впровадження результатів дисертації на ДП “Арсенал”, ДАХК “ Артем”, НВП “Інтрон”.

Особистий внесок здобувача. Всі теоретичні та практичні результати, що виносяться на захист, отримано автором самостійно. У роботах, опублікованих у співавторстві, здобувачеві належать: [1] - класифікація, оцінка апаратної та часової складності різних типів регістрових файлів програмованих процесорів; [2,10] - аналіз існуючих технологій автоматизованого проектування спеціалізованих процесорів, дослідження архітектури конфігурованого процесора, результати синтезу ШПФ; [4,9] - метод конфігурування спеціалізованого процесора; [7] - опис структури та форматів команд процесора; [8] - принципи побудови ISDN контролера на базі програмованого спеціалізованого процесора; [6,11] - структурна схема присторою виконання операторів циклу.

Апробація результатів дисертації. Основні результати дисертаційної роботи обговорено на сьомій міжнародній конференції “Досвід розробки та застосування САПР в мікроелектроніці” (2003, Славсько); міжнародній конференції “Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії” (2004, Львів); міжнародних конференціях “Сучасні комп'ютерні системи та мережі: розробка та використання” (2005, 2007, Львів); міжнародній конференції “NASA/ESA Conference on adaptive hardware and systems” (2007, Edinburgh, UK); другій міжнародній конференції молодих науковців “Комп'ютерні науки та інженерія” (2007, Львів); третій міжнародній науково-технічної конференції “Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування” (2007, Вінниця).

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

Обсяг і структура дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел і додатків викладених на 229 сторінках друкованого тексту. Основний зміст викладений на 151 сторінці. Список використаних джерел містить 129 найменувань. Робота містить 51 рисунок, 11 таблиць та 4 додатки.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Показано переваги та недоліки існуючих на даний час двох підходів до реалізації

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

Показано, щоб створити систему проектування з мови високого рівня шляхом конфігурування певної моделі базової архітектури програмованих процесорів, необхідно розробити три підсистеми: компілятор, конфігуратор та модель базової архітектури процесора. Оптимальність роботи систем другого класу значною мірою залежить від вибору базової архітектури. Архітектури VLIW, суперскалярна архітектура, EPIC та ТТА розглянуто як базові. Задачі обробки сигналів вибрано як основні тестові задачі для визначення принципів побудови базової моделі архітектури.

У результаті аналізу визнечено, що необхідно створити метод конфігурування моделі базової архітектури по вхідному алгоритму розв'язку задачі, описаної мовою програмування високого рівня. Як основну, для розробки моделі базової архітектури необхідно взяти архітектуру EPIC, обравши VLIW-подібний формат інструкції, і використати методи програмування ТТА для досягнення високого рівня конфігурованості моделі базової архітектури.

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

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

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

Кожний тип регістрового файлу досліджено на предмет ефективності використання в паралельній архітектурі. Аналітично апаратні затрати та час доступу для інтегрованого багатопортового регістрового файлу визначається за формулами 1 та 2 відповідно.

A=O(N* n_r* ((p_в+3)* N)²) (1)

T=O((p_в +3)*N*( n_r *N)^1/2), (2)

де N - кількість ОМ, n_r - кількість регістрів для одного ОМ, p_в+3 - кількість портів читання/запис для одного ОМ.

Апаратні затрати та час доступу для розподіленого регістрового файлу з керованою комутацією визначається за формулами 3 та 4 відповідно.

A= N*A_БР + А_КМ=N*O(1/2*n_r*2²)+O(N²)= N*O(2*n_r)+O(N²) (3)

T=O(2* n_r^1/2)+O(N), (4)

де A_БР - площа кристалу під банки регістрів, А_КМ - площі кристалу під комутуючу мережу. Аналізуючи формули (1-4) бачимо, що розподілений регістровий файл має кращі показники за апаратними затратами і часом доступу, що дозволяє на його базі будувати більш ефективні паралельні архітектури. Для дослідження можливості реалізації різних типів регістрових файлів створено їх моделі із різними параметрами на мові VHDL. Одержані результати підтвердили аналітичні розрахунки та довели, що розподілений регістровий файл з керованою комутацією є найбільш прийнятним з точки зору апаратних затрат та часу доступу. Обгрунтовано доцільність використання модулів пам'яті з програмованою затримкою в регістровому файлі. Регістровий файл конфігурується відповідно до кількості вхідних/вихідних портів, розрядності шини даних, кількості та величини адресного простору кожного МППЗ.

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

L=++++, (6)

де - кількість команд, що може виконувати i-тий обчислювальний модуль; - адресний простір i-того банку пам'яті з програмованою затримкою; - кількість модулів пам'яті з програмованою затримкою; - кількість вхідних портів комутуючої мережі №1; - кількість вихідних портів комутуючої мережі №2; Z - довжина мікрокоду. Формула (6) показує, що формат команди не є фіксований, а визначається з конфігураційних параметрів.

Для реалізації команд умовних переходів в моделі базової архітектури спеціалізованого процесора запропоновано та обгрунтовано використовувати умовні команди. Безпосередньо вводити команди умовних переходів в структуру процесора де використовуються МППЗ неможливо, оскільки відбудеться хаотична подача даних на ОМ, що призведе до помилкових результатів виконання програми. Для вирішення проблеми введено команди, що виконуються по умові. Існуючі методи виконання умовних команд передбачають введення додаткового поля умови в команду та порівняння його вмістимого із значенням стану регістра умов, що спричиняє затримку під час виконання таких команд, а також збільшує їх довжину. В дисертаційній роботі пропонується метод виконання умовних команд, який полягає в тому, що підраховується кількість захищених команд шляхом віднімання адреси переходу і текучої адреси команди керування. Якщо умова переходу справджується, тоді значення кількості команд заноситься в лічильник, який забезпечує подачу на ОМ пустої команди (рис. 3). Це дозволяє прискорити виконання команди, а також не виділяти додаткової пам'яті для збереження програми.

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

БАП = {МОМ, МКОМ, РД, ММППЗ, КПК, ПП, МВхР, МВихР, МКМ, МЛЗ}, (7)

де МОМ - множина конфігурованих ОМ, МКОМ - множина команд ОМ, РД - розрядність даних, ММППЗ - множина конфігурованих МППЗ, МКМ - множина конфігурованих комутаційних мереж (КМ), КПК - конфігурований ПК, ПП - конфігурована пам'ять програм, МВхР - множина конфігурованих вхідних портів, МВихР - множина конфігурованих вихідних портів, МЛЗ - множина ліній зв'язку.

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

У третьому розділі запропоновано метод конфігурування спеціалізованих процесорів із використанням моделі базової архітектури та отриманням оптимального рішення по відношенню продуктивністі до затрат обладнання, а також метод планування виконання інструкцій у спеціалізованому процесорі. Задачу отримати конфігураційні параметри та вибір оптимального рішення запропоновано представити таким чином: маючи вхідну множину інструкцій І мови високого рівня ANSI С, отримати вихідну множину інструкцій А низькорівневої асемблерної мови у форматі типу VLIW та множину конфігураційних параметрів С, яка повинна відповідати умові:

T>=N_a*T_iн, де T - максимально допустимий час виконання алгортму, N_a - кількість інструкцій множини А, T_iн - час виконання однієї інструкції множини А.

Для вирішення поставленої задачі розроблено метод конфігурування архітектури процесора, який полягає у перетворенні вхідної множини інструкцій І у множину інструкцій L, представлених у RTL форматі. Потім проводиться аналіз залежностей за даними вхідної множини інструкцій L. На основі цього аналізу будується множина рішень S_рішень., яка складається з пари {t_вик, w_проц}, де w_проц - апаратні витрати, t_вик - час виконання. А з множини рішень вибирається d_опт оптимальне по відношенню продуктивності до затрат обладнання. Знаходження оптимального рішення полягає у визначенні d_опт та визначенні інших конфігураційних параметрів, таких як час надходження операндів на ОМ, якісний склад інструкцій, необхідний розмір черги даних та інші. Обчисливши конфігураційні параметри генеруємо спеціалізований процесор.

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

1. Перетворення вхідного коду на мові високого рівня у проміжне представлення. Перетворення можна описати таким чином:

C_c>C_rtl>C_t , (8)

де C_c - вхідна програма на мові програмування високого рівня ANSI C;

C_rtl - проміжне представлення програми у RTL-коді;

C_t - проміжне представлення програми у триадресному коді.

2. Перетворення проміжного представлення вхідної програми на мові високого рівня у вигляд інформаційно-логічного графу. Аналіз вхідного коду на мові програмування високого рівня, перетвореного у триадресний код, виконується за допомогою представлення процесу виконання програми у вигляді інформаційно-логічного графу G=(X,P,Г). Множина X={i}={1..m} графу G відповідає множині операторів алгоритму. Множина P={ti}, i=1, …, m, визначає час виконання кожного оператору. Г - множина дуг. Таке представлення дозволяє аналізувати можливість розпаралелення вхідного коду і визначення параметрів для конфігурування базової архітектури процесора.

3. Визначення найменшої кількості ОМ процесора, який виконує алгоритм, на основі конкретизованого інформаційно-логічного графу. Конкретизований інформаційно-логічний граф G' = {X, Р, Г') будується об'єднанням вершини, що відповідають операторам кожної повної множини взаємно-незалежних операторів, що містить r>n операторів, r-n орієнтованими дугами в n шляхів, що не містять загальних вершин. Де r - кількість інструкцій, які можна виконати паралельно, а n - визначена кількість обчислювальних модулів. При цьому довжина критичного шляху графу G' не повинна перевищувати значення Т. Побудова графу G' базується на методі ефективного планування завантаження паралельних віток процесора.

4. Визначення конфігураційних параметрів базової архітектури. Для цього запропоновано перетворити конкретизований інформаційно-логічний граф у просторово-часовий граф G''=(X,P'', Г''), який повністю визначає конфігурацію базового процесора. Множина P''=P?P1, де P1={ni}, i=1..m, визначає номер ОМ, на якому буде виконуватись оператор i. Множина Г''= Г ? Гi, де Гi = {tj}, j=1..s, визначає час затримки даних. S - кількість дуг у графі. Даний граф визначає на якому ОМ і в який час буде виконуватися ця інструкція.

5. Побудова множин рішень S_рішень у двовимірному просторі “продуктивність/затрати обладнання”.

6. Вибір оптимальних конфігураційних параметрів по відношенню продуктивності до затрат обладнання. Простір рішень обмежується кривою, що з'єднує точки локальних оптимальних рішень (ЛОР). Ці точки визначаються за такою формулою:

M(t_викc, w_проц) € S_рішень є ЛОР (t,w) € S_рішень, ( t? t_викc V w ? w_проц)(9)

Окрім відношення часу виконання до апаратних витрат можливо для порівняльної характеристики застосовувати ефективність використання обладнання Е = 1/wt .

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

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

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

Для реалізації методу планування виконання інструкцій у спеціалізованому процесорі запропоновано такі етапи:

1. Представити програму описану інструкціями множини І_Р у вигляді графу G=(X,P,Г). Множина X={i}={1..m} графа G відповідає множині І_Р. Множина P={ti}, i=1, …, m, визначає час виконання кожної інструкції. Г - множина дуг, які описують залежності між вузлами графа.

2. Нехай tbeg(nx) -- довжина найдовшого шляху з початкового вузла до вузла nx в графі G. Відповідно, нехай tend(nx) -- довжина найдовшого шляху з вузла nx до кінцевого вузла. Впорядкуємо вузли за спаданням величини tend(nx).

3. Для відрізка часу t знаходимо кількість операторів r. Якщо r>n, тоді вводимо додаткових r-n зв'язків.

4. Додаткові зв'язки вводимо шляхом поступового збільшення tend(nx) на одиницю. Вибираємо найменше значення tend(nx) з усіх можливих.

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

На основі запропонованих методів та моделі базової архітектури процесора запропоновано послідовність етапів проектування спеціалізованих пристроїв (рис. 5.), які дозволяють звести процес проектування до написання програми мовою Сі.

У четвертому розділі досліджено реалізацію системи проектування на основі методу конфігурування базової архітектури спеціалізованого процесора. Розглянуто загальну організацію системи, реалізацію кожного компонента, представлено результати роботи системи та порівняння з існуючими аналогами. Розроблена система проектування складається з декількох окремих функціональних вузлів: компілятора, конфігуратора моделі базової архітектури процесора, генератора VHDL коду, конфігурованої моделі базового процесора, засобів візуалізації процесу проектування. Реалізація компілятора системи проектування базується на платформі компілятора CNU GCC. Компілятор GCC виконує перетворення коду з мови високого рівня у проміжне представлення. Компілятор GCC запускається окремим процесом. Загальну машинонезалежну оптимізацію коду покладено на GCC.

Перетворення проміжного представлення у триадресний код покладено на розроблений асемблер. Розроблено алгоритм перетворення проміжного представлення компілятора GCC у триадресний код. Для реалізації вводу/виводу до стандартних бібліотек мови С було додано бібліотеку з функціями вводу/виводу. Асемблер виконує перетворення високорівневих функцій вводу/виводу у відповідні триадресні команди.

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

Реалізований генератор конфігурованого процесора формує VHDL опис спеціалізованого процесора з отриманої моделі базової архітектури на основі відповідних параметрів конфігурування. Генератор побудовано на основі текстового процесора AWK, що дозволило прискорити процес реалізації. Реалізовано базову модель конфігурованого процесора на мові VHDL. Наведемо приклад проектування пристрою згортки, алгоритм роботи якого описаний мовою Сі (рис. 6).

Після компіляції та конфігурації, отримуємо VHDL - опис пристрою. На рис. 8 наведено часову діаграму роботи медіанного фільтра, яка доводить коректність роботи пристрою. Перевірено коректність роботи пристрою шляхом порівняння отриманих результатів з еталонними. Відповідно до наведених налаштувань отримано інтерфейс пристрою (рис. 7).

Наведені результати реалізації найбільш поширених алгоритмів обробки сигналів за допомогою розробленої системи показали значну перевагу у продуктивності і апаратних затратах над пристроями отриманими за допомогою системи Impulse C (таблиця 1).

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

Таблиця 1. Результат синтезу пристроїв на ПЛІС

№	Алгоритм	ПЛІС	Власна система	Impulse C
			Кількість блоків ПЛІС	Тактова частота (МГц)	Кількість блоків ПЛІС	Тактова частота (МГц)
1	RGB -> YUV	Virtex-4	350(2%)	236.401	395(3%)	93.413
2		Spartan3	352(5%)	113.418	360(5%)	67.595
3	Множення матриць 2x2	Virtex-2	308(60%)	99.541	354(69%)	65.300
4	ДКП 8x8	Virtex-2	863(56%)	94.838	890(57%)	40,416
5	Медіанний фільтр	Virtex-2	464(30%)	98.871	600(39%)	54.928
6	Згортка	Virtex-2	985(64%)	81.532	1050 (68%)	47.960

ВИСНОВКИ

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

При цьому одержано такі результати:

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

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

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

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

4. Запропоновано метод конфігурування формалізованої моделі архітектури процесора з описом алгоритму мовою високого рівня, який, на відміну від відомих, базується на виборі конфігураційних параметрів за критерієм “продуктивність/ затрати обладнання” та не вимагає введення додаткових конструкцій у мову опису алгоритму, що дозволяє прискорити та спростити процес проектування процесорів.

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

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

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

8. На основі розробленої системи виконано проектування процесорів перетворення RGB в YUV, множення матриць, дискретного косинусного перетворення, медіанного фільтру та згортки. Пристрої синтезовано на базі ПЛІС фірми Xilinx, які порівняно з кращими світовими реалізаціями мають аналогічні характеристики. Основною перевагою є те, що зменшується вартість розробки тільки до вартості написання алгоритму на мові високого рівня. Також одержані на спроектованих у роботі засобах процесори випереджають взірці процесорів, одержаних за допомогою аналогічних існуючих на ринку засобах майже в два рази за продуктивністю та майже на 1/3 за затратами обладнання.

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

1. Мельник, А. О. Організація регістрових файлів програмованих процесорів [Текст]/ А. О. Мельник, А. М. Сало // Вісник НУ “Львівська політехніка”. -2006. -№573. - С. 138-147.

2. Мельник, А. О. Проектування спеціалізованих процесорів на основі їх конфігурованих моделей[Текст]/ А. О. Мельник, А. М. Сало // Моделювання та інформаційні технології. Зб. наук. пр. ІПМЕ НАН України. - 2007. -№ 39. - C. 136-149.

3. Сало, А. М. Сучасні засоби проектування НВІС на системному рівні[Текст]/ А. М. Сало // Моделювання та інформаційні технології: Зб. наук. пр. ІПМЕ НАН України. - 2007. - №44. - С. 110-117.

4. Мельник, А. О. Методика проектування паралельного процесора на основі пам'яті з детермінованою вибіркою[Текст]/ А. О. Мельник, А. М. Сало// Вісник НУ “Львівська політехніка”. - 2005. - №546. - С. 96-101.

5. Сало, А. М. Реалізація умовних команд програмованого паралельного процесора[Текст]/ А. М. Сало // Моделювання та інформаційні технології. Зб. наук. пр. ІПМЕ НАН України. -2006. - № 37. - C. 169-180.

6. Мельник, А. О. Апаратна реалізація циклів програмованих конфігурованих процесорів[Текст]/ А. О. Мельник, А. М. Сало, В.А. Клименко // Вісник НУ “Львівська політехніка”. -2007. -№603. - С. 94-102.

7. Melnyk, Anatoly. Instruction set architecture of the determined memory access processor[text]/ Anatoly Melnyk, Andriy Salo // Досвід розробки та застосування САПР в мікроелектроніці - CADSM'2003. Матеріали 7-ї міжнародної конференції. -. м. Славсько. - 2003. - С. 198-199.

8. Melnyk, Anatoly. Integrated services digital network controller architecture based on parallel reconfigurable processor[text]/ Anatoly Melnyk, Andriy Salo // Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії - TCSET'2004. Матеріали міжнародної конференції TCSET'2004. - м. Львів-Славсько. -2004. - С. 426-427.

9. Melnyk, Anatoly. Designing system of determined memory access processor[text]/ Anatoly Melnyk, Andriy Salo // Сучасні комп'ютерні системи та мережі: розробка та використання - ACSN'2005. - Львів. - 2005. - С. 31-33.

10. Melnyk, Anatoly. Automatic generation of ASICs[text]/ Anatoly Melnyk, Andriy Salo // NASA/ESA Conference on adaptive hardware and systems. - Edinburg, UK. -2007. - P. 311-317.

11. Мельник, А. О. Апаратна реалізація команд керування програмованих процесорів [Текст]/ А. О. Мельник, А. М. Сало, В.А. Клименко // Комп'ютерні науки та інженерія: Матеріали 2-ї Міжнародної конференції молодих науковців CSE-2007. - Львів. -2007. - С. 119-121.

12. Сало, А. М. Використання умовних команд в апаратно-орієнтованих процесорах [Текст]/ А. М. Сало // Матеріали ІІІ Міжнародної науково-технічної конференції: Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування (СПРТП-2007). - Вінниця. -2007. - С 108-109.

13. Salo, Andriy. Hardware acceleration of control commands execution[text]/ Andriy Salo// Сучасні комп'ютерні системи та мережі: розробка та використання - ACSN'2007. - Львів. - 2007. - С. 35-37

АНОТАЦІЯ

Сало А.М. Методи та засоби конфігурування архітектури програмованих спеціалізованих процесорів. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. Національний університет «Львівська політехніка» , Львів, 2008.

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

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

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

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

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

АННОТАЦИЯ

Сало А.М. Методы и средства конфигурирования архитектуры программируемых специализированных процессоров. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. Национальный университет «Львовская политехника», Львов, 2008.

Диссертация посвящена вопросам разработки методов и способов конфигурирования архитектуры программируемых специализированных процессоров. В первой главе рассмотрены современные высокопродуктивные параллельные архитектуры процессоров и средства системного проектирования компьютерных устройств. На основе проведенного анализа были выделены основные черты алгоритмов программ, которые выполняются специализированными процессорами. В ходе выполнения диссертации рассмотрены основные современные подходы, методы и системы проектирования специализированных процессоров. В результате проведенных исследований было предложен подход по проектированию современных специализированных процессоров на основе конфигурирования модели базовой архитектуры по алгоритму, описанному на стандартном языке программирования высокого уровня. Вторая глава посвящена разработке новой модели базовой архитектуры специализированного процессора и структуры каждого элемента данной архитектуры. Данная архитектура и каждый ее элемент можно конфигурировать по разным параметрам. С целью создания теоретических принципов построения регистровых файлов программируемых процессоров была предложена их классификация. Для исследования возможности реализации разных типов регистровых файлов были созданы их модели с разными параметрами на языке VHDL. Полученные результаты подтвердили аналитические расчеты и доказали, что распределенный регистровый файл с управляемой коммутацией является наиболее приемлемым для построения параллельной архитектуры с точки зрения аппаратных затрат и времени доступа. Предложена структура устройства выполнения условных команд в базовой архитектуре процессора, которое обеспечило выполнение алгоритмов с процедурой передачи управления и позволило ускорить их выполнение. Аппаратно реализованный блок выполнения циклов позволил использовать вычислительные модули только для выполнения арифметико-логических операций, а не на обслуживание вычислительного процесса.

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

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

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

АBSTRACT

Salo A.M. Methods and tools for programmable dedicated processors architecture configuration. - Manuscript.

The dissertation for obtaining of a scientific degree of Candidate of Technical Science in a speciality 05.13.05 - computer systems and components. Lviv Polytechnic National University, Lviv, 2008.

The dissertation is dedicated to the programmable dedicated processors design process improvement by developing and implementing methods and software/hardware tools for processor architecture configuration.

New model of basic specialized processor architecture with instruction level parallelism support is developed. Capability to synthesize dedicated processors with given characteristics on the basis of the model is shown. The structure of conditional instruction execution unit for the basic processor architecture is proposed. The unit allows algorithms with control transfer execution with reduced run-time. The new method of basic architecture configuration is developed. The method is based on high-level language defined algorithm analysis and configuration parameters selection, which allows hardware algorithm implementation.

The known method of effective concurrent processor branches load planning is improved. It is expanded for the case of instruction execution optimization in proposed model of processor architecture based on distributed register file with dynamic date allocation.

The computer-aided design system for dedicated processors synthesis on the basis of high-level language defined algorithm is developed and examined. Variety of devices were implemented on it's basis: discrete cosine transformation, median filtering, image format conversion and others. Advantages of developed devices over known analogues in performance and hardware costs are shown.

Key words: dedicated processors, system-level design, processor architecture, instruction-level parallelism, system-on-chip, computer system cores, signal processing algorithms, configuration parameters.

Размещено на Allbest.ru

...