автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка структур и алгоритмов синтеза автоматов с ''программируемой" логикой на программируемых БИС

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

АЛЬ-ДАХЛЄ МУХАММЄД ЗАЙД АБДЄЛЬ (Іорданія)

УДК 681.324:681.327

РОЗРОБКА СТРУКТУР І АЛГОРИТМІВ СИНТЕЗУ АВТОМАТІВ З “ПРОГРАМУЄМОЮ* ЛОГІКОЮ НА ПРОГРАМУЄМ!« ВІС

Спеціальність 05. 13. 13 - “ Обчислювальні машини, системи та мережі ”

АВТОРЕФЕРАТ

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

Донецьк - 1998р.

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

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

Науковий керівник - кандидат техн. наук, доцент Павлиш Володимир Миколайович, завідуючий кафедрою “Обчислювальная математика і програмування’ Донецького державного технічного університету.

Офіційні опоненти: доктор техн. наук, професор Скобцов Юрій Олександрович, завідуючий відділом теорії керуючих систем інституту прикладної математики і механіки НАН України (м. Донецьк); кандидат техн. наук, доцент Стародубов Костянтин Євгенійович, системний аналітик СОВ “Імпакт” (м. Донецьк).

Провідна установа - Донецький державний інститут штучного інтелекта Міносвіти України (м. Донецьк).

Захист дисертації відбудеться « 2 % » С>~5________1998р.

годині, на засіданні спеціалізованоі вченоі ради К 11.052.03 у Донецькому державному технічному університеті за адресою :

340000 м. Донецьк, вул. Артема, 58, уч. корп. 1, ауд. 201.

З дисертацією можна ознайомитись у бібліотеці Донецького державного технічного університету за адресою : 340000 м. Донецьк, вул. Артема 58, уч. корп. 2

Автореферат розісланий « ^ ^_______1998р.

Вчений секретар спеціалізованоі вченої ради,

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

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

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

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

В цей час для реалізації керуючих автоматів широко використовуються автомати з "програмусмою" логікою (APL), що втілюють операційно-адресне подання мікрокоманд APL найбільш підходять для реалізації великих систем мікропрограмного забезпечення сучасних цифрових систем. Універсальність APL досягається за рахунок збільшення часу виконання алгоритму у порівнянні з автоматами з “жорсткою’' логікою, що зв'язане з багатотактним виконанням переходів, що залежать від декількох логічних умов. Це приводит до збільшення числа мікрокоманд у порівнянні з числом переходів автомату з “жорсткою” логікою. При цьому актуальною є проблема зменшення числа мікросхем в керуючій пам'яті APL, що дозволяє зменшити загальну вартість цифрової системи. Один з шляхів зменшення ємності керуючої пам'яті -введення додаткових блоків адресації, що придають автомату напівзамовлюваний характер і що дозволяє зменшити число і розрядність мікрокоманд в мікропрограмах, що реалізуються APL.

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

Ціль роботи. Вдосконалення характеристик синтезованих автоматів з “програмуємою” логікою (АРЬ) шляхом скорочення числа і разрядності мікрокоманд в мікропрограммах алгоритму, скорочення числа ВІС в схемі автомату і підвищення швидкодії.

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

Основні завдання досліджень. В процесі досліджень необхідно :

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

2. Розробка структури і алгоритми синтезу АРЬ з різноманітними режимами адресації' мікрокоманд при введенні додаткової схеми адресації;

3. Розробка структури і алгоритми синтезу АРЬ зі схемою перетворювача адреси мікрокоманд для різноманітних режимів адресації;

4. Розробка структури і алгоритми синтезу АРЬ з сполученняем функцій полів мікрокоманд, для різноманітних режимів адресації;

5. Розробка структури і алгоритми синтезу автоматів при багатотактній вибірці мікрокоманд;

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

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

Наукові положення і результати, що виносяться на захист, і особистий внесок автора в їх розробку.

Основні положення.

1. Введення додаткових функціональних блоків - перетворювача адреси мікрокоманд, додаткова схема адресації - в структуру автомату з “програмуємою” логікою дозволяє реалізувати багатоспрямовані переходи за один такт і зменшити розрядність мікрокоманд, що в цілому дозволяє зменшити число мікросхем в керуючій пам'яті на 23% - 60%.

з

2. Багатотактна вибірка мікрокоманд дозволяє зменшити на 30% число мікросхем в керуючій пам'яті, за рахунок більш ефективного використання

виходів ПЗУ,

3. Суміщення функцій полів мікрокоманд дозволяє зменшити на 60% розрядность мікрокоманд і, як слідство, число мікросхем в керуючій пам'яті.

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

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

2. Розроблені структура і алгоритм синтезу автоматів з перетворювачем адреси мікрокоманд.

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

4. Розроблені структура і алгоритм синтезу автоматів з багатотактною вибіркою

мікрокоманд.

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

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

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

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

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

Декларація особистого внеску. Автором самостійно розроблені всі структури і алгоритми синтезу автоматів, розглянуті в дисертаційній роботі.

Реалізація результатів роботи. Одержані в роботі результати реалізовані у вигляді методик синтезу автоматів з удосконаленими характеристиками на програмуємих ВІС і використані в практичних розробках лабораторії прикладних проблем дискретної математики інституту прикладної математики і механіки НАН України в рамках теми “Зворотні завдання теорії автоматів стосовно до ідентифікації і розпізнання дискретних систем” (м. Донецьк), де на їх основі розроблений проект системи ідентифікації дискретних об'єктів, включаючих автомати з зменшеними апаратурними витратами у порівнянні з раніше проектованими системами, а також на кафедрах ЕОМ і ОМіП при читанні лекцій, в курсовому і дипломному проектуванні.

Апробація. Основні результати роботи доповідалися і обговорювалися на міжнародній конференції “Комп'ютерізація проектування, управління і діагностики технічних систем” (м.Луганськ, травень 1996р.), на міжнародній конференції “III школа геомеханики” (Польща, Глівиці - Устрон 23-26 листопад 1997р.), а також на семінарах інституту прикладної математики і механіки НАН України (м.Донецьк, листопад 1997р.), кафедрах ОМіП (м.Донецьк, березень 1997р.), ЕОМ ДонДТУ (м.Донецьк, травень 1997р.).

Публікації. Зміст роботи відбито у 7 публікаціях, а саме : двох статтях у наукових виданнях, в матеріалах міжнародної конференції “III школа геомеханики” (Польща, Гливици-Устрон 23-26 листопад 1997р.), тезах доповідях міжнародної конференції “Комп’ютерізація проектування, управління і діагностики технічних систем” (м. Луганськ, травень 1996р.), а також в трьох депонованих рукописах. В публікаціях авторові належать структри і алгоритми синтезу автоматів з “програмуємою” логікою, що дозволяють підвищити їх бистродію і скоротити число мікросхем в керуючій пам'яті.

Структура і обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновку, викладених на 156 сторінках машинописного тексту, містить 87 рисунків, 41 таблицю, список літератури із 92 найменувань, а також 1 додатку. Робота містить список скорочень, прийнятих в роботі,

СТИСЛИЙ ЗМІСТ РОБОТИ

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

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

Алгоритми управління систем цифрової автоматики і обчислювальної техніки можуть бути реалізовані схемним шляхом з використанням автоматів з “жорсткою” і "програмуємою’' логікою ( APL ), Застосування APL дозволяє реалізувати об'ємне мікропрограмне забезпечення і не виключає можливості оперативної зміни мікропрограм.

APL є синхронним кінцевим автоматом Мура і засновується на використанні принципу операційно-адресного подання керуючих слів (мікрокоманд), що зберігаються в мікролрограмній пам'яті ( ММР ). В структурну схему APL входять (рисунок 1):

- схема адресації СА, що реалізує режим примусової ( ПА ), природної ( ЕА ) або комбінованої ( КА ) адресації мікрокоманд на основі аналізу логічних умов X -{x^,...,xL} і змісту RAMI, здійснюючий прийом адреси

мікрокоманди із СА або збільшення на одиницю адреси поточної макрокоманда;

- мікропрограмна пам'ять ММР, що зберігає М .мікрокоманд даного формату, що становлять мікропрограму;

- схему формування керуючих сигналів CCS, що формує на основі аналізу операційної частини мікрокоманд мікрооперації Y = {Уі, ■ • • > Ум } і сигнал зупинки APL Z.

У

г

Рисунок 1- Структурна схема автомату з “програмуємою” логікою

У

г

Рисунок 2 - Структурна схема автомату з додатковою схемою адресації

У

г

Рисунок 3 -Структурна схема автомату з перетворювачем адреси мікрокоманд

Метода синтезу APL із ПА, ЕА і КА достатньо розглянуті в літературі, тому в роботі процес синтезу доводиться тільки до одержання таблиць, що задають основні елемента структури автомату.

Універсальність APL приводить до збільшення часу виконання алгоритм)' порівняно з автоматом із “жорсткою” логікою. Це пов'язане з тим, що :

- при ЕА і КА в мікропрограму вво;тяться спеціальні керуючі мікрокоманди безумовного переходу при порушенні природного порядку прямування мікрокоманд;

- переходи, що залежать в ГСА від L¡ логічних умов, виконуються APL за L¡ тактів.

Крім того, при ПА і КА частина полів мікрокоманди можуть бути пустими, що зменшує ефективність використання ПЗУ.

Аналіз елементного базиса показує, Що програмуємі ВІС з регулярною структурою є ефективним засобом реалізації APL. При цьому для синтезу ММР

найбільш підходять ПЗУ, для синтезу С А - му.тьтіплексори, для синтезу CCS і будь-яких комбінаційних схем, орієнтованих на реалізацію ДНФ, - ПЛМ і ПЛІС. Широкий спектр мікросхем цього класу дозволяє підбирати ВІС. найбільш придатні для конкретної ГСА.

Підвищення бистродії APL пов'язане з введенням додаткових структурних елементів. В роботі пропонуються два основних алгоритми :

1. Введення додаткової схеми адресації. При цьому в склад APL вводиться схема CAI, шо дозволить за один такт сформувати адреси переходу, що залежать від L ¡ > 2 логічних умов X , є X 1 (рисунок 2). Безумовні переходи і переходи, що залежать від одні є з умов X , є X 2, реалізує схема СА. Для вибору джерела адреси вводиться мультиплексор МІ, шо управляє спеціальним полем признаку FA.

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

Схема СА1 найбільш ефективно реалізується на ПЛМ або ПЛІС, схема ACM - на

ПЗУ.

Для зменшення числа ПЗУ в схемі ММР в роботі пропонуються такі алгоритми :

1. Сполучення функцій полів мікрокоманд. В цьому випадку мікрокоманди при ПА і КА містять одне поле FMOLC, що поєднує функції полів набору мікрооперацій FMO і логічних умов FLC. Для декодування поля FMOLC використовується схема FCC.

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

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

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

Багатотактна вибірка МК вимагає введення в схему APL додаткового лічильника для визначення номеру такту і регістру, в який поступово заносяться різні частини мікрокоманди. Як показали дослідження, використання алгоритму доцільно при збільшенні ємності ПЗУ в S = 2к раз, де S - число частин, на які розподілена мікрокоманда. Апаратурні витрати оцінюються формулою

де <7 - число виходів і ємність ПЗУ відповідно, г - розрядність мікрокоманди.

Максимальний виграш т| т ах у порівнянні з АРЬ з однотакгною вибіркою

де По - число корпусів ПЗУ в традиційній схемі APL.

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

TW = n0/n = S,

автомату після вибірки пояя FMO, Як показали дослідження, втрати бистродіі визначаються коефіцієнтом уповільнення

а = (0 + X)/(S + %)),

де х - відношення часу циклу APL до часу циклу ОА.

Далі розглянуто алгоритм синтезу автомату' з сполученням функцій полів FMO і FLC. Ідея методу полягає в тому, щоб розглядати пару < набор мікрооперацій, логічна умова >, як єдине ціле, що дозволяє зменшити розрядність МК і як слідство, число мікросхем в керуючій пам'яті. В загальному випадку зменшення числа корпусів ПЗУ в ММР визначається висловом

Д = int((r - r0)/í)int(M /q),

де г, Го - розрядність мікрокоманд в APL без і з сполученням функцій полів. Зменшення складності ММР пов'язане зі зростанням складності схеми FCC, при цьому застосування структури і алгоритму доцільно, якщо число Мо попарно різноманітних пар виду (Y ,, х ,) таке, що виконується умова

in t io g 2M ) int lo g 2M 0 .

В роботі показано, що перетворювач коду FMOLC в коди Y і FLC доцільно реалізувати на ПЛМ або ПЛІС, і запропоновано алгоритм адресації, скорочуючий число термів в ДНФ функцій у л є Y

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

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

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

Для дослідження запрононованих алгоритмів використано імовірносний підхід (Г. І. Новіков), при якому ГСА характеризується двома параметрами : - імовірність

появи операторної вершини, %2 - імовірність появи умовної вершини. Такий підхід дозволяє змалювати аппаратурні випрати в різноманітних схемах автоматів як функції від xU %2, t, q, і К, де К- число вершин ГСА.

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

Перетворювач адреси ACM вводиться для ліквідації критичних ситуацій по адресації. При цьому в схемі з'являється додаткове джерело адреси, що викликає необхідність в збільшенні розрядності поля FA до двох біт. Основною відзнакою APL із ACM є механізм виконання керуючих мікрокоманд (УМК) умовного переходу. Якщо в традиційній APL після умовної вершини прямувала УМК, то в даному випадку це ідентифікується полем FA. Якщо переглянуте ЛУ дорівнює одиниці, то схема СА виробляє сигнал збільшення вмісту СТАМІ на одиницю, в протилежному випадку джерелом адреси є ACM.

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

Далі розглянуто алгоритм введення додаткової схеми адресації СА1, що дозволить максимально підвищити бистродію APL. В роботі пропонується алгоритм синтезу APL, заснований на побудові ПСТ автомату Мура для вихідної ГСА. Ця таблица розбивається на дві частини ПІ і П2, підтаблиця ПІ містить мікрокоманди, переходи із яких залежать від декількох ЛУ. В роботі показано, що для реалізації

доцільно використати ПЛІС, число слів в яких узгоджується з числом слів в ПЗУ пам'яті APL. Проведені дослідження показали, що виграш досягає 20-30% і збільшується по мірі зростання числа ЛУ, що визначають переходи із П2, і по мірі зменшення параметрів ПЗУ щодо параметрів ПЛІС.

Об'єднання ACM і СА1 приводить до схеми APL із максимально можливою бистродією. При цьому можливо два підходи - розділення схем ACM і СА1 (рисунок 4) і сполучення їх функцій схемою МАС (рисунок 5).

В роботі запропоновані алгоритми синтезу A PL по ГСА для обох структур. Перша структура приводить до збільшення розрядності поля FA до трьох біт, проте більше відповідає принципу динамічного макропрограмування. Структура APL із МАС дозволяє максимально зменшити ємність ММР, проте це досягається за рахунок спеціалізації автомату.

Проведений аналіз APL із МАС дозволяє зробити висновки, що в діапазоні X і є [0,47 ; 0.69] при зміні числа входів ПЛІС Sn в діапазоні [ 16, 64 ] і числа слів q„ в діапазоні [ 160; 480 J :

- виграш г| не залежить від параметра q„ і визначається параметрами S„ і хі, тут

де Vi, V2, V3 - число ВІС ПЗУ в ММР автомату з традиційного структурою і МАС, а також число ПЛІС в схемі МАС відповідно,

- виграш збільшується по мірі зростання параметрів S„ і хі, не пов'язане з тим, що по мірі зростання числа олераторних вершин ГСА і числа входів ПЛІС зменьшується число мікросхем в МАС;

- виграш зменьшується по мірі зростання параметрів ПЗУ, бо число ВІС в ММР зменьшується при незмінних параметрах МАС,

- максимальний виграш т]=2.3 при S„=32, 'х 1 = 0.69. q = 128 і t=2.

Вираз (1) дозволяє оцінити апаратурні виграти для будь-якого автомату із МАС, або ACM, або СА1, проте V) - V3 повинні відповідати конкретній структурі автомату. При цьому для оцінки числа мікрокоманд в мікропрограмі використовуються оцінки, одержані в роботах Л. В. Крилової, а оцінка числа ВІС в МАС або СА1 виробляється на основі результатів В. А. Склярова.

( І )

Рисунок 4 - Автомат з роздподіленням схем додаткової адресації і перетворювачем адреси мікрокоманд

Рисунок 5 - Автомат зі сполученою схемою додаткової адресації і перетворювачем адреси мікрокоманд

Для оцінки корректності одержаних результатів був проведений синтез схем APL по конкретним ГСА. При цьому розходження в г| склало до 10%, що цілком прийнятно для інженерній розрахунків.

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

При дослідженні характеристик автоматів, використовувався імовірностний метод завдання характеристик ГСА запропонований в роботах Л. В. Криловой і Г. І. Новікова.

При дослідженні характеристик автоматів використано заснований на теорії імовірностей метод завдання характеристик ГСА, запрононований в роботах JI. В. Крилової і Г. І. Новікова.

В роботі розглянуто алгоритм синтезу APL зі сполученням функцій полів FMO і

FLC полем FMOLC, що приводить до введення в автомат схеми перетворювача поля FMOLC. Запропоновано алгоритм синтезу, що дозволить формалізувати процес проектування APL по ГСА. Застосування структури і алгоритму дозволяє зменшити довжину мікрокоманди до Ro+R, де R 0 = int (log2 Т0) . Т0 - число різноманітних пар < Y,, х і > .

В роботі одержані аналітичні оцінки параметрів схем структури (рисунок 6), що дозволило висловити виграш т|, який задається виразом (1).

Тепер параметр \% визначається числом ВІС в схемі FCC перетворювача поля FMOLC. Схема FCC є джерелом коду логічних умов ,що перевіряються, адреса переходу FAF як і раніше формується ММР.

Як показали дослідження, виграш г| збільшується по мірі зростання числа виходів і ємності ВІС схеми FCC, що робить доцільніш застосування в якості елементного базиса ПЛІС. Виграш г| збільшується по мірі зростання частки поля FAF порівняно з часткою полів FMO і FLC.

Далі розглянуто алгоритм синтезу автомату з додатковою схемою адресації, спеціалізуючий структуру APL. Пропонується алгоритм синтезу APL по ГСА, що дозволить автоматизувати процес проектування.

В цьому випадку в формат мікрокоманд вводиться додаткове поле признаку FA, що дозволить управляти мультіплексором МІ для вибірки джерела адреси (рисунок 7).

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

де г0 - розрядність МК автомату.

Проведені дослідження показали, що виграш ті досягає 50-55%, при цьому :

- виграш т) практично не залежить від числа слів ПЛІС;

- параметрами ,що визначать т), є число входів ПЛІС і частка Хз логічних умов, що реалізуються схемою СА1

Iх 1 І

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

В роботі пропонується алгоритм синтезу APL із МАС і провадяться дослідження ефективності цього алгоритму.

ВИСНОВКИ

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

Рисунок б - Автомат зі сполученням функцій полів мікрокоманд

Рисунок 7 - Автомат з дотатковою схемою адресації мікрокоманд з комбінованою адресацією

логікою і алгоритмів їх синтезу в базисі ПЗУ, ПЛМ і ПЛІС. В процесі досліджень вирішені такі завдання :

1. Виконано аналіз методів синтезу і удосконалення характеристик автоматів з “програмуємою” логікою.

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

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

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

5. Виконані дослідження запропонованих алгоритмів синтезу і визначена область ефективного застосування розроблених структур автоматів з “програмуємою” логікою.

ОСНОВНІ ПОЛОЖЕННЯ І РЕЗУЛЬТАТИ РОБОТИ МІСТЯТЬСЯ В НАСТУПНИХ ПУБЛІКАЦІЯХ:

1. В. Н. Павльпп, М. 3. Аль-Дахле Минимизация числа микрокоманд в автомате с комбинированной адресацией / “Информатика, кибернетика и вычислительная техника”. Сборник трудов Донецкого государственного технического университета ( 1997г. ). выпуск 1. - Донецк - ДонГТУ. 1997г. - с. 151-158.

2. В. Н. Павлыш, М. 3. Аль-Дахле, О. К. Мороз Автоматизация управления процессом гидродинамической обработки угольного пласта / Материалы конференции. “III Школа геомеханики”. (Польша, Гливице - Устрон 23-26 ноябьря 1997г.). Устрон 1997г. - с. 133-136.

3. В. Н. Павлыш, М. 3. Аль-Дахле Оптимизация характеристик автомата с принудительной адресацией микрокоманд для систем" автоматизированного контроля / Журнал '‘Известия Донецкого Горного Института”. ДонГТУ. Донецк, 1997г. - № 2 (6) - с. 108-109.

4. В. Н. Павлыш, М. 3. Аль-Дахле Автоматизация проектирования автоматов с программируемой логикой /' “Автоматизация проектирования и производства изделий в машиностроении”. Тезисы Международной научно-практической конференции (г. Луганск, 14-17 мая 1996г.). часть II. - Луганск : ВУГУ. 1996. -с. 196.

5. В.Н. Павлыш, М.З. Аль-Дахле Оптимизация характеристик автомата с принудительной адресацией микрокоманд / ДонГТУ. -Донецк, 1996 -11с-Билиогр.: с. 11 - Деп. в Гос. Науч-техн. библ. Украины Группа деп. 29.07.1996, № 2134-Ук 96 от 4.11.96.

6. В.Н. Павлыш. М.З. Аль-Дахле Минимизация числа микрокоманд в автомате с комбинированной адресацией / ДонГТУ. -Донецк, 1996 - 12 с. - Билиогр.: с. 12 - Деп. в Гос. Науч-техн. библ. Украины Группа деп. 29.07.1996, № 2106-Ук 96 от 24.10.96.

7. В.Н Павлыш. М.З. Аль-Дахле Повышение быстродействия автомата с естественной адресацией микрокоманд / ДонГТУ. -Донецк, 1996 - 10 с. -Билиогр.: с 10 - Деп. в Гос. Науч-техн. биол. Украины Группа деп 29.07.1996, №2131-У к 96 от 4.11.96.

ОСОБИСТИЙ ВНЕСОК В ПУБЛІКАЦІЯХ:

ПІ- Ідея суміщення функцій полів МК як способа скорочення числа мікрокомаїп і підвищення ефективності використання мікропрограмної

пам'яті: розробка структури і алгоритму синтезу автомату з суміщенням функцій полів МК; кількісні оцінки доцільності вступу суміщення функцій полів МК.

[2] - Способи поліпшення параметрів керуючих автоматів, що застосовуються в приладах управління процесом гідродинамічної обробки вугільних пластів; опис структур і алгоритмів синтезу автоматів, що дозволять підвищити швидкодію автоматів і скоротити аппаратурні виграти - вступ додаткової

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

[3] -Аналіз двох основних шляхів реалізації приладів автоматичного контролю і управління на основі кінцевого автомату; кількісна оцінка витрат мікросхем при реалізації мікропрограмної пам'яті на ПЗУ; ідея і суттевість методу послідовно-паралельного виконання мікрокоманд для зменшення числа ПЗУ; кількісна оцінка ефективності методу.

[4] -Порушення задачі синтезу автоматів з характеристиками ,що

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

[5] - Розробка методу багатотактной вибірки мікрокоманд як способу зменшення

апаратурних витрат при синтезі автомату з “програмуємою” логікою; кількісна оцінка ефективності методу; розрахунок граничного відносного зменшенні числа мікросхем, структури та алгоритми синтезу автоматів з “програмуємою” логікою.

[6] - Метод вступу додаткової схеми адресації як спосіб скорочення часу

виконання алгоритму; структура і алгоритм синтезу автомату з додатковою схемою адресації.

[7] - Структура і алгоритм синтезу автомату з перетворювача адреси

мікрокоманд; кількісна оцінка ефективності застосування методу.

АНОТАЦІЯ

Аль-Дахлє Мухаммед Зайд Абдєль. Розробка структур і алгоритмів синтезу автоматів з “програмуємою” логікою на програмуємих ВІС. - Рукопис.

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

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

Ключові слова :

автомат, “програмуєма” логіка, синтез, удосконалення, логічна схема, велика інтегральна схема, мікропрограмна пам’ять.

АННОТАЦИЯ

Аль-Дахле Мухаммед Зайд Абдель. Разработка структур и алгоритмов синтеза автоматов с ‘'программируемой” логикой на программируемых БИС. -Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 “Вычислительные машины, системы и сети”. - Донецкий государственный технический университет, г. Донецк, 1998г.

Диссертационная работа посвящена разработке структур и алгоритмов синтеза автоматов с '‘программируемой” логикой, которые могут уменьшать число микрокоманд и емкость памяти микропрограммы. Способы совершенствования гтруктур и алгоритмов синтеза основаны на применении дополнительной схемы адресации и преобразователя адреса микрокоманды, и на применении совмещения функций полей микрокоманд. В работе предлагаются усовершенствованные структу ры и алгоритмы синтеза автоматов с “программируемой” логикой, а также определена область эффективного применении предложенных разработок.

Ключевые слова:

автомат, “программируемая” логика, синтез, усовершенствование, логическая :хема, большая интегральная схема, микропрограммная память.

ANNOTATION

Al-Dahleh Mohammad Zaid Abdel. The Development of structures and algorithms of synthesis of an automata with “programmable” logic on programmable LSIC. - Manuscript.

The dissertation work on reception a scientific degree of the candidate of technical sciences (PHD). A specialty 05.13.13 “Computers, systems and network”. - Donetsk state technical university, Donetsk, 1998.

This dissertation work is devoted to development of structures and algorithms of synthesis of an automata with “programmable” logic, which can reduce the number of microcommands and capacity of microprogram memory. The ways of perfection of structures and algorithms of synthesis are based on application of the additional circuit of addressing and converter of address’s of microcommands, and on the application of overlapping functions of fields of microcommands. In work the advanced structures and algorithms of synthesis of an automata with “programmable” logic are offered, and also the area of effective application of the offered development is determined.

Key words :

an automaton, “programmable” logic, synthesis, advance, logical circuit, improvement, big integrated circuit, microprogram memory.