Донецький НАЦІОНАЛЬНИЙ технічний університет

УДК 518.610

Черкашин Вячеслав Анатолійович

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

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

Автореферат

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

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

ДОнецьк 2001

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

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

Науковий керівник: д.т.н., проф. Баркалов Олександр Олександрович,

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

Офіційні опоненти: д.т.н., доц. Скобцов Юрій Олександрович,

завідувач кафедри “Автоматизовані системи управління” Донецького національного техничного університету.

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

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України, відділ 205 , м. Київ

Захист відбудеться “ 11 ” жовтня 2001р. о 14 годині на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного техничного університету (адреса : 83000 м.Донецьк вул. Артема 58 I уч. корп. ауд. 201)

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

Автореферат розісланий “ 10 ” вересня 2001р

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

спеціалізованої вченої Мокрий Г.В.

ради

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

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

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

Керуючий автомат може бути реалізований як композиція автоматів з "жорсткою" та "програмуємою" логікою. Такі автомати були запропоновані О.О. Баркаловим і названі композиційними мікропрограмними пристроями керування(КМПК). У КМПК досягається мінімально можлива кількість керуючої пам'яті і максимальна швидкодія. При цьому актуальною є проблема зменшення числа мікросхем в автоматі з "жорсткою" логікою. Один з шляхів вирішення цієї задачі - зменшення числа входів і виходів автомата за рахунок розділення процесів кодування станів автомата з "жорсткою" логікою і адресації мікрокоманд автомата з "програмуємою"логікою.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.

2.

3.

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

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

На захист виносяться:

1.

2.

3.

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

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

1.

2.

3.

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

Реалізація результатів роботи. Отримані в роботі результати реалізовані у вигляді методик синтезу композиційних мікропрограмних пристроїв керування з поліпшеними характеристиками і використані в практичних розробках Інституту кібернетики НАН України, а також на кафедрі ЕОМ ДонГТУ при читанні лекцій, в курсовому і дипломному проектуванні.

Структура і об'єм роботи. Діссртаційна робота складається з вступу, чотирьох розділів, висновку і двох додатків викладених на 115 сторінках машинописного тексту, містить 60 рисунків, 39 таблиць. Список використаних джерел складається з 84 найменувань і розташований на 6 сторінках.

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

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

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

Алгоритми керування систем цифрової автоматики можуть бути реалізовані схемним шляхом з використанням композиційних мікропрограмних пристроїв керування (КМПК), що являють собою композицію автоматів з "жорсткою" і "програмуємою" логікою (рис. 1).

Рис 1 - структурна схема композиційного мікропрограмного пристроя керування U0.

У КМПК U0 комбінаційна схема КС і регістр пам'яті РП являють собою автомат з "жорсткою" логікою S1, що служить для адресації мікрокоманд при порушенні природного порядку їх проходження. Керуюча пам'ять КП, що зберігає мікропрограму, і лічильник адреси мікрокоманд СЧАМК являють собою автомат S2 з "програмуємою" логікою і природною адресацією мікрокоманд. Метод синтезу КМПК заснований на формуванні в початковій ГСА Г множини операторних лінійних ланцюгів (ОЛЛ) С = 1,…,G і природною адресацією мікрокоманд в кожній ОЛЛ GС.

Нехай задана ГСА Г = Г(В, Е), де В - безліч вершин, Е - безліч дуг. ОЛЛ GС називається кінцева послідовність вершин G = bg1,…,bgFg, така, щоbgi,bgi+1, где i1,…,Fg-1. Кожна ОЛЛ має як мінімум один вхід і точно один вихід.

У КМПК U0 функціонує таким чином. По сигналу "Пуск" в СЧАМК і РП заносяться нульові адреса і код стану відповідно. Нехай в момент часу t автомат S1 перейшов в стан аmА1, где А1 = а1,…аМ1 - безліч станів автомата S1, і заніс в СЧАМК адресу j - го входу ОЛЛ GС.. Якщо цей вхід не є і виходом, то автомат S2 формує набір мікрооперацій з безлічі у1,…,уN і сигнал у0. По сигналу у0 до СЧАМК додається одиниця, адресуючи чергову мікрокоманду. При досягненні виходу ОЛЛ g сигнал у0 не формується і чергова адреса переходу заноситься в СЧАМК функціями 1,…,R, де R = log2 M, де М - число мікрокоманд в КП.

Одночасно автомат S1 формує функцію 1,…,R0,де R0 = log2 M1, для переходу в черговий стан аS = (аm,Х), де - функція переходу, Х = х1,…,хL - безліч вхідних сигналів (логічних умов).Функціонування продовжується до досягнення кінця програми

При виконанні умови

R = R0 (1)
доцільно сумістити функції СЧАМК і РП в СЧАМК, що приводить до економії числа виходів в КС і породжує структуру U1 (рис.2а). Для оптимізації числа входів КС при виконанні умови

R log2 G = R1 (2)
в структуру U1 можна ввести перетворювач адреси ОЛЛ в її код (ПА), що породжує структуру U2 (рис. 2б).

Рис 2. - Структурні схеми КМПК з загальною памяттю U1 (а) та з перетворювачем адреси U2 (б).

Автомат S1 в КМПК U1 - U2 є автоматом Мура і для його оптимізації можуть бути використані всі відомі методи, запропоновані в роботах О.О. Баркалова. Однак внаслідок того, що коди станів жорстко пов'язані з адресами мікрокоманд, то використання відомих методів оптимізації неможливе.

У дисертаційній роботі пропонується метод представлення адреси мікрокоманди Оg у вигляді, що дозволяє довільно кодувати стани автомата S1, а саме у вигляді конкатенації

А(Оg) = К(i)К(Оgi), (3),
де К(i) - R1 - розрядний код ОЛЛ i; К(Оgi) - R2i - розрядний код вершини bg i, R2i = log2 Fi, - знак конкатенації. Оскільки адресний простір для мікрокоманд загальний, то для адресації будь-якої вершини необхідно

R2=max(R21,…,R2G) (4)
адресних розрядів.

Рис 3 - структурна схема КМПК з розділенням кодів U3 (а) та елементарними ОЛЛ U41(б).

КМПК, засноване на принципі (3), назване КМПК з розділенням кодів і визначено символом U3. Для адресації команд U3 досить

R3 = R1+ R2 (5)
адресних розрядів. Для зберігання коду К(i), який не міняється в процесі формування мікрокоманд ОЛЛ i, можна використати регістр РОЛЛ, а друга частина адреси може зберігатися на лічильнику адреси компонент СТАК (рис. 3а)

Для зменшення числа виходів КС в роботі пропонується використати елементарні ОЛЛ, що мають тільки один вхід. Це породжує КМПК U41, в якому вхід ОЛЛ завжди має нульову адресу і сигнали замінюються сигналами обнулення.

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

1. Розробка методів синтезу КМПК з розділенням кодів і елементарних ОЛЛ по ГСА.

2. Розробка структур і методів синтезу КМПК U3 - U41, заснованих на застосуванні методів оптимізації автомата Мура, а саме оптимальне кодування станів, перетворення кодів станів, введення додаткових станів.

Як елементний базис використовуються програмуємі ВІС типу ПЛМ, ПЛІС, ПЗУ.

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

У роботі запропонований алгоритм синтезу КМПК U3, заснований на уявленні (3). При цьому для формування систем та пропонується побудувати таблицю переходів автомата S1 і стовпцями: g; K(g); I(t,j) - j – тий вхід ОЛЛ tС, в який відбувається h-й перехід автомата S1; А(t,j) - адреса цього входу; h - набір функцій збудження РОЛЛ, що приймають одиничне значення для запису в РОЛЛ коду К(t); h - набір функцій збудження СТАК, що приймають одиничне значення для запису в СТАК адреси А(t,j); h=1,…,H - номер переходу. При цьому:

r = h=1H Crh h Xh (r = 1,…,R1)

(6)

S = h=1H Csh h Xh (r = 1,…,R2)

де h – кон’юнкція змінних r, відповідна коду K(g) ОЛЦ g

з h-й рядка таблиці, Crh и Csh - булеві змінні.

Далі розглядаються методи оптимізації КМПК U3, засновані на формуванні розбиття ¶с безліччю ОЛЛ С на класи псевдоеквівалентних ОЛЛ, під якими розуміються ОЛЛ, виходи яких пов'язані з входом однієї і тієї ж вершини ГСА Г: ¶С = В1,…,В

1.Оптимальне кодування ОЛЛ. При цьому ОЛЛ gВi кодуються так, щоб їх входи входили в один узагальнений інтервал R1-мірного булева простору. Такий підхід не впливає на структуру КМПК U3, але дозволить зменшити число рядків в таблиці переходів до

Н1 = kН, (7)
де k - коефіцієнт стиснення таблиці. Оптимальне кодування можливе, тільки якщо є достатня кількість неістотних наборів внутрішніх змінних. Цей метод породжує КМПК U31.

2. Перетворення кодів ОЛЛ. У цьому випадку кожному класу Вi¶С ставиться у відповідність код К(Вi) розрядності

R4 = log2 I (8)
і задається відповідність 0, де 0 - безліч додаткових змінних, що кодують класи Вi¶С . Цей метод породжує КМПК U32, в якій при виконанні умови

R1 , (9)
де = , число входів КС U2 і U32 співпадає, а число входів перетворювача - менше.

3.Введення додаткових ОЛЛ. У цьому випадку кожний клас Вi¶С однозначно ідентифікується додатковою ОЛЛ. Доцільність перетворення для кожного класу визначається виразом

i = Hi(Qi - 1) - Qi 0, (10)

де Hi - число переходів з виходу ОЛЛ gВi, QiВi Подальше зменшення числа рядків таблиці переходів можливе за рахунок поєднання методів оптимального кодування і введення додаткових ОЛЛ, що породжує КМПК U33.

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

У третьому розділі розглянуті структури і методи синтезу КМПК з елементарними ОЛЛ, отримані оцінки складності реалізації КМПК на заказних матрицях.

У роботі пропонується загальна методика синтезу подібних пристроїв, заснована на процесі елементаризації безліч ОЛЛ EС = 1,…,G0, внаслідок застосування якого формується безліч елементарних ОЛЛ, де G0 . G. Використання елементарних ОЛЛ дозволяє:

1.

2.

3.

У роботі пропонуються методи оптимізації апаратурних витрат, засновані на оптимальному кодуванні елементарних ОЛЛ (U42), перетворенні кодів елементарних ОЛЛ (U43) і введенні додаткових елементарних ОЛЛ (U44).

Економія виходів схеми КС може бути використана таким чином - схема КС може використовуватися для реалізації перетворення кодів ОЛЛ в коди класів ОЛЛ, що породжує структуру U45 (рис. 4).

Рис 4. - Структурна схема КМКП без додаткового перетворювача кодів.

У КМПК U45 схема КС одночасно з кодом ОЛЛ формує код K(Bi), що включає ОЛЛ gВi, який заноситься в регістр коду РКК. Код K(Bi) залишається незмінним до формування сигналу у0 = 0. Застосування цього методу найбільш доцільно, якщо виконується умова

+ t, (11)

де t - число виходів ПЛМ або ПЛІС схеми КС.

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

F(уп) Р (12)

Для більшості функцій уп , где F(уп) - число термів в ДНФ функції уп. Очевидно, будь-яка диз’юнкція Am Zi As Zj, де Zi,Zj – кон’юнкції, відповідні кодам i-й і j-й рядків ПСТ, виражається одним терміном, якщо:

1.

2.

У роботі пропонується метод оптимального кодування станів і рядків, що дозволяє виконати умову (12). Застосування цього методу породжує структури, аналогічні для структури U45 (рис. 5).

Рис 5 – Структурна схема КМКП U45 з кодуванням строк підтаблиць таблиці переходів

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

Далі розглянуті структури КМПК U41 - U45 на заказних матрицях і отримані формули для оцінки апаратурних витрат.

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

При дослідженні використано ймовірностний метод, запропонований в роботах Г.І. Новікова і який дозволяє дослідити не окремі ГСА, а їх класи, що виділяються за двома параметрами:

1)

2)

Параметри р1 і р2 можна розглядати як імовірності появи операторних і умовних вершин ГСА відповідно. При цьому р1 + р2 1, оскільки в ГСА є початкова і кінцева вершини.

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

1.

Н = 10,6 + 2,16р1К/р3. (13)

2.

М = р1К. (14)

3.

L = (1 - р1)К/р4. (15)

4.

Т = р1К/р3. (16)

Тут р3 - відношення числа операторних вершин до числа наборів мікрооперацій, р4 - відношення числа умовних вершин до числа логічних умов, р3, р4 1; 1,2. Застосування КМПК доцільне при р1 0,75, що і використано при проведенні досліджень.

Як відомо, відносні витрати числа ВІС і площі заказних ВІС для різних автоматних структур співпадають з точністю до 0,89 - 0,92. Це дозволяє спростити формули для апаратурних витрат, оскільки при виборі структури КМПК важливі насамперед відносні витрати обладнання.

У роботі отримані аналітичні оцінки площі ВІС для всіх запропонованих структур КМПК і дісталися відносні оцінки для КМПК одного класу. Залежність, отримана при порівнянні структур Ui і Uj, позначена як (Ui , Uj).. При цьому отримані наступні результати.

З аналізу залежності (U3, U1) видно, що структура U3 завжди більш ефективна, ніж U1. Виграш меншає по мірі зростання числа вершин ГСА і зростання числа ОЛЛ, тобто по мірі зростання розгалуженості ГСА.

Аналіз залежності (U32, U2) показує, що виграш для структури U31 практично не залежить від числа операторних вершин.. Виграш меншає по мірі зменшення стиснення таблиці переходів за рахунок оптимального кодування ОЛЛ, а також по мірі зростання числа ОЛЛ.

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

Аналіз залежності (U33, U3) показує, що введення додаткових ОЛЛ дозволяє зменшити апаратурні витрати. Виграш збільшується по мірі зменшення числа вершин ГСА і кількості ОЛЛ.

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

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

Таблиця 1

Функція | Максимум | Мінімум | Функція | Максимум | Мінімум

(U3,U1) | 12% | 0,5% | (U41,U1) | 24% | 0,2%

(U31,U3) | 65% | 21% | (U42,U1) | 85% | 41%

(U32,U2) | 13% | 0,4% | (U43,U2) | 22% | 1%

(U33,U3) | 17% | 0,7% | (U44,U3) | 28% | 1,3%

(U45,U2) | 40% | 3%

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

ВИСНОВКИ

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

1.

2.

3.

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

1. Баркалов А.А., Самин Нахлави, Черкашин В.А. Принципы оптимизации логических схем автоматов на счетчиках. / сб. наук. праць Донецького державного технiчного унiверсiтету. Серiя “Обчислювальна технiка та автоматизацiя”. Вип. 12 – Донецьк.- 1999. – С.190-196.

2. Саломатин В.А., Белецкий О.В., Черкашин В.А. Оптимизация логической схемы PR-автомата на счетчике./ сб. наук. праць Донецького державного технiчного унiверсiтету. Серiя “Iнформатiка, кiбернетика та обчислювальна технiка”. Вип. 6 – Донецьк.- 1999. – С.192-197.

3. Ковалев С.А., Черкашин В.А., Науменко А.А. Синтез устройства управления с элементарными операторными линейными цепями. / сб. наук. праць Донецького державного технiчного унiверсiтету. Серiя “Проблеми моделювання та автоматизацii проектування динамiчних систем”. Вип. 10 – Донецьк.- 1999. – С.289-295.

4. Баркалов А.А., Белецкий О.В., Черкашин В.А. Синтез логической схемы PR-автомата на счетчике // Управляющие системы и машины. –1999.- №6 – С.11-15.

5. Баркалов А.А., Белецкий О.В., Черкашин В.А. Синтез PR-автомата с преобразователем кодов состояний. / Логическое проектирование. Сборник научных трудов. Выпуск 4. – Минск: Институт технической кибернетики НАН Беларуси.- 1999. – С. 165-172.

6. Баркалов А.А., Черкашин В.А., Зеленева И.Я. Принципы оптимизации логических схем устройств управления на счетчиках. / В.кн.: Автоматизация проектирования дискретных систем // Материалы III Международной конференции (10-12 ноября 1999г., г.Минск, том 2). – Минск: Институт технической кибернетики НАН Беларуси.- 1999. – С. 101-108.

Особистий внесок здобувача в публікаціях:[1]-автором розроблений загальний метод синтезу мікропрограмного автомата на лічильнику, ПЛМ і ПЗУ з використанням ОЛЛ; [2,5]- розроблений метод представлення адреси мікрокоманди у вигляді конкатенації кодів ОЛЛ і компоненти; [3]- поєднання методів розділення кодів і використання елементарних ОЛЛ для оптимізації апаратурних витрат в КМПК; [6]- загальний підхід до синтезу пристроїв керування з використанням розділення кодів мікрокоманди на коди ОЛЛ і її компоненти; [4]- розроблений метод синтезу з розділенням кодів і перетворенням коду мікрокоманди в набір мікрооперацій

Анотація

Черкашин В. А. Методи синтезу композиційних мікропрограмних пристроїв керування. – Рукопис.

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

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

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

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

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

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

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

Ключевые слова : композиционные микропрограммные устройства управления, микропрограммные автоматы, псевдоэквивалентные состояния, микрокоманды, программируемые БИС.

Cherkashin V.A. The methods of synthesis of compositional microprogram control units – Manuscript

Thesis for a candidate’s degree(technical sciences ) by specialty 05. 13. 13 – computers, systems and networks, Donetsk national technical university Donetsk, 2001

On the basis of theoretical and experimental researchers the new formal methods of compositional microprogram control units are proposed. It is shown that optimization of hardware can be achieved by presentation of the microinstruction address as concatenation of the code of operational linear chain and its component. On the base of such sharing the methods of synthesis of compositional microprogram control units with traditional and elementary operational linear chains have been proposed. The further optimization is reached because of usage of pseudoequivalent states of Moore automaton that forms the addresses of microinstructions. The proposed methods permit to decrease the ammount of programmable VLSI in the automaton circuit till 80% in comparison with known methods of synthesis. The analytical estimations of the hardware amount as the function of parameters of VLSI and flow-chart have been made up. These methods are implemented as some programs and it permits to expand the class of synthesisable microprogram control units. The conducted researchers permit to find the area of the effective application of the proposed structures of the compositional microprogram control units.

Key words :compositional microprogram control units, microprogram automata, pseudoequivalent states, microinstructions, programmable VLSI.