RUS | ENG || ДонНТУ> Портал магістрів ДонНТУ
Магістр ДонНТУ Черниш Ігорь Ігорович

Черниш Ігорь Ігорович

Факультет: Комп'ютерних наук і технологій
Кафедра: Комп'ютерної інженерії

Тема випускної роботи:

Дослідження структур композиційних мікропограммних пристроїв керування із загальною адресацією в базисі стандартних ВІС

Науковий Керівник: Зеленьова Ірина Яківна

Матеріали до теми випускної роботи: Про автора

Реферат за темою випускної роботи

Вступ

На сьогоднішній день існує тенденція у бік розвитку web-технологій. Одним з головних завдань цього напряму є перенесення функціональних блоків обробки на сервер, а також максимальне спрощення інтерфейсу користувача [20, 21]. В результаті користувачеві надається система, в якій прості команди стають наслідком виконання складних алгоритмів, що вимагають витрати більшої кількості ресурсів. Ці витрати повністю переносяться на сервер, що практично не позначається на ресурсах ПК. Java-Applet використовуються для надання інтерактивних можливостей веб-додатка, які не можуть бути надані HTML [20, 21]. Оскільки байт-код Java платформонезалежен, то Java-Applet може виконуватися за допомогою плагинов браузерами багатьох платформ, включаючи Microsoft Windows, UNIX, Apple Mac OS і GNU/Linux. Такі програми з відкритим початковим кодом, як applet2app, можуть бути використані для перетворення аплета в самостійні програми на Java або виконуваних файлах Linux і Windows [22, 23].

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

Як наукова область в даній роботі розглядаються структури пристроїв керування. Одним з методів реалізації пристрою керування цифрової системи є використання моделі композиційного мікропрограмного пристрою керування (КМУУ) [28, 29].

Мета і завдання роботи

Актуальність теми

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

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

ACTIVE-HDL в своїй програмній реалізації має засоби для створення і редагування FSM-структур (finite state machine, кінцевий автомат). Основна ідея автоматної реалізації – це опис процесу у вигляді граф-схемы з генерацією програмного коду на мові VHDL або Verilog, з подальшою можливістю синтезу отриманого коду на заданій ПЛІС.

В даний час зростання використання ПЛІС для реалізації автоматів припиняється дорожнечею мікросхем. Тому конструкторам-програмістам доводиться вирішувати задачу зменшення апаратних витрат (в даному випадку – площа кристала ПЛІС або число вентилів) з великими витратами часу розробки.

Існує безліч методів зменшити апаратні витрати шляхом використання додаткових елементів (наприклад мультиплексорів, ППЗУ), які додають алгоритму гнучкість автомата з програмованою логікою (АПЛ) і швидкість автомата з жорсткою логікою (АЖЛ).

Порівняльні результати параметрів синтезованих пристроїв при однакових початкових граф-схемах, реалізовані засобами FSM A-HDL(finite state machine) і за допомогою структурного опису результуючої схеми, показують певне зменшення числа використовуваних елементів FPGA при реалізації іншим методом.

Недолік FSM-редактора A-HDL–генерація програмного коду в поведінковому стилі, що робить неможливим передбачити результат синтезу. Структурний же опис схеми, отриманої в результаті тривіальної реалізації, дає можливість спрогнозувати результат ще до синтезу – на етапі генерації програмного коду, що дає можливість генерувати код для кристала або числа вентилів FPGA заданої розмірності.

Передбачувана наукова новизна

Наукова значущість дослідження для нашого проекту полягає у визначенні найбільш оптимального керуючого автомата для реалізації заданого алгоритму. Алгоритм задається у вигляді граф-схемы (ГСА). Інтерфейс користувача містить в собі всі графічні компоненти, з яких в процесі обробки будується ГСА. Паралельно з цим процесом генерується XML-файл, що містить інформацію про алгоритм (кількість операторних і умовних вершин, структура ГСА), який у результаті пересилається на сервер. На сервері відповідно до статистики в базі даних виконується аналіз XML–файлу і підбирається керуючий автомат найбільш відповідний для реалізації запропонованого користувачем алгоритму. У відповідь з сервера користувачеві приходить посилання на VHDL-файл, що є моделлю вибраного типу КА.

В ході магістерської роботи планується розробка системи автоматизованого проектування, яка враховує деякі методи оптимізації для ПЛІС. Вихідними даними програми є файли, що містять VHDL-код, що описує роботу пристрою.

Система автоматизованого проектування структури керуючого автомата (САПР СУА) ділиться на дві частини: клієнтська і серверна. Такий підхід найбільш виправданий з економічної точки зору і сточування зору обчислювальних витрат. Сервер, який бере на себе функцію перетворення просторового представлення граф-схемы алгоритму в автоматне уявлення і, в результаті, в результуючий VHDL-код. Клієнт, маючи графічний інтерфейс, дозволяє ввести граф-схему алгоритму в графічній формі і перетворити її в просторову.

Сервер має можливість динамічного оновлення або додавання методів генерації VHDL-кода. Для інтерпретації ГСА можна використовувати модель КМУУ із загальною пам'яттю [24]. (Рис.1).

Рисунок 1 — Структурна схема КМУУ із загальною пам'яттю.

Цей пристрій функціонує таким чином. По сигналу Start в лічильник СТ завантажується нульова адреса першої мікрокоманди мікропрограми, відповідною ГСА Г. Одночасно трігер вибірки TF встановлюється в одиничні стани (Fetch=1). Чергова мікрокоманда (МК) вибирається з керуючої пам'яті СМ. Якщо ця МК відповідає вершині bqog, то одночасно з набором мікрооперацій Y(bq) формується змінна y0=1. Якщо y0=1, то вміст СТ збільшується на 1 по сигналу Clock, це відповідає режиму (3), тобто перехід відбувається усередині деякого операторного лінійного ланцюга (ОЛЦ) gс. Якщо bq=og, то змінна y0=0. В цьому випадку комбінаційна схема СС формує функції збудження Ст.

Ф=Ф(Т,Х)необхідні для завантаження в СТ адреси входу деякої ОЛЦ. Адреса встановлюється в СТ по сигналу Clock. Якщо , де be — кінцева вершина ГСА, то формується змінна ye=1. Якщо ye=1, то трігер TF встановлюється в нульовий стан (Fetch=0). В цьому випадку вибірка мікрокоманд із СМ припиняється і КМУУ U1 припиняється також.

Очевидно, дане КМУУ є автоматом мура, оскільки вихідні сигнали y0, ye і Y залежать тільки від вмісту Ст. При цьому адреса мікрокоманди може розглядатися, як код стану автомата. Проте у відмінності від класичного автомата Мура, пам'ять КМУУ реалізується на лічильнику.

Плановані практичні разультати

В ході магістерської роботи планується розробка система автоматизованого проектування, яка враховує деякі методи оптимізації для ПЛІС. Вихідними даними програми є файли, котрі містять VHDL-код, що описує роботу пристрою.

В результаті практичної роботи планується отримати web-додаток, який буде реалізований з використанням технології Java-Applet. Ця технологія дозволяє використовувати додаток без необхідності його встановлення, а просто набравши певний URL в рядку адреси браузера. Технологія Java-Applet є платформонезалежною. Таким чином користувач має можливість роботи безпосередньо у вікні браузера в будь-якій операційній системі.

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

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

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

В результаті тестування роботи програми були отримані наступні дані. Як вхідний параметр були узятті три граф-схеми: граф-схема на 5 станів, 3 вхідних сигналу, 6 вихідних сигналів, перевірки умови не повторюються; граф-схема на 15 станів, 3 вхідних сигналу, 6 вихідних сигналів, перевірки умови не повторюються; граф-схема на 35 станів, 3 вхідних сигналу, 6 вихідних сигналів, перевірки умови не повторюються.

Синтез пристроїв на інтегральній схемі Xilinx Coolrunner Xpla3:

Таблиця 1 — Результат синтезу

Рисунок 2 — Діаграма порівняння

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

Результати, отримані за допомогою САПР СУА, показують, що засоби синтезу мають достатньо розвинені алгоритми пошуку у вхідному VHDL-коде структур кінцевих автоматів. А деякі типи ПЛІС мають вентилі, що дозволяють спростити апаратну структуру коду, що генерується. Завдяки чому поведінковий метод не поступається тривіальному. Але це вірно не для всіх типів ПЛІС.[27]

Огляд існуючих розробок по темі

Глобальний

Про актуальність теми кінцевих автоматів свідчить наявність редакторів FSM (finite state machine) в таких продуктах як AHDL і Riviera. Найбільш поширеними серед мов опису апаратури є мови VHDL і Verilog. Проте безпосередня реалізація керуючих автоматів на цих мовах є трудомістким процесом. Тому до складу багатьох зарубіжних САПР були включені спеціальні інструменти, що дозволяють спростити розробку керуючих автоматів. Так до складу САПР Active-HDL фірми Aldec включений модуль FSM. Цей модуль володіє багатофункціональним графічним інтерфейсом, для опису керуючих автоматів. Проте модуль FSM володіє рядом недоліків. Зокрема, форма запису керуючого автомата вимагає знання мови HDL. Так само організовані системи проектування керуючих автоматів і в інших САПР.

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

Недолік FSM-редактора A-HDL-генерація програмного коду в поведінковому стилі, що робить неможливим передбачити результат синтезу. Структурний же опис схеми, отриманої в результаті тривіальної реалізації, дає можливість прогнозу результатів ще до синтезу — на етапі генерації програмного коду, що дає можливість генерувати код для кристала або числа вентилів FPGA заданої розмірності.

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

При унарному кодуванні станів автомата зменшується кількість необхідних для реалізації схеми інверторів. Це відбувається за рахунок відсутності необхідності інвертування розрядів коду станів.

Таким чином, плюсами цього методу, є менша складність функцій збудження (особливо виявляється при зменшенні разветленності автомата) і відповідно вища швидкодія автомата. Недоліками є значно велика кількість використовуваних схем трігерів (особливо виявляється при збільшенні станів графа : R ~ M, при унарному кодуванні; R ~ log 2 M, при бінарному кодуванні ); і велика апаратна затратность схем формування вихідних сигналів (за відсутності в ПЛІС елементів XOR ).

Відомі, проте, і інші методи оптимізації структури автоматів на ПЛІС.

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

Одним з найбільш перспективних способів дозволу цієї проблеми є використання для проектування апаратних систем, засобів заснованих на раніше розроблених засобах проектування складних систем для програмного забезпечення, таких як використання керованої моделями архітектури ( MDA — Model — Driven Architecture ) і уніфікована мова моделювання ( UML — Unified Modeling Language ).

MDA була запропонована групою OMG ( Object Management Group ) в 2000 році. Головною ідеєю MDA є опис складних систем у вигляді набору моделей, що стоять на різних рівнях абстракції, щодо один одного, і можливість перетворення моделей одного рівня в моделі іншого рівня абстракції. Результатом таких перетворень є отримання реалізацій незалежної від платформи моделі, для різних платформ.

В даний час існує безліч середовищ проектування, що підтримують керовану моделями архітектуру і мову UML для опису моделей, які орієнтовані на розробку програмного забезпечення ( Eclipse, Netbeans, Jbuilder_x, Poseidon, ARGOUML і так далі). Багато хто з цих середовищ є розширюваними продуктами (тобто до них можна підключати додаткові модулі сторонніх розробників), тому було ухвалено рішення побудувати САПР для керуючих автоматів на базі одного з наявних середовищ проектування. Як базове середовище був вибраний JBuilder 2006.

Локальний

До подібних розробок можна віднести роботи наступних Магістрів ДонНТУ:

Поточні і плановані результати по темі

Розглянь приклад синтезу КМУУ по ГСА Г1 (Рис.3.)

Рисунок 3 — Початкова ГСА Г1

Використовуючи методи з [4], можна отримати безліч С={б1, б2, б3}, де d1= I=b1, I=o1=b2; І2=, I=b3, I=b4, O2=b5; б3==, I=b6, O3=b8. Отже, G=3, M=8, R=3, T={T1, T2, T3} ={D1, D2, D3}, X={x1, x2}, L=2, Y={y1, y2, y3, y4, y5, y6}, N=6, I()={b1, b2, b3, b4,b6}, O()={b2, b5, b8}, C1={ б1, б2}.

Природна адресація мікрокоманд [3] дозволяє отримати наступні адреси: A(b1)=000, A(b2)=001, ., A(b8)=111. Формули переходу будуються для виходів ОЛЦ, тобто для О1 і О3.

Система має H=4 терма, отже, таблиця переходів КМУУ має H=4 рядка (Табл.1).

Таблиця 2 — Таблиця переходів КМУУ

Зміст керуючої пам'яті КМУУ зображено в Табл.2, яка аєм М=8 строк.

Таблиця 3 — Зміст керуючої пам'яті КММУ

На наступному кроці рішення даної задачі виконується формування XML-файлу, який містить інформацію по початковій ГСА. Вміст XML-файлу приведений на рисунку 4.

Рисунок 4 — Вміст XML-файлу

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

Процес розробки УА на ПЛІС зображений на рисунку 5

Рисунок 5 — Процес розробки УА на ПЛІС

Анімація: 8 кадрів, вага — 47492 байти, розмір — 760х241

Література

    Роботи магістрів минулих років

  1. Бережок Олексій Юрійович:
  2. Боровлев Артем Сергійович:
  3. Войтенко Сергій Аркадійович:
  4. Данилов Максим Васильович:
  5. Костянок Тятьяна Миколаївна:
  6. Силуанов Антон Федорович:
  7. Скоропад Олександр Сергійович:
  8. Цололо Сергій Олексійович:
  9. Шишко Сергій Миколайович:

    Іноземні дослідницькі группи, котрі займаються подібними розробками

  10. Университет Аугзбурга
  11. Факультет комп'ютерних наук технічного університету Дрезденського
  12. Лабораторія систем управління університету Карлсруе (Німеччина)
  13. Ізраїльськая асоціація автоматичного управління (IAAC)
  14. Центр дослідження комплексних автоматизованих систем (Болонський університет, Італія)
  15. Зеленогурський університет (Польща)
  16. Владімірський державний університет
  17. Моськовський Державний Інститут Електронної Техніки

    Печатні джерела та посилання

  18. Кей З. Хорстман, Гарі Корнелл «Java 2. Бібліотека професіонала»;
  19. Г. Шилдт «Повний довідник по Java»;
  20. Баркалов А.А. Мікропрограмний пристрій управління як композиція автоматів з програмованою і жорсткою логікою. Автоматика і обчислювальна техніка, 1983 №4.-с.36-41.
  21. Barkalov A.A., Titarenko L.A. Synthesis of operational and control automate.- Donets’с: Untech, 2005.-25pp.
  22. Maxfield C. The Design Warrior’s Guide for FPGA.-Amsterdam: Elsevier, 2004.-541 p.
  23. Smith M. Application – Specific Integrated Circuits. — Boston: Addison — Wesley, 1997.-836 pp.
  24. Baranov S. Logic Synthesis for Control Automate. — Boston: Kluwer Academic Publishers, 1984.-312pp.
  25. lexvit.dn.ua / Дослідження структур керуючих автоматів з елементарізаціей лінійних послідовностей станів / [Електронний ресурс] — режим доступу: http://www.lexvit.dn.ua/arhiv/articles.php?art_id=ua_java1
Про автора