ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД“

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

АХМАД ФУАД ХАМАДА БАДЕР

(ЙОРДАНІЯ)

УДК 681.324

МЕТОДИ ОПТИМІЗАЦІЇ ПРИСТРОЇВ КЕРУВАННЯ

З ГЕТЕРОГЕННОЮ СТРУКТУРОЮ

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

АВТОРЕФЕРАТ

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

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

Донецьк 2007

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

Робота виконана в Державному вищому навчальному закладі “Донецький національний технічний університет” Міністерства освіти і науки України

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

Офіційні опоненти: | доктор технічних наук, професор Нестеренко Сергій Анатолійович, директор інституту комп’ютерних систем, Одеський національний політехнічний університет, м. Одеса;

кандидат технічних наук, старший науковий співробітник,

Опанасенко Володимир Миколайович,

старший науковий співробітник інституту кібернетики ім. В.М. Глушкова НАН України, м. Київ.

Захист відбудеться “04” жовтня 2007 р. о 14 годині на засіданні спеціалізованої вченої ради К11.052.03 ДВНЗ “Донецький національний технічний університет” за адресою:

83000, м. Донецьк, вул. Артема, 58, уч. корпус 8, ауд. 704.

З дисертацією можна ознайомитись у бібліотеці ДВНЗ “Донецький національний технічний університет” за адресою:

83000, м. Донецьк, вул. Артема, уч. корпус 2

Автореферат розісланий “30” серпня 2007 р.

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

спеціалізованої вченої

ради К 11.052.03 Г.В. Мокрий

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

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

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

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

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

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

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

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

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

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

3. Розробка структур і методів синтезу автомата Мура з кодуванням наборів мікрооперацій, перетворенням кодів станів і фрагментацією змінних.

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

Об'єкт дослідження – керуючі автомати з “жорсткою” логікою.

Предмет дослідження – методи оптимізації апаратурних витрат у схемах АЖЛ з гетерогенним елементним базисом.

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

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

1. Уперше запропоновано використати метод кодування наборів фрагмента змінних для зменшення апаратурних витрат в автоматах з “жорсткою” логікою.

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

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

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

Практичне значення отриманих результатів:

1. Отримано аналітичні залежності апаратурних витрат у запропонованих структурах керуючих автоматів з “жорсткою” логікою від параметрів вихідної граф-схеми алгоритму.

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

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

4. Експериментально визначена область ефективного застосування розроблених структур керуючих автоматів з кодуванням наборів фрагмента змінних.

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

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

- Четверта Міжнародна науково-технічна конференція “Схід-захід. Проектування й діагностика” (Сочі, 15-19 вересня 2006 р.);

- Сьома Міжнародна науково-практична конференція “Сучасні інформаційні й електронні технології” (Одеса, 22-26 травня 2006 р.);

- Сьома Міжнародна науково-технічна конференція “Искусственный интеллект. Интеллектуальные и многопроцессорные системы – 2006” (Таганрог, 25-30 вересня 2006 р.);

- наукові семінари кафедри електронних обчислювальних машин ДонНТУ (Донецьк).

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

Структура й обсяг роботи. Дисертаційна робота обсягом 164 сторінки складається із вступу, 4 розділів, висновку, містить 52 рисунки і 51 таблицю. Список використаних джерел складається із 115 найменувань і розташований на 9 сторінках.

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

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

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

Залежно від способу реалізації вихідних сигналів (функції виходу) МПА діляться на автомати Мілі, у яких

, (1)

і автомати Мура, у яких

. (2)

Для обох типів автоматів функції переходів виглядають однаково:

. (3)

Комбінаційна схема МПА Мілі реалізує системи (1) і (3), а МПА Мура – (2) і (3), представлені у вигляді диз'юнктивних нормальних форм (ДНФ). Системи (1)-(3) формуються по прямій структурній таблиці (ПСТ) керуючого автомата.

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

1. Кодування наборів мікрооперацій. В цьому випадку кожному набору Yt Y ставиться у відповідність двійковий код розрядності Q=]log2T[, де T – число різних наборів. Для кодування використовуються змінні з безлічі Z = {z1, …, zQ}... Цей метод приводить до PY-автоматів (рис. 1), у яких Y-підсхема реалізує перетворення .

Y-підсхема реалізується на ПЗП й формує функції

Y = Y (Z), (4)

а P-підсхема будується за перетвореною ПСТ і реалізує систему функцій

Z = Z (X, T), (5)

Ф = Ф (X, T).

Рис. 1. Структура автомата Мілі з кодуванням наборів мікрооперацій

Метод синтезу PY-автомата містить наступні етапи:

1) Кодування наборів мікрооперацій.

2) Формування перетвореної ПСТ PY-автомата.

3) Формування таблиці мікрооперацій.

4) Синтез логічної схеми автомата в заданому елементному базисі.

2. Кодування рядків прямої структурної таблиці. У цьому випадку кожному рядку ПСТ ставиться у відповідність код K(Fh) розрядності Q=]log2H[, . Змінні, що здійснюють кодування, утворюють безліч Z. Цей метод приводить до PH-автоматів (рис. 2).

Рис. 2. Структура автомата Мілі з кодуванням рядків ПСТ

У цій структурі H-підсхема реалізується на ПЗП й формує функції

Y = Y (Z), (6)

Ф = Ф (Z),

а P-підсхема реалізує функції

Z = Z (X, T). (7)

Метод синтезу PH-автомата включає наступні етапи:

1) Кодування рядків ПСТ автомата Мілі.

2) Формування перетвореної ПСТ автомата Мілі.

3) Формування таблиці H-підсхеми.

4) Синтез логічної схеми автомата в заданому елементному базисі.

Логічна схема МПА Мура задається системою булевих функцій (2), (3), тобто вихідні сигнали Y залежать тільки від станів автомата. Фактично коди станів K(am) є кодами наборів мікрооперацій, записаних в операторних вершинах, які відзначають станами amA. Це породжує структуру логічної схеми автомата Мура (рис. 3), що містить Р-підсхему для реалізації (2) і Y-підсхему для реалізації (3). Основою для синтезу схеми автомата є ПСТ, формована по вихідної ГСА. У найпростішому випадку автомат Мура представляється дворівневою структурою, у якій система (2) реалізується на ПЛМ, а система (3) – на ПЗП. Таким чином, ця структура має гетерогенну організацію.

При оптимізації автомата Мура одним із центральних понять є поняття “псевдоеквівалентного стану”. Стани am й as є псевдоеквівалентними, якщо виходи відзначених ними вершин ГСА зв'язані із входом однієї й тієї ж вершини.

Рис. 3. Структурна схема автомата Мура

з кодуванням наборів мікрооперацій

Для оптимізації схеми автомата безліч станів A розбивається на класи B1, …, BI псевдоеквівалентних станів, що утворять розбивку ПA. Оптимізація досягається за рахунок однозначної ідентифікації класів BiПA і виключенням із ПСТ однакових підтаблиць. Для однозначної ідентифікації класів застосовується метод перетворення кодів станів:

У цьому випадку класи BiПA кодуються кодами K(Bi) розмірності R1=]log2I[, для чого використовуються змінні r. Перетворення виконується схемою перетворення кодів, що приводить до PCY-структури МПА Мура (рис. 4).

Рис. 4. Структурна схема автомата Мура

з перетворювачем кодів станів

У цій схемі КС1 реалізує систему функцій

Ф = Ф (, X), (8)

яка формована за перетвореною ПСТ. Схема КС2 реалізує систему функцій Y = Y (T).

Застосування цієї методики завжди дозволяє зменшити довжину ПСТ автомата Мура до довжини ПСТ еквівалентного автомата Мілі, але це досягається за рахунок введення додаткової апаратури.

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

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

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

1. Розробка структур і методів синтезу схем АЖЛ, що використають кодування наборів фрагмента змінних по граф-схемі алгоритму.

2. Дослідження області ефективного застосування запропонованих структур АЖЛ.

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

Застосування методу кодування наборів фрагмента змінних до PY-автомата Мілі приводить до появи структури автомата Мілі з кодуванням наборів фрагмента мікрооперацій (PYF-автомат Мілі), зображеної на рис. 5.

Рис. 5. Структурна схема PYF-автомата

У даній структурі безліч мікрооперацій Y ділиться на дві частини. Одна частина, що утворить фрагмент мікрооперацій (ФМО), формується Y-підсхемою аналогічно PY-автомату; друга частина формується унітарно P-підсхемою пристрою, реалізованої в базисі ПЛМ.

YF-підсхема будується на ПЗП й формує підмножина мікрооперацій Y1Y, що входять у фрагмент мікрооперацій. P-підсхема формує код I набору МО, що входять у ФМО, а також підмножина мікрооперацій Y2, формованих унітарно. У цілому PYF-автомат реалізує наступні системи функцій:

I = I (T, X), (9)

Y1 = Y1 (I), (10)

D = D (T, X), (11)

Y2 = Y2 (T, X), (12)

причому Y1Y2=Y й Y1Y2=. В іншому PYF-автомат функціонує аналогічно PY-автомату.

Будемо думати, що для реалізації блоків структури використовуються базиси ПЛМ і ПЗП, що мають матричне подання блоків. Як параметр, що характеризує інформаційну ємність блоків аналізованих структур, умовимося використати площі матриць “І” й “АБО” схем ПЛМ і ПЗП. При цьому з метою співвідношення інформаційних ємностей ПЛМ і ПЗП використовується спеціальний коефіцієнт вартості K, що характеризує відношення одиниці площі кристала ПЛМ до одиниці площі кристала ПЗП.

Ефективність структури PYF-автомата Мілі стосовно структури PY-автомата може бути виражена як відношення сумарних інформаційних ємностей схем у структурах PYF- і PYF-автоматах:

, (13)

де L – кількість логічних умов, аналізованих у ГСА; N – кількість МО, формованих автоматом; N1 – кількість МО, формованих YF-підсхемою; R – розрядність коду стану автомата; R0 – розрядність коду набору МО в PY-автоматі; R1 – розрядність коду набору МО в PYF-автоматі; R2 – кількість МО, формованих P-підсхемою в PYF-автоматі; QPY, QPYF – кількість внутрішніх термів ПЛМ PY- і PYF-автомата відповідно.

Для оцінки виграшу в Y-підсхемі може бути використана так названа ефективність по ПЗП, обумовлена відношенням ємностей ПЗП Y-підсхеми до YF-підсхемі:

. (14)

Тут W й W1 – кількість наборів в Y- і YF-підсхемі відповідно.

Метод синтезу PYF-автомата Мілі включає наступні основні етапи:

1. Оцінка заданої ГСА станами автомата Мілі.

2. Кодування станів.

3. Формування таблиці мікрооперацій.

4. Визначення вмісту фрагмента мікрооперацій.

5. Побудова перетвореної ПСТ (ППСТ). У порівнянні із ПСТ PY-автомата Мілі, у ППСТ стовпець, що містить код набору МО в Y-підсхемі, заміняється кодом набору фрагмента МО. Також додається стовпець Y2, який містить МО, що не ввійшли у фрагмент і формовані P-підсхемою.

6. Формування по ПСТ систем булевих функцій (9, 11, 12).

7. Синтез логічної схеми автомата.

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

При використанні методу кодування наборів фрагмента мікрооперацій у структурі PH-автомата Мілі одержуємо автомат Мілі з кодуванням рядків ПСТ і кодуванням наборів змінних або PHF-автомат Мілі (рис. 6).

Рис. 6. Структурна схема PHF-автомата Мілі

Тут P-підсхема реалізується на ПЛМ і формує наступні системи функцій:

I = I (X, T), (15)

Y2 = Y2 (X, T), (16)

Ф2 = Ф2 (X, T), (17)

де I – код рядка HF-підсхеми, що відповідає коду набора фрагмента змінних; Y2 і Ф2 – відповідно безлічі мікрооперацій і функцій порушення регістра пам'яті, що не ввійшли у фрагмент змінних. У загальному випадку Y2Y і Ф2Ф.

HF-підсхема реалізується на ПЗП й формує системи функцій

Y1 = Y1 (I), (18)

Ф1 = Ф1 (I), (19)

утворюючий фрагмент змінних. Відзначимо, що Y2Y і Ф2Ф, причому Y1Y2 = Y, Ф1Ф2 = Ф.

У цілому, PHF-автомат функціонує подібно PH-автомату.

Ефективність E(PHF) використання PHF-автомата стосовно еквівалентного PH-автомата Мілі визначається наступним виразом:

.(20)

Тут RI – розрядність коду набору змінних в PH-автоматі; RIF – розрядність коду набору рядка в PHF-автоматі; RФ1 – число функцій порушення, формованих HF-підсхемою; RФ2 – число функцій порушення, формованих P-підсхемою; RY1 – число МО, формованих HF-підсхемою; RY2 – число МО, формованих P-підсхемою.

Якщо як виграш розглядати лише зменшення ємності HF-підсхеми стосовно ємності H-підсхеми еквівалентного PH-автомата, то даний параметр, за аналогією з (14), може бути визначений у такий спосіб:

. (21)

Тут WH – число наборів змінних в H-підсхемі; WHF – число наборів змінних в PHF-підсхемі.

Метод синтезу PHF-автомата Мілі аналогічний методу синтезу PH-автомата, однак має додаткові етапи формування фрагмента змінних і кодування наборів змінних фрагмента.

Для оптимізації апаратурних витрат в Y-підсхемі базової структури автомата Мура з використанням методу кодування наборів фрагмента змінних пропонується представити Y-підсхему складною із двох частин:

- YF-підсхема, що зберігає набори фрагмента МО й керується частиною коду стану T?;

- YY-підсхема, що зберігає МО, що не ввійшли у фрагмент, і керується повним кодом стану автомата T.

Подібна розбивка Y-підсхеми приводить до PYF-автомата Мура (рис. 7).

Рис. 7. Структурна схема автомата Мура з кодуванням

наборів фрагменту змінних

YF-підсхема містить набори МО, для кодування яких потрібне менше число розрядів у порівнянні з Y-підсхемою базової структури автомата Мура, і формує безліч мікрооперацій Y1. YY-підсхема має те ж число адресних входів, що й Y-підсхема, і формує безліч МО Y2 = Y \ Y1. При цьому сумарна ємність YF- і YY-підсхем виявляється менше, ніж ємність Y-підсхеми в базовій структурі, при збереженні числа виходів ПЛМ P-підсхеми. Отже, структура на рис. 7 буде мати в загальному випадку менші апаратурні витрати в порівнянні з базовою структурою автомата Мура (рис. 3).

Ефективність даної структури стосовно еквівалентного PY-автомата Мура визначається виразом:

. (22)

Зменшення ємності Y-підсхеми визначається виразом:

. (23)

Метод синтезу PYF-автомата Мура містить наступні основні етапи:

1. Оцінка заданої ГСА станами автомата Мура.

2. Формування таблиці мікрооперацій.

3. Визначення вмісту фрагмента МО, що забезпечує максимальне значення ефективності.

4. Кодування наборів мікрооперацій у фрагменті.

5. Формування вмісту ПЗП YF-підсхеми з урахуванням кодів наборів мікрооперацій.

6. Кодування станів з урахуванням кодів наборів мікрооперацій.

7. Формування вмісту ПЗП YY-підсхеми з урахуванням кодів станів.

8. Формування ПСТ автомата.

9. Формування й мінімізація системи функцій переходів. Виконується аналогічно базовій структурі автомата Мура.

10. Синтез логічної схеми автомата в заданому елементному базисі.

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

В PCY-автоматі Мура (рис. 4) перетворювач коду традиційно реалізується на ПЗП. Це означає, що виділення фрагмента змінних може бути зроблене як у схемі ПК, так й в Y-підсхемі, що дозволяє одержати дві нових структури PCY-автомата Мура з кодуванням наборів фрагмента змінних:

PCFY-автомат Мура (рис. 8).

У даній структурі перетворювач коду складається із двох частин: –

Схема ПК містить підмножину (фрагмент) 1 змінних коду класу стану, для кодування яких потрібне менше число розрядів. Набори змінних у схемі ПК кодуються частиною розрядів коду стану T'.–

Схема ПК1, що є по суті частиною схеми ПК зі структури на рис. 4 і формуючу підмножину 1 змінних коду класу стану, що не ввійшли в безліч 1. Дана підмножина формується на підставі повного коду стану T.

Вирази для визначення ефективності структури PCFY-автомата Мура будуються аналогічно відповідним вираженням для інших розглянутих структур.

Метод синтезу PCFY-автомата аналогічний методу синтезу PCY-автомата Мура й має етап виділення фрагмента змінних у схемі ПЗП перетворювача кодів.

Рис. 8. Структурна схема PCFY-автомата Мура

PCYF-автомат Мура (рис. 9).

Рис. 9. Структурна схема PCYF-автомата Мура

Дана структура за принципом формування мікрооперацій збігається з PYF-автоматом Мура (рис. 7), а за принципом формування функцій переходів – зі структурою PCY-автомата Мура (рис. 8).

Вирази для визначення ефективності структури PCFY-автомата Мура будуються за тим ж принципом, що й для інших структур АЖЛ, реалізованих у базисі ПЛМ і ПЗП.

У роботі показано, що одночасне виділення фрагментів змінних в Y-підсхемі й перетворювачі кодів є неможливим.

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

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

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

3. Можливість одержання для розроблених структур бінарних прошивань для синтезу в FPGA або CPLD. Досягається за рахунок засобів синтезу й імплементації і є кінцевим результатом їхнього використання.

Як основний засіб моделювання обрана мова опису апаратури VHDL, що підтримується більшістю сучасних САПР програмувальних інтегральних схем.

При реалізації моделей структур мовою VHDL витриманий наступний принцип. Ті блоки структури, які традиційно реалізуються в базисі ПЛП (P-підсхема, регістр пам'яті), описані структурним стилем, тобто з використанням тільки тих операторів мови VHDL, які можуть бути синтезовані на кристал ПЛІС.

У той же час ті блоки, які необхідні для здійснення процесу моделювання, реалізуються моделюючим стилем, тобто з використанням усього безлічі операторів мови VHDL. До таких блоків ставляться, наприклад, Y- або H-підсхеми.

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

Також у третьому розділі роботи виконана програмна реалізація методів формування фрагмента змінних по заданому вмісту схеми ПЗП. Програма написана мовою C++ і враховує особливості формування фрагмента змінних для автоматів Мілі й Мура.

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

У дисертаційній роботі показані дослідження структури PYF-автомата Мілі, для якої виконане дослідження значень ефективності залежно від таких параметрів автомата, як кількість формованих мікрооперацій, кількість логічних умов, кількість внутрішніх термів P-підсхеми й коефіцієнт вартості базису ПЛП стосовно базису ПЗП. Дослідження проведені з використанням аналітичних виражень визначення ефективності запропонованих структур.

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

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

2. Значення ефективності нелінійно убуває зі збільшенням кількості логічних умов.

3. Значення ефективності різко убуває зі збільшенням кількості внутрішніх термів.

Аналогічні дослідження проведені для всіх запропонованих структур АЖЛ. Узагальнюючи результати досліджень, можна затверджувати, що в розроблених структурах автоматів Мілі виграш по апаратурним витратам досягає 20% у порівнянні з раніше відомими структурами. У структурах автоматів Мура з кодуванням наборів фрагмента змінна величина виграшу досягає 10%.

ВИСНОВКИ

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

У процесі досліджень вирішені наступні основні завдання:

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

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

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

ПЕРЕЛІК ОПУБЛІКОВАНИХ РОБІТ ЗДОБУВАЧА

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Баркалов А.А., Бабаков Р.М., Ахмад Бадер. Метод кодирования наборов фрагмента переменных // Зб. наукових праць ДНТУ. Серія “Інформатика, кібернетика та обчислювальна техніка”. Вип. 93. – Донецьк: ДонДТУ, 2005. – С. 175-181.

2. Баркалов А.А., Бабаков Р.М., Ахмад Бадер. Оптимизация автомата Мили с кодированием наборов микроопераций // Зб. наукових праць ДонНТУ. Серія “Обчислювальна техніка та автоматизація”. Випуск 107. – Донецьк: ДонНТУ, 2006. – С. 143-147.

3. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Хамада Бадер. Моделирование автомата Мили с кодированием наборов фрагмента микроопераций // Искусственный интеллект. – 2006. – №4. – С.361-367.

4. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Хамада Бадер. Фрагментация переменных в автомате Мили с кодированием строк прямой структурной таблицы // Радиотехника и информатика. – 2006. – №4. – С.31-33.

5. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Хамада Бадер. Исследование аппаратурных характеристик автомата Мили с кодированием наборов фрагмента микроопераций по VHDL-модели // Искусственный интеллект. – 2007. – №1. – С.117-122.

6. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Хамада Бадер. Метод кодирования наборов фрагмента переменных // Праці Сьомої Міжнародної науково-практичної конференції “Современные информационные и электронные технологии” (Одеса, 22-26 травня 2006 р.) – Одеса: ОНПУ, 2006 р. – Т.1. – С. 180.

7. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Бадер. Encoding of Collection of Fragment of Variables // Матеріали Четвертої Міжнародної науково-технічної конференції “Схід-Захід. Проектування і діагностика” (Сочі, 15-19 вересня 2006 р.) – Харків: ХНУРЕ, 2006 р. – С. 153-155.

8. Баркалов А.А., Бабаков Р.М., Ахмад Фуад Хамада Бадер. Моделирование устройств управления с кодированием наборов фрагмента переменных // Матеріали Сьомої Міжнародної науково-технічної конференції “Искусственный интеллект. Интеллектуальные и многопроцессорные системы – 2006” (Таганрог, 25-30 вересня 2006 р.) – Таганрог: Вид-во ТРТУ, 2006 р. – Т.2. – С. 88-90.

Особистий внесок здобувача в публікаціях: [1] – запропонований підхід до виділення фрагмента змінних у структурах цифрових пристроїв з гетерогенним елементним базисом; [2] – розроблені структура і аналітичне визначення ефективності автомата Мілі з кодуванням наборів фрагмента змінних; [3] – побудована VHDL-модель автомата Мілі з кодуванням наборів фрагмента мікрооперацій; [4] – розроблена структура керуючого автомата Мілі з кодуванням рядків прямої структурної таблиці і фрагментацією змінних; [5] – сформований підхід до оцінки апаратурних витрат в логічній схемі автомату Мілі з кодуванням наборів фрагменту мікрооперацій за допомогою VHDL-моделювання; [6] – запропоновано метод кодування наборів фрагменту змінних як шлях до зменшення апаратурних витрат у схемах автоматів з “жорсткою” логікою; [7] – подано обґрунтування доцільності використання методу кодування наборів фрагменту змінних; [8] – визначені вимоги щодо моделювання пристроїв керування з кодуванням наборів фрагменту змінних.

АНОТАЦІЯ

Ахмад Фуад Хамада Бадер. Методи оптимізації пристроїв керування з гетерогенною структурою. – Рукопис.

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

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

Ключові слова: керуючий автомат з “жорсткою” логікою, гетерогенний елементний базис, VHDL-моделювання, кодування наборів фрагменту змінних.

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. – ГВУЗ “Донецкий национальный технический университет”, Донецк, 2007.

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

Показано, что применение метода кодирования наборов фрагмента переменных позволяет уменьшить аппаратурные затраты в схемах, реализуемых в базисе ПЗУ, без увеличения затрат в схемах, реализуемых в базисе ПЛМ. В качестве схем, подвергающихся оптимизации, могут выступать, в зависимости от структуры управляющего автомата, схема формирования микроопераций (Y-подсхема), схема дешифрации кода строки (H-подсхема) либо схема формирования кодов классов псевдоэквивалентных состояний (схема ПК). В работе предложены методики формирования содержимого фрагмента переменных для автоматов Мили и Мура. Разработаны структуры и методы синтеза управляющих автоматов с “жесткой” логикой и кодированием наборов фрагмента переменных.

Для предложенных структур АЖЛ разработаны программные модели, использующие в своей основе язык описания аппаратуры VHDL. Модель автомата представляется состоящей их синтезируемой и моделирующей частей, что позволяет как проверить корректность логической организации структуры, так и выполнить синтез структуры на кристалл ПЛИС с возможностью получения технических характеристик автомата, синтезированного по конкретной ГСА.

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

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

Ключевые слова: управляющий автомат с “жесткой” логикой, гетерогенный элементный базис, VHDL-моделирование, кодирование наборов фрагмента переменных.

ABSTRACT

Ahmad Fuad Hamadah Bader. The methods of optimization of control units with heterogeneous structure. – Manuscript.

The dissertation on competition of a scientific degree of Candidate of Technical sciences on a speciality 05.13.13 – computers, systems and networks. – State high education institution “Donetsk National Technical University”, Donetsk, 2007.

On the basis of theoretical and experimental researches the new structures and formal methods of synthesis of control automata with hardware logic are proposed. It is shown that optimization of hardware expenses in the unit of forming of variables can be achieved by application of the method of coding o sets of fragment of variables. It is proposed to use the method of coding of sets of fragment of variables in structures of Mealy automaton with coding of sets of microoperations and with coding of lines of direct structural table, and also in structures of Moore automaton with coding of sets of microoperations and with coding of classes of pseudo-equal sates. New structures and methods of synthesis of Mealy and Moore automata with coding of sets of fragment of variables are developed. Methods, proposed in dissertation, allow to decrease hardware expenses in circuits of Mealy automaton up to 20%, and in structures of Moore automaton up to 10% according to known structures. The analytical estimations of effectiveness of proposed structures of automata from point of view of hardware expenses as functions of parameters of flow chart, are achieved. The area of effective using of proposed structures is defined.

Keywords: control automaton with hardware logic, heterogeneous basis, VHDL-modelling, coding of sets of fragment of variables.