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

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

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

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

Міжнародній конференції "Mixed Design - 9" (м. Лодзь, Польша, червень 1998 р.),

III Міжнародній конференції "Автоматизація проектування дискретних систем “ (м. Мінськ 10-12 листопада 1999 р. )

Семінарах Інституту прикладної математики і механіки НАН України (м. Київ, квітень 1999 р.) і кафедри ЕОМ ДонДТУ (м. Донецьк, березень 1999р.).

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

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

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

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

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

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

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

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

У КМПК U0 функціонує таким чином. По сигналу "Пуск" в СЧАМК і РП заносяться нульові адреса і код стану відповідно. Нехай в момент часу t автомат S1 перейшов в стан а_mА₁, где А₁ = а₁,…а_М1 - безліч станів автомата S1, і заніс в СЧАМК адресу j - го входу ОЛЛ _GС.. Якщо цей вхід не є і виходом, то автомат S2 формує набір мікрооперацій з безлічі у_1,…,у_N і сигнал у₀. По сигналу у₀ до СЧАМК додається одиниця, адресуючи чергову мікрокоманду. При досягненні виходу ОЛЛ _g сигнал у₀ не формується і чергова адреса переходу заноситься в СЧАМК функціями ₁,…,_R, де R = log₂ M, де М - число мікрокоманд в КП.

Одночасно автомат S1 формує функцію ₁,…,_R0,де R₀ = log₂ M₁, для переходу в черговий стан а_S = (а_m,Х), де - функція переходу, Х = х₁,…,х_L - безліч вхідних сигналів (логічних умов).Функціонування продовжується до досягнення кінця програми

При виконанні умови R = R₀ доцільно сумістити функції СЧАМК і РП в СЧАМК, що приводить до економії числа виходів в КС і породжує структуру U1. Для оптимізації числа входів КС при виконанні умови R log₂, G = R₁ в структуру U1 можна ввести перетворювач адреси ОЛЛ в її код (ПА), що породжує структуру U2.

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

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

А(О_g) = К(_i)К(О_gi),

де К(_i) - R₁ - розрядний код ОЛЛ _i; К(О_gi) - R₂ⁱ - розрядний код вершини b_{g i}, R₂ⁱ . Оскільки адресний простір для мікрокоманд загальний, то для адресації будь-якої вершини необхідно max(R₂¹,…,R₂^G) адресних розрядів. КМПК, засноване на принципі, назване КМПК з розділенням кодів і визначено символом U3. Для адресації команд U3 досить адресних розрядів

R₃ = R₁+ R₂

Для зберігання коду К(_i), який не міняється в процесі формування мікрокоманд ОЛЛ _i, можна використати регістр РОЛЛ, а друга частина адреси може зберігатися на лічильнику адреси компонент СТАК.

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

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

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

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

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

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

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

_r = _h=1^H C_{rh h} X_h(r = 1,…,R₁)

_S = _h=1^H C_{sh h} X_h(r = 1,…,R₂)

де _{h -} кон'юнкція змінних _r, відповідна коду K(_g) ОЛЦ _g з h-й рядка таблиці, C_rh и C_sh - булеві змінні.

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

1.Оптимальне кодування ОЛЛ. При цьому ОЛЛ _gВ_i кодуються так, щоб їх входи входили в один узагальнений інтервал R₁-мірного булева простору. Такий підхід не впливає на структуру КМПК U₃, але дозволить зменшити число рядків в таблиці переходів до Н₁ = kН, k - коефіцієнт стиснення таблиці. Оптимальне кодування можливе, тільки якщо є достатня кількість неістотнихнаборів внутрішніх змінних. Цей метод породжує КМПК U₃¹.

2. Перетворення кодів ОЛЛ. У цьому випадку кожному класу В_i¶_С ставиться у відповідність код К(В_i) розрядності R₄ = log₂ I і задається відповідність ₀, де _{0 -} безліч додаткових змінних, що кодують класи В_i¶_{С .} Цей метод породжує КМПК U₃², в якій при виконанні умови R₁ , де = , число входів КС U₂ і U₃² співпадає.

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

_i = H_i(Q_i - 1) - Q_i 0

де H_i - число переходів з виходу ОЛЛ _gВ_i, Q_iВ_i Подальше зменшення числа рядків таблиці переходів можливе за рахунок поєднання методів оптимального кодування і введення додаткових ОЛЛ, що породжує КМПК U₃³.

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

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

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

При виконанні умови R₀ + R₅ R₁ + R₂ економити необхідну місткість керуючої пам'яті в порівнянні з КМПК з розділенням кодів. Тут

R₀ = log₂ G₀, R₅ = log₂ F_{g max}, F_{g max} = max (F₁,…, F_G0).

При виконанні умови R₀ + R₅ = число ВІС в КП КМПК U₂ і U₄¹ є однаковим і мінімально можливим.

При виконанні умови R₀ = R₁ число входів в схемі КС для КМПК U₃ і U₄¹ співпадає, а число виходів меншає з R₁ + R₂ до R₀.

У роботі пропонуються методи оптимізації апаратурних витрат, засновані на оптимальному кодуванні елементарних ОЛЛ (U₄²), перетворенні кодів елементарних ОЛЛ (U₄³) і введенні додаткових елементарних ОЛЛ (U₄⁴).

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

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

+ t,

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

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

F(у_п) Р

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

Zi = Zj і коди станів a_m і a_s входять в один інтервал R- мірного булева простору.

A_m = A_s і коди рядків F_i і F_j входять в один узагальнений інтервал Q - мірного булева простору.

У роботі пропонується метод оптимального кодування станів і рядків, що дозволяє виконати умову. Застосування цього методу породжує структури, аналогічні для структури U₄⁵.

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

Далі розглянуті структури КМПК U₄¹ - U₄⁵ на заказних матрицях і отримані формули для оцінки апаратурних витрат. У четвертому розділі приводяться результати досліджень розроблених методів і визначаються області їх застосування. При дослідженні використано ймовірностний метод, запропонований в роботах Г.І. Новікова і який дозволяє дослідити не окремі ГСА, а їх класи, що виділяються за двома параметрами: частка операторних вершин ГСА р₁; частка умовних вершин ГСА р₂.

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

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

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

Н = 10,6 + 2,16р₁К/р₃.

Число станів автомата Мура

М = р₁К

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

L = (1 - р₁)К/р₄.

Число наборів мікрооперацій в ГСА

Т = р₁К/р₃.

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

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

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

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

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

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

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

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

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

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

Висновки

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

Виконаний аналіз синтезу і оптимізації характеристик композиційних мікропрограмних пристроїв керування на ВІС.

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

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

Список опублікованих рабіт по темі дисертації

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.

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