ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

АДНАН ІБРАХІМ СУЛЕЙМАН АЛЬ-РАБІЄ

(ЙОРДАНІЯ)

УДК 681.324

МЕТОДИ СИНТЕЗУ БАГАТОРІВНЕВИХ СХЕМ

КОМПОЗИЦІЙНИХ МІКРОПРОГРАМНИХ

ПРИСТРОЇВ КЕРУВАННЯ

Спеціальність 05.13.13 – Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Донецьк – 2004

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

Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Баркалов Олександр Олександрович, професор кафедри “Електронні обчислювальні машини” Донецького національного технічного університету.

Офіційні опоненти: доктор технічних наук, професор Скобцов Юрій Олександрович, завідувач кафедри “Автоматизовані системи управління” Донецького національного технічного університету,

кандидат технічних наук, доцент Вороний Сергій Михайлович, завідувач кафедри “Технічна інформатика” Донецького державного інституту штучного інтелекту.

Провідна установа: Харківський національний університет радіоелектроніки, кафедра автоматизації проектування обчислювальної техніки, Міністерства освіти і науки України, м. Харків.

Захист відбудеться “01” липня 2004 р. о 13 годині на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного технічного університету за адресою: 83000, м. Донецьк, вул. Артема, 58, I н. корп., ВАЗ.

З дисертацією можна ознайомитись у бібліотеці ДонНТУ (адреса: 83000, м. Донецьк, вул. Артема, 58, II н. корп.)

Автореферат розісланий “24” травня 2004 р.

Вчений секретар

спеціалізованої вченої ради К 11.052.03

кандидат технічних наук, доцент Г.В. Мокрий

Загальна характеристика роботи

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

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

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

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

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

Мета і задачі досліджень. Метою роботи є мінімізація числа ВІС у схемах автоматів адресації КМПК за рахунок застосування методів структурної редукції.

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

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

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

2. Розробка структур і методів синтезу КМПК з кодуванням логічних умов автомата адресації.

3. Розробка структур і методів синтезу КМПК з перетворенням номерів переходів.

4. Розробка структур і методів синтезу КМПК з перетворенням об'єктів, під якими розуміються стани автомата адресації, адреси мікрокоманд, коди операторних лінійних ланцюгів (ОЛЛ), коди класів псевдоеквівалентних ОЛЛ.

5. Отримання аналітичних оцінок апаратурних витрат в схемах КМПК при реалізації їх в базисі замовлених матричних схем.

6. Дослідження розроблених структур і методів синтезу КМПК з метою визначення області їх ефективного застосування.

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

Предмет дослідження – методи оптимізації апаратурних витрат у схемах КМПК на програмувальних логічних пристроях.

Методи дослідження. В процесі досліджень застосовувався формальний апарат теорії кінцевих автоматів, теорії множин і булевої алгебри. При синтезі схем використовувалася методологія В.М. Глушкова, деталізована в роботах С.І. Баранова, О.В. Палагіна, О.О. Баркалова, В.А. Склярова, В.В. Соловйова.

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

1. Уперше показана можливість застосування методів оптимізації автоматів з “жорсткою” логікою (методів структурної редукції) для зменшення апаратурних витрат в автоматі адресації КМПК.

2. Показано, що застосування методу перетворення об'єктів дозволяє до 40% зменшити апаратурні витрати в схемах КМПК з представленням адреси мікрокоманди у вигляді конкатенації коду ОЛЛ і адреси компонента в порівнянні з раніше відомими структурами.

3. Уперше розроблені методи синтезу КМПК з перетворенням номерів наборів при використанні традиційних структур КМПК і структур з розподілом кодів.

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

Особистий внесок здобувача. Основні положення і результати дисертаційної роботи отримані автором самостійно.

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

Апробація роботи. Основні положення і результати роботи доповідалися й обговорювалися на: міжнародної науково-технічної конференції “Машиностроение и техносфера XXI века” (Севастополь, вересень 2003 р.); семінарах Інституту прикладної математики і механіки НАН України і кафедри ЕОМ ДонНТУ.

Публікації. Зміст роботи відбитий у 5 публікаціях, у яких авторові належать структури і методи синтезу КМПК, що дозволяють скоротити число ВІС у схемі автомата адресації мікрокоманд. З цих робіт 4 опубліковано в наукових журналах, одна – у працях міжнародної конференції.

Реалізація результатів роботи. Отримані в роботі результати реалізовані у вигляді методик синтезу КМПК з багаторівневою структурою і використані на кафедрі ЕОМ ДонНТУ при читанні лекцій, в курсовому і дипломному проектуванні.

Структура й обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, викладених на 159 сторінках машинописного тексту, містить 105 рисунків і 59 таблиць. Список використаних джерел складається зі 102 найменувань і розташований на 8 сторінках.

Основний зміст

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

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

Алгоритми керування цифрових систем можуть бути реалізовані у вигляді автомата з “жорсткою” логікою, пам'ять якого реалізована на тригерах. У практиці інженерного проектування алгоритм керування прийнято представляти у вигляді граф-схеми алгоритму (ГСА) Г=Г(B,E), де B – безліч вершин, E – безліч дуг. В процесі синтезу формується пряма структурна таблиця (ПСТ), що відбиває інформацію про переходи між станами amA={a1, …, aM} автомата під дією логічних умов xlX={x1, …, xL} з формуванням мікрооперацій ynY={y1, …, yN} і містить H рядків.

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

1. Кодування логічних умов xlX змінними із безлічі P, причому |P|<<L.

2. Кодування рядків ПСТ.

3. Перетворення кодів об'єктів, під якими розуміються стани amA і набори мікрооперацій YtY.

У роботах О.О. Баркалова запропоновано реалізовувати алгоритм керування у вигляді КМПК, що представляє собою композицію автоматів з “жорсткою” і “програмувальною” логікою (рис. 1).

У КМПК U1 комбінаційна схема КС і регістр пам'яті РП реалізують автомат адресації, що формує адреси мікрокоманд, що зберігаються в керуючій пам'яті КП. Лічильник адреси мікрокоманд СТ і КП являють собою автомат з “програмувальною” логікою і природною адресацією мікрокоманд. Синтез КМПК заснований на формуванні безлічі операторних лінійних ланцюгів C={1, …, G} і природній адресації мікрокоманд, що відповідають вершинам ОЛЛ.

Під ОЛЛ gC розуміється кінцева послідовність операторних вершин, така що для кожної пари компонентів bgi, bgi+1 ОЛЛ g є дуга <bgi, bgi+1>E, де i – номер компонента ( ). Кожен ОЛЛ має не менш одного входу і точно один вихід.

КМПК U1 функціонує таким способом. Нехай в момент часу t=0, 1, 2, … в СТ знаходиться адреса деякої мікрокоманди A(bq), де bqB. Якщо bq не є виходом ОЛЛ, то одночасно з набором YtY формується сигнал y0, що збільшує вміст СТ на одиницю і забороняє зміну коду стану в РП. Таким чином відбувається перехід до наступного компонента ОЛЛ gC. Якщо вихід ОЛЛ g досягнуто, то схема КС формує сигнали rФ=Ф(, X), які формують у СТ адресу входу чергового ОЛЛ iC, і r=(, X), що формують у РП код наступного стану автомата адресації. Адреси мікрокоманд кодуються змінними TrT, де |T|=R2=]log2M2[, де M2 – потужність безлічі мікрокоманд. Стани автомата адресації кодуються змінними r, де ||=R1, R1=]log2M1[, де M1 – потужність безлічі станів.

Існують модифікації КМПК U1, що називається КМПК з базовою структурою:

1. КМПК U2 із загальною пам'яттю, у якому адреси виходів ОЛЛ є одночасно і кодами станів, що виключає зі схеми КМПК регістр РП і зменшує число виходів схеми КС.

2. КМПК U3 із загальною пам'яттю і перетворювачем адрес виходів ОЛЛ у коди класів псевдоеквівалентних ОЛЛ, під якими розуміються ОЛЛ, виходи яких зв'язані зі входами однієї і тієї ж вершини ГСА. Цей підхід зменшує число входів схеми КС.

3. КМПК U4 з розподілом кодів (рис. 2), засноване на представленні адреси A(bq) у вигляді конкатенації кодів ОЛЛ K(g) і коду компонента K(bt), що відповідає вершині btB.

Такий підхід дозволяє зменшити число входів і виходів схеми КС при виконанні умови

R1 + R3 = R1, (1)

де R3 – розрядність коду компоненти.

4. КМПК U5 з розподілом кодів і перетворювачем коду ОЛЛ в код класу псевдоеквівалентних ОЛЛ gC. Тут відбувається подальше зменшення числа входів схеми КС.

5. КМПК U6 (U7) – аналог КМПК U4 (U5), у якому всі ОЛЛ є елементарними, тобто мають точно один вхід. Такий підхід дозволяє не формувати функції Ф, що зменшує число виходів схеми КС.

В дисертаційній роботі пропонується використовувати для оптимізації вартості схем КМПК Ui ( ) методи структурної редукції автоматів з “жорсткою” логікою. Такий підхід породжує наступні структури КМПК:

1. MUi, у яких M-підсхема використовується для кодування логічних умов. Ця структура припускає модифікації, зв'язані з уточненим кодуванням станів і перетворенням кодів станів у коди логічних умов.

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

3. TSi, у яких уводиться перетворювач адреси мікрокоманди в код стану автомата адресації.

У роботі вирішуються наступні основні задачі:

1. Розробка методів синтезу схем КМПК MUi, TUi, TSi, TAi, ( ) по граф-схемі алгоритму.

2. Дослідження області ефективного застосування запропонованих структур логічних схем КМПК.

В другому розділі розглянуті структури і методи синтезу КМПК U1-U3, що не використовують принцип розподілу кодів, засновані на використанні методів структурної редукції.

У роботі запропоновані структури КМПК MU1-MU3, а також їх модифікації. На рис. 3 приведена структурна схема КМПК MU1, у якій M-підсхема реалізує метод кодування логічних умов і формує змінні

, (2)

де Ckm – булева змінна, яка дорівнює одиниці, якщо і тільки якщо в стані amA змінна xlX замінюється змінною pkP.

Тепер P-підсхема реалізує систему Ф=Ф(, P) і =(, P), для формування якої необхідно перетворити вихідну ПСТ.

Як показали дослідження, у рівняннях (2) для різних структур MU1-MU3 знаходяться різні об'єкти. Для КМПК MU1 використовуються кон’юнкція Am змінних r, що відповідає кодові K(am); для КМПК MU2 – кон’юнкція змінних TrT, що відповідає адресі виходу ОЛЛ gC; для КМПК MU3 – кон’юнкція змінних vrV, що кодують I класів псевдоеквівалентних ОЛЛ BiПC={B1, …, BI}, де ПC – розбивка безлічі C на класи псевдоеквівалентних ОЛЛ. Це породжує різні підходи до оптимізації M-підсхеми, що реалізується на мультиплексорах.

У роботі запропонована структура КМПК TU1 (рис. 4), у якій перетворювач кодів ПК перетворює коди переходів у функції Ф и .

Під переходом Fk автомата адресації розуміється вектор <k, Фk>, що містить функції і Ф, які приймають одиничні значення в h-му рядку ПСТ, FkF0, де |F0|=KH.

Для кодування переходів FkF0 використовуються змінні zrZ, де |Z|=R4

R4=]log2K[. (3)

Для синтезу P-підсхеми необхідно перетворити вихідну ПСТ і одержати систему функцій Z=Z(, X). У КМПК TU1 ПК реалізується на ПЗП, що дозволяє скоротити кількість дорогих ВІС ПЛМ або ПМЛ, що реалізують P-підсхему в порівнянні зі схемою КС.

Аналогічні структури запропоновані для КМПК U2 і U3, однак методи їх синтезу докладно не розглядаються, тому що вони збігаються з методом синтезу КМПК TU1.

У дисертаційній роботі пропонується виразити адресу A(bt) мікрокоманди як конкатенацію кодів стану з ПСТ і ідентифікатора

A(bt)=K(as)*K( ), (4)

де K(as) – код стану переходу автомата адресації, K( ) – код ідентифікатора, що визначає мікрокоманду, яка відповідає вершині btB, адреса якої формується при переході в стан asA, “*” – знак конкатенації. Нехай для кодування ідентифікаторів використовуються змінні zrZ, тоді цей принцип породжує КМПК US1 (рис. 5).

Тут схема ПК реалізує систему функцій

, (5)

де – кон’юнкція змінних r, що відповідає коду K(as) стану asA з h-го рядка ПСТ, Zh – кон’юнкція змінних zrZ, що відповідає коду ідентифікатора з h-го рядка таблиці ПК, – номер рядка таблиці ПК (H0 H).

У роботі запропонований метод синтезу КМПК US1 по ГСА і показано, що його застосування дозволяє зменшити число виходів ПЛП P-підсхеми при виконанні умови

(R1 + R2 > t) & (R1 + Q1 t) = 1, (6)

де t – число виходів ПЛП, Q1=|Z|. Цей метод не може бути застосований для КМПК U2 і U3, тому що їхні автомати адресації не мають явно виражених станів.

У дисертаційній роботі пропонується структура КМПК UA1 (рис. 6) з перетворенням адреси мікрокоманди в код стану автомата адресації.

У роботі доведено, що адреса мікрокоманди однозначно визначає стан, і додаткові ідентифікатори не потрібні. При наявності вільних виходів КП цей метод може бути реалізований, використовуючи вільні виходи КП для формування змінних =(T), що породжує КМПК . У роботі запропоновані методи синтезу КМПК і UA1 і показано, що застосування методів доцільно, якщо економія вартості P-підсхеми в КМПК U1 перевершує вартість ПА.

В роботі показано, що застосування цих методів для КМПК U2 і U3 неможливо.

У третьому розділі розглянуті структури і методи синтезу КМПК U4-U7, засновані на застосуванні методів структурної редукції.

У роботі запропоновані структури і методи синтезу КМПК з розподілом кодів і кодуванням логічних умов. Показано, що процедури заміни й оптимізації для КМПК MU4-MU7 виконуються аналогічно, але в ПСТ використовуються різні об'єкти: ОЛЛ (MU4), класи BiПC псевдоеквівалентних ОЛЛ (MU5), елементарні ОЛЛ (MU6), класи псевдоеквівалентних елементарних ОЛЛ (MU7).

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

У роботі запропонована структурна схема (рис. 7) і метод синтезу КМПК TU4, у якій ПК використовується для перетворення номера переходу у функції керування СТ і РП.

Показано, що методи синтезу КМПК TU4-TU7 багато в чому збігаються, але для КМПК TU4-TU7 під переходом розуміється набір функцій збудження РП. При синтезі КМПК TU5 і TU7 додається етап синтезу перетворювача кодів ОЛЛ у коди класів псевдоеквівалентних ОЛЛ.

В дисертаційній роботі запропоновані структури і методи синтезу КМПК US4-US7, засновані на перетворенні коду ОЛЛ на адресу мікрокоманди. Показано, що ці методи доцільно застосовувати при виконанні умов

R3 + R4 > R2, (7)

R5 + R6 > R2,

де R3, R5 – розрядність коду ОЛЛ і елементарного ОЛЛ відповідно, R4, R6 – розрядність коду компоненти в КМПК U4, U5 і U6, U7 відповідно.

Показано, що в КМПК US6 і US7 відсутні ідентифікатори для визначення адреси входу, що для КМПК US6, наприклад, породжує структуру (рис. 8).

Тут ПК формує функції Ф=Ф(), що адресують мікрокоманду в КП. При виконанні умови (2) ємність КП не буде надлишковою в порівнянні з КМПК U1, тому що |Ф|=R2. Такий підхід дозволяє зменшити вимоги до числа виходів ПЛП P-підсхеми до t=R5 при збереженні мінімальної розрядності адреси КП.

У четвертому розділі наводяться результати дослідження розроблених методів і визначаються області їхнього застосування.

Аналіз методів кодування логічних умов стосовно до КМПК U1-U7 показав, що ці методи відрізняються тільки об'єктами перетворення, під якими розуміються елементи, що знаходяться в першому стовпці ПСТ автомата адресації. Існує шість типів об'єктів (стан, адреса виходу ОЛЛ, код ОЛЛ, код класу ОЛЛ, код елементарного ОЛЛ, код класу елементарних ОЛЛ), але вони не впливають на методи кодування логічних умов і оптимізацію апаратурних витрат у M-підсхемі. На підставі цього аналізу розроблена узагальнена методика кодування логічних умов, що дозволяє зменшити число модулів САПР синтезу КМПК MU1-MU7.

При дослідженні методів синтезу, запропонованих у роботі, використаний імовірнісний підхід (Г.І. Новіков), при якому будь-яка ГСА характеризується частками операторних (p1) і умовних (p2) вершин у ній. Ці параметри можна розглядати як імовірності того, що довільна вершина ГСА буде операторною або умовною (p1+p21). Такий підхід дозволяє досліджувати не окремі ГСА, а їхні класи, виділені по параметрах p1 і p2.

Другою особливістю досліджень є перехід від схем на стандартних ПЛП до схем на замовлених матрицях і визначення відносної ефективності розроблених структур і традиційних схем КМПК U1-U7. Як показано в роботах О.О. Баркалова, відносні витрати числа ВІС і площі замовлених ВІС для різних структур ПК збігаються з точністю до 0.89-0.92%. Це дозволяє спростити процес вибору оптимальної схеми КМПК.

Відомо, що основні параметри автомата можуть бути виражені через число вершин ГСА і деякі коефіцієнти:

1. Число рядків ПСТ автомата Мілі

H = 4.44 + 1.44p1K/p3. (8)

2. Число станів автомата Мілі

M = 3.55 + 0.44p1K/p3. (9)

3. Число логічних умов у ГСА

L = (1-p1)K/p4. (10)

Тут K – число вершин ГСА, p3{1; 1.2} – відношення числа операторних вершин до числа різних наборів мікрооперацій, p4{1; 1.2} – відношення числа умовних вершин до числа логічних умов. Використовуючи матричну структуру схеми КМПК U1, наприклад, і формули (8)-(10), можна одержати формули, що оцінюють площу S(S1(U1)), яку займає автомат адресації, і площу S(КП), яку займає керуюча пам'ять:

(11)

, (12)

де p5 – відношення числа вершин перетвореної ГСА Г’ до числа вершин вихідної ГСА. Формула (12) є загальною для всіх відомих структур КМПК.

У дисертаційній роботі отримані формули для всіх вихідних структур КМПК (U1-U7) і структур, запропонованих у роботі. У роботі досліджувалися два класи функцій – без обліку КП і з обліком КП. Показано, що при уведенні вартісного коефіцієнта, що враховує відносну вартість ПЗП КП і інших ПЛП, керуюча пам'ять впливає незначно на загальний виграш у вартості.

Застосування перетворювача номера переходів у КМПК U1 завжди ефективно, причому виграш збільшується при зменшенні числа операторних вершин ГСА Г, зменшення числа вершин перетвореної ГСА Г’ і числа переходів стосовно числа рядків ПСТ. Максимальний виграш досягає 17%.

Введення в КМПК U1 перетворювача коду стану автомата адресації в адресу мікрокоманди дозволяє домогтися виграшу до 30% (p1=0.95, p5=p14=0.1, K=100, p14 – відношення розрядності коду ідентифікатора до розрядності адреси). Виграш зменшується при рості числа вершин ГСА Г и Г’, а також при рості потужності безлічі ідентифікаторів.

Перетворення адреси мікрокоманди в код стану автомата адресації в КМПК U1 завжди дає позитивний ефект. Виграш збільшується при рості числа вершин ГСА Г і Г’ і зменшенні загального числа вершин, досягаючи 27%.

Застосування методу перетворення номера переходу в КМПК U2 і U3 не завжди приводить до виграшу. Ефективність методу підвищується при рості числа вершин ГСА і зменшенні числа ОЛЛ і частки операторних вершин у них. Максимальний виграш може досягати 14% (TU2).

Застосування всіх методів оптимізації для КМПК U4 і U5 більш ефективно, чим для КМПК U6 і U7, у яких менші вимоги до числа виходів ПЛП P-підсхеми.

Перетворення номера переходу дає найбільший ефект для КМПК U4 (виграш досягає 26%), причому виграш тим більше, чим менше вершин містить ГСА і чим менше переходів має автомат адресації стосовно довжини ПСТ. При цьому виграш практично не залежить від частки операторних вершин у ГСА. У КМПК U5 виграш не перевищує 12%, причому він підвищується при рості числа вершин ГСА і зменшенні частки операторних вершин.

Найбільший виграш у КМПК U4-U7 досягається при введенні перетворювача коду ОЛЛ на адресу мікрокоманди. Для КМПК U4 він досягає 42% і збільшується при рості числа операторних вершин, зменшенні числа вершин і відносної розрядності коду ідентифікаторів p14.

ВИСНОВКИ

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

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

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

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

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

1. Баркалов А.А., Аль-Рабие Аднан, Красичков А.А. Оптимизация логической схемы композиционного микропрограммного устройства управления // Радіоелектроніка. Інформатика. Управління. Вип. 2 – Запоріжжя, Запорізький національний технічний університет, 2002. – С. 54-57.

2. Баркалов А.А., Аль-Рабие-Аднан, Саломатин В.А. Синтез композиционного микропрограммного устройства управления с преобразователем кодов состояний в адреса микрокоманд // Зб. наукових праць ДДТУ. Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. Вип. 52. – Донецьк, ДонНТУ, 2002. – С. 72-76.

3. Баркалов А.А., Ковалев С.А., Аль-Рабие Аднан. Синтез оптимальной схемы адресации композиционного микропрограммного устройства управления // Збірник праць X міжнародної науково-технічної конференції “Машиностроение и техносфера XXI века”. – Донецьк, ДонНТУ, 2003. Т. 1. – С. 62-66.

4. Баркалов О.О., Аднан А.-Р., Красічков О.О. Оптимізація автомата адресації композиційного мікропрограмного пристрою керування // Вісник Донецького університету. Серія А – природні науки. Вип. 2. – Донецьк, Донецький національний університет, 2002. – С. 371-374.

5. Баркалов А.А., Аль-Рабие Аднан, Ковалев С.А. Оптимизация схемы адресации композиционного микропрограммного устройства управления // Зб. наукових праць ДонНТУ. Серія “Обчислювальна техніка та автоматизація”. Вип. 64. – Донецьк, ДонНТУ, 2003. – С. 137-143.

Особистий внесок здобувача в публікаціях: [1] – Структура і формальний метод синтезу КМПК з перетворенням номерів переходів; [2] – Метод оптимізації схеми КМПК, заснований на перетворенні кодів стану автомата адресації в адреси мікрокоманд; [3] – Метод оптимізації схеми адресації КМПК, що організований як автомат Мілі; [4] – Структура, метод синтезу і дослідження КМПК з використанням адреси мікрокоманди для формування коду стану автомата адресації мікрокоманд; [5] – Структура і формальний метод синтезу КМПК з формуванням стану автомата адресації за допомогою керуючої пам'яті.

АНОТАЦІЯ

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

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

На основі теоретичних і експериментальних досліджень в роботі запропоновані нові структури та формальні методи синтезу композиційних мікропрограмних пристроїв керування. Показано, що оптимізація апаратурних витрат у схемі формування адреси мікрокоманди може бути отримана, якщо використовувати методи багаторівневої реалізації автоматів з „жорсткою” логікою, які повинні бути адаптовані до особливостей композиційних мікропрограмних пристроїв керування. Запропоновано використовувати методи кодування логічних умов, перетворення номерів переходів, кодів станів, кодів операторних лінійних ланцюгів та їх класів, а також адреси мікрокоманд. Розроблено нові структури та методи синтезу для всіх відомих композиційних мікропрограмних пристроїв керування. Запропоновані в роботі методи дозволяють зменшити апаратурні витрати в схемі автомата адресації на 12-42% у порівнянні з відомими методами синтезу. Отримані аналітичні оцінки складності апаратурних витрат у схемах пристроїв керування як функції від параметрів граф-схеми алгоритму. Запропоновані методи дозволяють розширити клас синтезованих пристроїв керування. Проведені дослідження дозволили визначити область ефективного використання запропонованих структур композиційних мікропрограмних пристроїв керування.

Ключові слова: композиційні мікропрограмні пристрої керування, операторні лінійні ланцюги, програмувальні логічні пристрої, автомати з „жорсткою” логікою.

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. – Донецкий национальный технический университет, Донецк, 2004.

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

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

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

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

Проведено исследование предложенных методов с целью определения области их эффективного применения. В основу методики исследований положен переход от стандартных БИС к заказным матричным схемам, площадь кристалла которых определяется суммой площадей матриц “И” и “ИЛИ”. Для исследования эффективности методов в зависимости от структуры реализуемой ГСА использовано вероятностное задание характеристик исходных граф-схем алгоритма. К таким характеристикам относятся общее число вершин ГСА, доля операторных и условных вершин, число логических условий, число строк прямой структурной таблицы и другие.

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

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

ABSTRACT

Adnan Ibrahim Suliman Al-Rabie. The methods of synthesis of multilevel compositional microprogram control units. – Manuscript.

The Dissertation on competition of a scientific degree of the candidate of technical sciences on a speciality 05.13.13 – computers, systems and networks. – Donetsk national technical university, Donetsk, 2004.

On the basis of theoretical and experimental researches the new structures and formal methods of compositional microprogram control units design are proposed. It is shown that optimization of hardware in the unit of microinstructions’ addressing can be achieved by application of the methods of multilevel implementation of automata with “hardware” logic, that need adaptation to the peculiarities of compositional microprogram control units. It is proposed to use the methods of the logic conditions’ encoding, the codes of the states, the codes of the operational linear chains and their classes, and also the addresses of microinstructions. The new structures and methods of design were developed for all known structures of compositional microprogram control units. The proposed methods permit to decrease the amount of programmable logic devices in the automaton of addressing’s circuit from 12% to 42% in comparison with known methods of design. The analytical estimations of hardware amount as the function of characteristics of initial flow-chart have been made up. These methods permit to expand the class of synthesizable control units. The conducted researches permit to find an area of the effective application of proposed methods of design.

Key words: compositional microprogram control units, operational linear chains, programmable logic devices, automata with hardware logic.