Методи синтезу керуючих автоматів на конфігурованих логічних блоках

Размещено на http://www.allbest.ru/

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

УДК 681.324

МЕТОДИ СИНТЕЗУ КЕРУЮЧИХ АВТОМАТІВ НА КОНФІГУРОВАНИХ ЛОГІЧНИХ БЛОКАХ

Спеціальність 05.13.13

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

АВТОРЕФЕРАТ

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

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

КРАСІЧКОВ ОЛЕКСІЙ ОЛЕКСАНДРОВИЧ

Донецьк - 2004

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

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

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

Офіційні опоненти: д.т.н., професор Хаханов Володимир Іванович, декан факультету “Комп'ютерна інженерія” Харківського національного університету радіоелектроніки Міністерства освіти і науки України;

к.т.н., доцент Ладиженський Юрій Валентинович, доцент кафедри “Прикладна математика і інформатика” Донецького національного технічного університету.

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

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

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

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

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

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

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

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

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

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

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

Дисертаційна робота присвячена рішенню актуальної наукової задачі розробки структур і методів синтезу керуючих автоматів, орієнтованих на мінімізацію розмірності логічної схеми (ЛС) при реалізації її на КЛБ.

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

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

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

Виконати аналіз: існуючих методів декомпозиції і визначити шляхи їх оптимізації; існуючих структур і методів синтезу МПА і визначити шляхи їх оптимізації.

Розробити методи функціональної декомпозиції, що дозволяють мінімізувати час або число КЛБ при реалізації довільної БФ у базисі FPGA.

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

Одержати аналітичні оцінки складності реалізації МПА в базисі FPGA і розробити алгоритм вибору оптимальної структури автомата по заданій ГСА.

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

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

Предмет дослідження: логічна схема МПА Мілі з розділенням кодів станів, реалізована на КЛБ.

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

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

Розроблено метод приведення для функціональної декомпозиції шляхом представлення вихідної функції у виді сукупності двох підфункцій, що реалізуються на КЛБ. Запропонований метод дозволяє реалізувати довільну БФ, скорочуючи число переборів при виборі мінімальної реалізації до трьох, у порівнянні з відомими методами.

Розроблено метод розширення для функціональної декомпозиції, в основі якого лежить штучне збільшення числа аргументів вихідної БФ для визначення функції наступного КЛБ. Запропонований метод мінімізує число КЛБ при реалізації БФ, яка виконується загальним числом кроків, близьким до повного перебору.

Розроблено удосконалені структури і методи синтезу автоматів Мілі на лічильнику з розділенням кодів станів. Використання лінійних послідовностей станів чотирьох видів для запропонованих структур приводить до мінімізації ЛС автомата Мілі і мінімізації числа КЛБ при її декомпозиції, у порівнянні з базовою структурою МПА Мілі на лічильнику.

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

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

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

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

Апробація. Основні результати роботи доповідалися і обговорювалися на міжнародних науково-технічних конференціях: “Машиностроение и техносфера XXI века” (м. Севастополь, вересень 2002р.), “Автоматика-2002” (м. Донецьк, вересень 2002р.), на Третьому і Четвертому міжнародних науково-технічних семінарах “Практика и перспективы развития институционного партнёрства” (м. Таганрог, червень 2002р., м. Донецьк, квітень 2003р.), на науково-технічних семінарах: кафедри ЕОМ Донецького національного технічного університету (2002,2003 р.р.), інституту ISR (Institut fur Systemdynamik und Regelungstechnik - інститут динамічних систем і систем управління) Штутгартського університету (м. Штутгарт, Німеччина, липень 2003р.).

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

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

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

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

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

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

Складовою частиною операційного пристрою з динамічною реконфігурацією (рис. 1) є пристрій керування (ПК) - АЖЛ, реалізований на ПЛІС FPGA.

У залежності від критеріїв керування, аналізатор ситуації може змінювати алгоритм функціонування ПК за допомогою реконфігурації FPGA.

Кожна реконфігурація приводить до реалізації на ПЛІС ПК, що відповідає визначеній ГСА.

Відомо, що для ГСА, у яких не менш 75% вершин складають операторні, оптимізація апаратурних витрат у схемі автомата можлива за рахунок заміни регістра пам'яті лічильником.

Лінійною послідовністю станів (ЛПС) ГСА Г називається кінцевий кортеж g =<ag1,.. agFg>, такий, що для будь-якої пари станів agi, agi+1A, де i - номер компоненти кортежу g, існує перехід <agi, agi+1> автомата, що інтерпретує ГСА Г.

Для кожної ЛПС виконано таке кодування станів, що якщо <agi, agi+1> входить до ЛПС g (Г), то

K(agi+1)=K(agi)+1. (1)

У цьому випадку регістр пам'яті автомата можна замінити лічильником, що породжує С-автомати. На рис. 2 зображена структура автомата Мілі на лічильнику.

Автомат функціонує наступним образом. У момент часу t у СТ знаходиться код K(am) стану amAg. Якщо аm не є виходом ЛПС g, то Р-підсхема формує сигнал Inc і по сигналу Clock до вмісту СТ додається одиниця, тим самим, згідно (1), відбувається перехід у наступний стан ЛПС g. У протилежному випадку сигнал Inc не формується і Р-підсхема формує функції Ф=Ф(Т,Х), що викликають перехід у стан аsA. У кожнім такті Р-підсхема також формує вихідні сигнали Y=Y(T,X).

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

Формування мінімальної розбивки множини станів на класи, що відповідають ЛПС g вихідної ГСА.

Оптимальне кодування станів згідно (1).

Формування прямої структурної таблиці (ПСТ) РС1-автомата.

Реалізація Р-підсхеми в заданому елементному базисі.

Відомі методи оптимізації апаратурних витрат у РС1-автоматах Мілі пов'язані з:

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

2. Введенням до структури автомата Y-підсхеми при різному кодуванні мікрооперацій. У цьому випадку також відбувається збільшення часу спрацьовування схеми.

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

В дисертаційній роботі пропонується розділення кодів станів в автоматі Мілі на лічильнику для оптимізації його Р-підсхеми (РС1R-автомати). При цьому код стану am представляється у вигляді конкатенації

K(am) = K(бi) * K' (am), (2)

де K(бi) - R1-разрядний код ЛПС бi, до якої входить am, K'(am) - R2-розрядний код стану am у межах ЛПС бi, * - знак конкатенації, R1=]log2G[, R2 = ]log2Fi[, де G - загальне число ЛПС, Fi - число станів у найдовшій ЛПС.

Замість R розрядного лічильника РС1-автомата, у РС1R-автоматі пропонується використовувати R1-розрядний регістр для збереження коду ЛПС і R2-розрядний лічильник для адресації станів у межах ЛПС.

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

1. Розробка структур і методів синтезу РС1R-автоматів, що орієнтовані на мінімізацію ЛС і не приводять до збільшення часу виконання алгоритму.

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

3. Одержання аналітичних оцінок складності реалізації МПА в базисі FPGA і розробка алгоритму вибору оптимальної структури автомата по заданій ГСА.

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

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

РС1R-автомат (рис. 3) функціонує таким чином. При переході до наступної ЛПС, по сигналу Inc=0 в регістр RG заноситься код ФC ЛПС бg, а в лічильник СТ - код ФCT стану am у межах ЛПС бg.

Адресація наступного стану am+1 в межах ЛПС бg відбувається шляхом інкременту лічильника по сигналу Inc=1, при цьому значення ФСТ та ФС не визначені, а код стану автомата визначається парою <ТС,ТСТ>.

На регістр і на лічильник надходять також сигнали синхронізації (Clk) і скидання (Reset), не показані в структурі автомата.

До ЛПС РС1R-автомата Мілі можуть входити як операторні, так і умовні вершини. У зв'язку з цим, у дисертаційній роботі пропонується використовувати чотири види ЛПС, ефективне використання яких дозволяє оптимізувати Р-підсхему РС1R-автомата.

У відповідності з кожним видом ЛПС у роботі запропоновано чотири структури Р1СR-автоматів:

1. РС1R1-автомат. ЛПС першого роду може мати входи з інших ЛПС і умовні вершини. Структура відповідає рис. 3 при наявності обох зв'язків, позначених пунктиром.

2. РС1R2-автомат. ЛПС другого роду не має входів з інших ЛПС але може містити умовні вершини. Структура відповідає рис. 3 при наявності тільки зворотного зв'язку ТСТ. (При Inc=0 лічильник скидається, а в регістр заноситься код ФС).

3. РС1R3-автомат. ЛПС третього роду може мати входи з інших ЛПС але не містить умовних вершин. Структура відповідає рис. 3 при наявності тільки зв'язку ФСТ.

4. РС1R4-автомат. ЛПС четвертого роду не має входів з інших ЛПС і не містить умовних вершин. Структура відповідає рис. 3 без зв'язків, позначених пунктиром. (При Inc=0 лічильник скидається, а в регістр заноситься код ФС).

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

Формування (Г) - мінімальної розбивки множини станів на ЛПС.

Кодування ЛПС (Г) і станів am у межах кожної ЛПС.

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

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

Вибір ефективної структури автомата може бути однозначно здійснений тільки для конкретної ГСА.

Складність Qi характеризує сумарні витрати усіх функцій Р-підсхеми РС1R-автомата:

Qi = Nарг Nф , ( ), (3)

де Nарг - число аргументів Р-підсхеми, Nф - число функцій Р-підсхеми.

Апаратурні витрати РС1R-автоматів розрізняються тільки параметром Qi, котрий виражається сумарним числом входів усіх функцій збудження Р-підсхеми (табл. 1).

Таблиця 1

Складність Р-підсхеми PC1R-автоматів

i	Структура автомата	Складність Qi
1	PC1R1	(+)·(++L)
2	PC1R2	·(++L)
3	PC1R3	(+)·(+L)
4	PC1R4	·(+L)

В табл. 1 прийняті наступні позначення:

=]log2Gi[ - розрядність регістра RG, де Gi - число ЛПС i-го роду;

=]log2Fi[ - розрядність лічильника CT, де Fi - максимальне число станів у ЛПС i-го роду.

В дисертаційній роботі пропонується алгоритм вибору оптимальної структури PC1R-автомата для заданої ГСА (рис. 4).

Складність Р-підсхеми PС1R-автомата залежить, насамперед, від числа ЛПС переважного роду в заданій ГСА. Найвищою швидкодією при найменших апаратурних витратах володіють PC1R4-автомати.

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

Основою для реалізації БФ на FPGA є конфігуровані логічні блоки з S входами, причому кожен КЛБ дозволяє реалізувати довільну БФ S аргументів. Для реалізації БФ N аргументів у базисі КЛБ з S входами, необхідно виконати функціональну декомпозицію, тобто, представити функцію у виді сукупності підфункцій M аргументів, причому .

Більшість методів декомпозиції побудовано на перетворенні Шеннона:

(4)

Реалізація БФ на підставі (4) називається каскадним методом, при цьому число К КЛБ у схемі визначається як і є надлишковим.

К = 42N-S - 3 (5)

Метод PUB-декомпозиції є удосконаленням каскадного методу і полягає в реалізації частини або всієї БФ Y у виді структури, зображеної на рис. 5.

Даний метод, як і каскадний, завжди приводить до реалізації БФ на КЛБ, однак мінімізація числа КЛБ носить випадковий характер і залежить безпосередньо від БФ і розбивки аргументів на множини А и В.

Метод декомпозиції Рота-Карпа (Roth-Karp) характеризується мінімальним числом КЛБ при реалізації частини або всієї БФ у вигляді структури на рис. 6.

Однак, головним недоліком методу є мала доля БФ, реалізованих у вигляді:

. (6)

Серед N1 функцій (M+N) аргументів ( ), у вигляді (6) реалізується N2 функцій:

(7)

Декомпозиція Куртіса-Ашенхерста (Curtis-Ashenhurst) є модифікацією метода Рота-Карпа (рис. 7).

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

В дисертаційній роботі запропоновано метод приведення функціональної декомпозиції, що є модифікацією методу Куртіса-Ашенхерста. Реалізація довільної БФ виконується послідовно, по системі:

(8)

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

Таблиця 2

Кодування функцій приведення для базових функцій суміщення

Y	Y'	Y''	Y'	Y''	Y'	Y''
0 0	0 0	0 0	1 0	0 1	0 0	0 0
0 1	0 1	0 0	1 1	0 1	0 0	0 1
1 0	0 1	1 1	1 0	1 1	/1 0	0 0
1 1	0 0	1 1	1 1	1 1	1 0	0 1
F	Y' Y''	Y'& Y''	Y' Y''

Достоїнством методу є швидка реалізація довільної БФ з необмеженим числом аргументів на КЛБ з S=2 входами. На кожнім кроці виконується і аналізується три варіанти реалізації функцій приведення.

Значними недоліками є ускладнення реалізації на КЛБ із S>2, а також надмірність приведення для кожного з N-S аргументів БФ.

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

Вихідними даними для декомпозиції служить каскадна структура невизначених S-входових КЛБ Gi, з'єднаних у повне К-рівневе дерево. Число рівнів К для реалізації БФ N аргументів, складає:

(9)

де операція ] [ означає округлення до більшого цілого.

Загальне число КЛБ P у структурі складає:

(10)

Сумарне число входів на рівні К складає

Метод розширення включає наступні етапи:

1. Визначення аргументів функції Gi наступного КЛБ.

2. Розширення БФ Y на аргумент Gi.

3. Вибір області визначення функції Gi.

4. Визначення аргументів частини логічної схеми, що залишилася.

5. Мінімізація частини логічної схеми, що залишилася.

Максимальне число переборів в одному проході метода розширення складає:

, (11)

що відповідає добутку переборів на етапах 1, 3 і 5.

При експериментальному дослідженні методу показано можливість знаходження рішення до завершення усіх переборів, обумовлених (11).

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

Для визначення ефективності методів декомпозиції встановлені наступні залежності:

1. теоретичний мінімум КЛБ для реалізації БФ;

2. максимум КЛБ для реалізації довільної БФ;

3. число КЛБ для реалізації БФ методом приведення;

4. число КЛБ для реалізації БФ методом розширення;

5. теоретичний мінімум часу для декомпозиції БФ;

6. час, затрачуваний на декомпозицію БФ методом приведення;

7. час, затрачуваний на декомпозицію БФ методом розширення.

Для визначення експериментальних залежностей і застосовано запропонований А.Д. Закревським підхід, в основі якого лежить використання потоків псевдовипадкових булевих функцій для дослідження алгоритмів декомпозиції. Для кожного обумовленого параметра береться середнє арифметичне число логічних блоків, отриманих у результаті декомпозиції групи БФ (рис. 8, 9).

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

(12)

При реалізації будь-якої БФ методом приведення

В якості використовується середнє арифметичне число експериментально отриманих переборів. Таким чином отримані графіки залежностей (рис. 10) для S=25. Залежність S=* відповідає , розрахованому по формулі (11) для S=3.

Для проведення досліджень PC1R-автоматів використовується метод імовірнісного підходу, запропонований Г.І. Новиковим, який полягає в дослідженні не конкретних ГСА, а їх класів, що характеризуються двома основними параметрам: часткою операторних вершин - p1 і часткою умовних вершин - p2. Згідно з цим методом число Н рядків прямої структурної таблиці визначається так:

H=10,6 + 2,16 p1K/ p3, (13)

де K - загальне число вершин ГСА, p3 відношення числа операторних вершин до числа наборів мікрооперацій.

На рис. 11 показані залежності складності Qi Р-підсхем PC1R-автоматів від числа Н за умови R1=R2 і L=100 .

Найменші витрати для тих самих ГСА властиві PC1R4-автоматам, найбільші PC1- і PC1R1-автоматам, складність Р-підсхем яких приблизно збігається.

Залежність витрат PC1R-автоматів від числа логічних умов при R1=R2 є практично лінійною для всіх структур. Так, при збільшенні L з 10 до 100, відбувається збільшення складності Р-підсхеми всіх структур приблизно в 4 рази.

На рис. 12 показано вплив відношення R1/R2 на витрати розроблених структур PC1R-автоматів при фіксованих L=100, H = 10 000.

З залежностей на рис. 12 випливає, що розділ кодів станів приводить до значної оптимізації Р-підсхеми в PC1R2- і PC1R4-автоматах.

На рис. 13 показані залежності числа аргументів Р-підсхеми PC1R-автоматів без обліку числа L логічних умов від числа Н рядків ПСТ.

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

ВИСНОВКИ

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

Виконано аналіз: відомих структур автоматів на лічильниках і їх особливостей; сучасного елементного базису, використованого при синтезі цифрових пристроїв; відомих методів реалізації систем булевих функцій у базисі FPGA.

Розроблено структури і методи синтезу автоматів Мілі на лічильнику з розділом кодів станів, запропоновано алгоритм вибору оптимальної структури автомата.

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

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

Отримано аналітичні залежності числа КЛБ від числа аргументів реалізованих БФ.

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

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

1. Баркалов А. А., Саломатин В.А., Красичков А.А. Синтез микропрограммного устройства управления со статической реконфигурацией // Наукові праці ДонДТУ. Серія "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 29. - Севастополь: “Вебер”. - 2001. - C.172-179.

2. Баркалов А.А., Красичков А.А. Синтез автомата Мили на счетчике. Синтез многоуровневых схем автоматов Мили на счетчике // Синтез пристроїв керування на програмованих логічних пристроях. - Донецьк: РВА ДонНТУ, 2002. - C.237-248.

3. Баркалов А.А., Ковалев С.А., Красичков А.А. Оптимизация логической схемы автомата Мили на программируемых логических устройствах и счетчиках // Известия ТРТУ-ДонНТУ. Матеріали Третього міжнародного науково-практичного семінару “Практика и перспективы развития институционного партнерства”. В 2-х кн. - Таганрог: ТРТУ.- 2002.- №2. кн.1. - C.34-40.

4. Баркалов А.А., Красичков А.А. Методы декомпозиции булевых функций // Наукові праці ДонНТУ. Серія: “Інформатика, кібернетика та обчислювальна техніка”, випуск 39. - Донецьк: ДонНТУ. - 2002. - C.116-121.

5. Красичков А.А. Синтез микропрограммных автоматов на FPGA // Наукові праці ДонНТУ. Серія: “Обчислювальна техніка та автоматизація”. Випуск 64. - Донецьк: ДонНТУ. - 2003. - C. 192-198.

6. Красичков А.А. Синтез комбинационных схем на БИС с архитектурой FPGA // Синтез операційних пристроїв. - Донецьк: РВА ДонНТУ, 2003. - C.89-102.

7. Баркалов А.А., Красичков А.А. Декомпозиция булевых функций методом приведения // Известия ТРТУ-ДонНТУ. Матеріали IV міжнародного науково-практичного семінару “Практика и перспективы развития институционного партнёрства”. В 2-х т. - Донецьк. - Т.1. - C.31-37.

Особистий внесок здобувача в публікаціях: [1] Структура і метод синтезу пристрою керування із статичною реконфігурацією на базі автомата з програмованою логікою; [2] Напрямки оптимізації МПА Мілі на лічильнику; [3] Структура МПА Мілі з розділенням кодів станів та шляхи її подальшої оптимізації; [4] Аналітичний аналіз та приклади декомпозиції булевих функцій методом Рота-Карпа; [7] Метод приведення функціональної декомпозиції.

АНОТАЦІЯ

Красiчков О.О. Методи синтезу керуючих автоматів на конфігурованих логічних блоках. - Рукопис.

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

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

Запропоновано метод приведення декомпозиції булевих функцій шляхом представлення вихідної функції у виді сукупності двох свідомо реалізованих на КЛБ підфункцій.

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

Отримано експериментальні залежності числа кроків запропонованих методів декомпозиції і числа КЛБ від числа аргументів реалізованих функцій. Для отриманих структур виконано аналітичні оцінки витрат логічних схем автоматів. Дослідження проводилися з застосуванням імовірнісного підходу на окремих класах ГСА.

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

автомат мілі логічна схема

АННОТАЦИЯ

Красичков А.А. Методы синтеза управляющих автоматов на конфигурируемых логических блоках. - Рукопись.

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

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

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

Предложен метод приведения декомпозиции булевых функций путем представления исходной функции в виде совокупности двух заведомо реализуемых на КЛБ подфункций. Предложенный метод позволяет реализовать любую БФ с произвольным числом аргументов, сокращая число переборов при выборе минимальной реализации до трех, по сравнению с известными методами. Реализация функций методом приведения основана на декомпозиции Куртиса-Ашенхерста и построена на использовании условия разложения методом Рота-Карпа.

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

Получены экспериментальные зависимости числа КЛБ от числа аргументов реализуемых функций. Среднее число КЛБ для метода приведения, полученное экспериментально, близко максимально возможному и составляет 70% от каскадного метода. Экспериментальные исследования метода расширения показали, что число КЛБ в среднем на порядок выше, чем минимальное теоретическое, определяемое декомпозицией Рота-Карпа. Общее число шагов декомпозиции методом расширения, полученное экспериментально, близко к полному перебору решений, определенных для данного метода аналитически, и в среднем, на порядок меньше.

Исследования методов декомпозиции проводились для реализации функций на ПЛИС с архитектурой FPGA, базисом которых являются КЛБ с числом входов от двух до пяти.

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

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

Установлено, что на сложность логической схемы автомата существенное влияние оказывает количество линейных последова-тельностей состояний определенного рода, преобладающих в ГСА, что, в свою очередь, выражается в соотношении разрядностей регистра и счетчика. Так, при уменьшении этого соотношения с 1 до 0.1 происходит снижение затрат Р-подсхемы на 83% по отношению к базовой структуре автомата Мили на счетчике.

Предложенные структуры и методы синтеза автоматов Мили на счетчике с разделением кодов состояний позволяют реализовать управляющие автоматы с числом строк прямой структурной таблицы около 100000 на современных ПЛИС с архитектурой FPGA.

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

ABSTRACT

Krasichkov A.A. Methods of synthesis of control units on configurable logic blocks. - Manuscript.

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

On the basis of theoretical and experimental researches new structures and methods of synthesis of Mealy control unit on the counter with division of state codes are offered. Use of linear state sequences of four kinds is offered, which effective application results in minimization of the logic circuit of the control unit. The algorithm of a choice of optimum structure of the control unit for the given flow-chart is developed.

The method of reduction of the Boolean functions decomposition is offered by representation of initial function as two subfunctions set which obviously realized on CLBs.

The method of expansion of functional decomposition is offered, in which basis the artificial increase of the arguments number of the initial Boolean function with its further minimization.

The experimental dependences of steps number of the offered methods of decomposition and CLBs' number from number of arguments of the realized functions are received. The analytical estimations of expenses of the logic circuits of control units are executed for the proposed structures. The research was made with probability method application of the approach for separate classes of the flow-charts.

Key words: configurable logic block, division of codes, linear state sequence, decomposition, reconfiguration, programmable logic integrated circuits.

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