Синтез чотирирівневої схеми суміщеного автомата
Запропоновано метод зменшення апаратурних витрат у схемі суміщеного автомата, що реалізовується в спільному базисі елементів LUT і блоків пам'яті EMB. Метод заснований на заміні логічних умов і розбитті множин логічних станів на класи. Кожен клас відповідає окремому блоку схеми. Такий підхід пр...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2019
|
| Schriftenreihe: | Control systems & computers |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/181045 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Синтез чотирирівневої схеми суміщеного автомата / О.О., Баркалов, Л.О. Тітаренко,Я.Є. Візор, О.В. Матвієнко// Control systems & computers. — 2019. — № 5. — С. 12-22. — Бібліогр.: 21 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-181045 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1810452021-10-31T01:27:08Z Синтез чотирирівневої схеми суміщеного автомата Баркалов, О.О. Тітаренко, Л.О. Візор, Я.Є. Матвієнко, О.В. Fundamental Problems in Computer Science Запропоновано метод зменшення апаратурних витрат у схемі суміщеного автомата, що реалізовується в спільному базисі елементів LUT і блоків пам'яті EMB. Метод заснований на заміні логічних умов і розбитті множин логічних станів на класи. Кожен клас відповідає окремому блоку схеми. Такий підхід призводить до схем з регулярною структурою і чотирма логічними рівнями. Наведено приклад використання запропонованого методу. Показано умови його застосування. Цель. Предложенная модель приводит к схемам с регулярными связями. Это упрощает задачи размещения и трассировки при реализации схемы СМПА. Положительной чертой предложенной модели является тот факт, что сигналы Clock и Start связаны только с одним блоком схемы. Это позволяет избежать проблем, связанных с так называемым перекосом синхронизации. Результаты. Анализ специальной библиотеки показал, что предложенный метод целесообразно использовать для 68 процентов тестовых примеров. При этом для 76 процентов примеров может быть использована исходная модель. Для 24 процентов примеров, при выполнении соответствующего условия, может быть использована только предложенная модель. Наши исследования с использованием FPGA Virtex-6 показали, что по мере роста параметров R, L, N увеличивается выигрыш в быстродействии и потребляемой энергии используемой аппаратуры с применением предложенных автоматов в сравнении с исходными. Приведен пример использования предложенного метода и показаны условия его применения. Purpose. The proposed model leads to schemes with regular connections. This simplifies the placement and tracing tasks when implementing the SMPA scheme. A positive feature of the proposed model is the fact that the Clock and Start signals are associated with only one block of the circuit. This avoids the problems associated with the so-called distortion synchronization. Results. Analysis of a special library showed that the proposed method is advisable to use for 68% of test cases. Moreover, for 76% of the examples, the original model can be used. For 24% of the examples, if the corresponding condition is met, only the proposed model can be used. Our studies using Virtex-6 FPGAs showed that as the parameters R, L, N increase, the gain in equipment, speed and energy consumption for the proposed machines compared to the original ones is increased An example is shown for using of proposed method. The conditions of its application are shown. 2019 Article Синтез чотирирівневої схеми суміщеного автомата / О.О., Баркалов, Л.О. Тітаренко,Я.Є. Візор, О.В. Матвієнко// Control systems & computers. — 2019. — № 5. — С. 12-22. — Бібліогр.: 21 назв. — укр. 2706-8145 DOI: doi.org/10.15407/usim.2019.05.012 http://dspace.nbuv.gov.ua/handle/123456789/181045 004.274 uk Control systems & computers Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science |
| spellingShingle |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science Баркалов, О.О. Тітаренко, Л.О. Візор, Я.Є. Матвієнко, О.В. Синтез чотирирівневої схеми суміщеного автомата Control systems & computers |
| description |
Запропоновано метод зменшення апаратурних витрат у схемі суміщеного автомата, що реалізовується в спільному базисі елементів LUT і блоків пам'яті EMB. Метод заснований на заміні логічних умов і розбитті множин логічних станів на класи. Кожен клас відповідає окремому блоку схеми. Такий підхід призводить до схем з регулярною структурою і чотирма логічними рівнями. Наведено приклад використання запропонованого методу. Показано умови його застосування. |
| format |
Article |
| author |
Баркалов, О.О. Тітаренко, Л.О. Візор, Я.Є. Матвієнко, О.В. |
| author_facet |
Баркалов, О.О. Тітаренко, Л.О. Візор, Я.Є. Матвієнко, О.В. |
| author_sort |
Баркалов, О.О. |
| title |
Синтез чотирирівневої схеми суміщеного автомата |
| title_short |
Синтез чотирирівневої схеми суміщеного автомата |
| title_full |
Синтез чотирирівневої схеми суміщеного автомата |
| title_fullStr |
Синтез чотирирівневої схеми суміщеного автомата |
| title_full_unstemmed |
Синтез чотирирівневої схеми суміщеного автомата |
| title_sort |
синтез чотирирівневої схеми суміщеного автомата |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2019 |
| topic_facet |
Fundamental Problems in Computer Science |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181045 |
| citation_txt |
Синтез чотирирівневої схеми суміщеного автомата / О.О., Баркалов, Л.О. Тітаренко,Я.Є. Візор, О.В. Матвієнко// Control systems & computers. — 2019. — № 5. — С. 12-22. — Бібліогр.: 21 назв. — укр. |
| series |
Control systems & computers |
| work_keys_str_mv |
AT barkalovoo sintezčotirirívnevoíshemisumíŝenogoavtomata AT títarenkolo sintezčotirirívnevoíshemisumíŝenogoavtomata AT vízorâê sintezčotirirívnevoíshemisumíŝenogoavtomata AT matvíênkoov sintezčotirirívnevoíshemisumíŝenogoavtomata |
| first_indexed |
2025-07-15T21:34:34Z |
| last_indexed |
2025-07-15T21:34:34Z |
| _version_ |
1837750314135977984 |
| fulltext |
12 iSSN 2706-8145, control systems and computers, 2019, № 3
doi.org/10.15407/usim.2019.05.012
удк 004.274
о.о. БарКаЛов, д-р техн. наук, проф., університет Зеленогурський (Польща),
вул. Підгірна, 50, Зелена гура, 65246, Польща,
a.barkalov@imei.uz.zgora.pl
Л.о. тІтаренКо, д-р техн. наук, проф., університет Зеленогурський (Польща),
вул. Підгірна, 50, Зелена гура, 65246, Польща,
l.titarenko@iie.uz.zgora.pl, d_ts@nure.ua
я.Є. вІЗор, канд. техн. наук, ст. наук. співробітник,
Ін-т кібернетики ім. В.м. глушкова НаН україни,
03187, м. київ, просп. акад. глушкова, 40, україна,
yaviz@ukr.neta
о.в. матвІЄнКо, наук. співробітник,
Ін-т кібернетики ім. В.м. глушкова НаН україни,
03187, м. київ, просп. акад. глушкова, 40, україна,
matv@online.ua
синтеЗ ЧотирирІвневоЇ
сХеми сумІЩеноГо автомата
Запропоновано метод зменшення апаратурних витрат у схемі суміщеного автомата, що реалізовується в спільному
базисі елементів LUT і блоків пам'яті EMB. Метод заснований на заміні логічних умов і розбитті множин логічних
станів на класи. Кожен клас відповідає окремому блоку схеми. Такий підхід призводить до схем з регулярною
структурою і чотирма логічними рівнями. Наведено приклад використання запропонованого методу. Показано умови
його застосування.
Ключові слова: суміщений автомат, синтез, LUT, EMB, розбиття, FPGA.
Вступ
На сьогодні цифрові системи є невід’ємною
частиною сучасної цивілізації [1] Це пов’язано
з широким використанням вбудованих, авто-
номних і мобільних пристроїв [1, 2] . Важливою
частиною подібних систем є пристрій керуван-
ня (ПК) [3, 4] . Ефективність ПК багато в чому
визначає ефективність системи загалом . І тут
важливе значення має зменшення витрат апа-
ратури у схемі ПК . Вирішння цієї проблеми
дає змогу зменшити енергоспоживання і час
затримки схеми ПК .
Методи вирішення цього завдання багато в
чому залежать від моделі, яка задає поведін-
ку ПК, та елементного базису для реалізації
схеми ПК [5, 6] . У цій статті ми розглядаємо
задачу реалізації схеми суміщеного мікропро-
грамного автомата (СМПА) [7, 8] в базисі про-
грамованих логічних інтегральних схем FPGA
(field-programmable logic arrays) [9, 10] . Вибір
моделі зумовлений її широким використанням
для реалізації ПК сучасних цифрових систем
[11] . Вибір базису зумовлений тим, що FPGA
використовуються в багатьох цифрових систе-
мах [12, 13] . При цьому вважається, що вони
iSSN 2706-8145, control systems and computers, 2019, № 5 13
Синтез чотирирівневої схеми суміщеного автомата
домінуватимуть у цій галузі найближчими де-
сятиліттями [14] .
Пропонований нами метод засновано на
використанні структурної декомпозиції [13]
схем СМПА . Для зменшення загальних витрат
апаратури ми використовуємо й елементи таб-
личного типу LUT (look-up table), й вбудовані
блоки пам'яті EMB (embedded memory blocks) .
Для запровадження закону функціонування
ПК ми використовуємо мову граф-схеми ал-
горитму (ГСА) [14] .
Реалізація схеми
СМПА в базисі FPGA
Модель СМПА об'єднує в собі риси авто-
матів Мілі і Мура [7, 8] . Множина станів
A = {a
1
,…, a
M
} формується, як для атомата Мура
[11] . Множина вихідних змінних (мікроопера-
цій) Y є об’єднанням множин Y
A
(мікроопера-
ції автомата Мілі) і Y
B
(мікрооперації автомата
Мура) . Мікрооперації y
n
∈ Y
A
записуються біля
дуг ГСА, а мікрооперації y
n
∈ Y
B
— в операцій-
них вершинах ГСА [11] .
Для синтезу схеми СМПА необхідно побуду-
вати пряму структурну таблицю (ПСТ) . Цьому
етапу передує кодування станів, коли кожному
стану a
m
∈A ставиться у відповідність двійковий
код K(a
m
) розрядності R:
R = | log
2
M . (1)
Для кодування станів використовуються
внутрішні змінні, що утворюють множину T =
= {T
1
, . . .,T
R
} . Коди K(a
m
) зберігаються в спеці-
альному регістрі (RG), що складається з R дво-
тактних тригерів . Ми розглядаємо випадок,
коли ці тригери мають інформаційні входи
типу D [6] . Для зміни вмісту RG використову-
ються функції збудження пам’яті, що утворю-
ють множину Φ = {D
1
, . . ., D
R
} .
У ПСТ є такі стовпці [11]: a
m
— початковий
стан СМПА; K(a
m
) — код стану a
m
∈A; a
s
— стан
переходу; K(a
S
) — код стану a
s
∈A; X
h
— вхідний
сигнал, що визначає перехід з < a
m,
a
S
> і дорів-
нює кон’юнкції вхідних змінних із множини
X={x
1
,…, x
L
}; Y
Ah
— набір мікрооперацій (НМО)
автомата Мілі, що формується на переході
< a
m,
a
S
>; Φ
h
— набір функцій D
r
∈Φ, що до-
рівнюють одиниці для запису в RG коду K(a
S
);
h — номер переходу ( 1,h H= ) . У стовпці a
m
за-
писуються НМО автомата Мура, що форму-
ються в цьому стані . Метод формування ПСТ
щодо ГСА Γ розглянуто, наприклад, в [11] .
Схема СМПА задається системами бу-
левих функцій (СБФ), що формуються на
основі ПСТ:
Φ = Φ(T, X); (2)
Y
A
=Y
A
(T, X); (3)
Y
B
=Y
B
(T) . (4)
Кожна із систем (2)–(4) відповідає окремо-
му блоку у схемі СМПА [7, 8] .
У цій статті ми розглядаємо задачу реаліза-
ції систем (2)–(4) в базисі FPGA . Для реалізації
схеми ми використовуватимемо елементи LUT
і EMB . Розгляньмо головні характеристики еле-
ментного базису .
Нехай LUTer означає блок, що складаєть-
ся з елементів LUT, програмованих тригерів і
міжз’єднань . Таким чином, кожен LUTer склада-
ється з логічних елементів, наведених на рис . 1 .
Елемент LUT реалізує довільну логічну
функцію f
C
, яка залежить від не більше, ніж S
L
аргументів . Вихід f
C
подається на вхід D дво-
тактного тригера . Імпульс Start використову-
ється для операції f
R
: = 0 . Імпульс Clock ініці-
ює операцію f
R
= f
C
. Вихід логічного елемента
може бути або комбінаційним (f
L
= f
C
), або
реєстровим (f
L
= f
R
) . Для вибору типу виходу
використовується мультиплексор MX і вну-
трішній сигнал y0:
0 0L C Rf y f y f= ∨ .
Системи (2)–(4) визначають однорівневу
схему СМПА [7] . Схема складається з блоків
LUTerA (реалізує систему (3)), LUTerB (реа-
лізує систему (4)) і LUTerT (реалізує систему
(2)) . Блок LUTerT включає регістр RG, розпо-
Start
ClockLUT
X
SL
.
.
.
.
TT
C
D
R
fC
fR
y0
fL
MX
Рис. 1. Логічний елемент блоку LUTer
14 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
О.О. Баркалов, Л.О. Тітаренко, Я.Є. Візор, О.В. Матвієнко
ділений між логічними елементами . Тому блок
має виходи T
r
∈∈ T і входи Clock і Start (рис . 2) .
Позначмо цей СМПА символом U
1
.
Сучасні FPGA мають значне число блоків
EMB [12, 13] . Характерною рисою EMB є мож-
ливість зміни числа адресних входів (S
A
) і роз-
рядності комірок пам’яті (t
F
) при збереженні
постійної ємності (V
0
):
0 2SA FV t= × . (5)
Кожна пара <S
A
, t
F
>, яка задовольнить (5),
визначає конфігурацію EMB . Для сучасних
FPGA характерні наступні конфігурації блоків
EMB: <15, 1>, <14, 2>, . . ., <9, 64> . Таким чи-
ном, зменшення S
A
на одиницю подвоює число
виходів блоку t
F
.
Наявність різних конфігурацій дає змо-
гу узгодити параметри СМПА і блоку EMB .
Нехай |Y
A
|=N
A
, |Y
B
|=N
B
, |Y|=N=N
A
+N
B
. Нехай
виконується така умова:
02 ( )L R N R V+ × + ≤ . (6)
При цьому СМПА реалізується у вигляді од-
ного блоку EMB . Аналіз бібліотеки стандарт-
них автоматів [16] показав, що умова (6) має
місце для 68 відсотків всіх прикладів .
оптимізація
схеми смпа в базисі FpGA
Елементи LUT мають вкрай обмежене число
входів (S
L
≤ 6) [15, 16] . Аналіз [16] показує, що
для більшості автоматів дотримується умова:
L+R>S
L
. (7)
У цьому разі схеми блоків LUTerA і LUTerT
мають більше одного рівня елементів . Це при-
зводить до нерегулярних схем із великим чис-
лом міжз’єднань . Це призводить до збільшення
паразитних ємностей, відповідальних за по-
довження часу поширення сигналів і збіль-
шення споживаної енергії [17] . При цьому для
реалізації схеми використовуються складні ме-
тоди функціональної декомпозиції [14] .
Якщо умова (6) виконується, то для реа-
лізації схеми СМПА потрібно кілька блоків
EMB . Це призводить до значної надлишко-
вості схеми . Крім того, завдання взагалі не має
розв’язку, якщо виконується умова
2L+R > V
0
. (8)
Аналіз бібліотеки [16] показав, що умо-
ва (8) виконується для 24 відсотків тестових
прикладів . При цьому блоки EMB інтенсивно
використовуються для реалізації різних бло-
ків цифрових систем [18] . Як наслідок, роз-
робник ПК може мати тільки обмежене число
блоків EMB .
За виконання умов (7)–(8) найкращим
рішенням є спільне використання елемен-
тів LUT і блоків EMB для реалізації схеми
СМПА [7, 8] . Цей підхід пов'язано із за-
стосуванням методів структурної декомпо-
зиції [14] . При цьому найчастіше вико-
ристовується метод заміни логічних умов
(ЗЛУ) x
l
∈X [14] .
Нехай X(a
m
) — множина логічних умов (ЛУ),
яка визначає переходи зі стану a
m
∈ A . Знайдімо
значення параметра G:
G = max (|x(a
1
)|, … , |x(a
M
)|) . (9)
Параметр G визначає множину додаткових
змінних P = {p
1
,…, p
G
}, що замінює множину
X . Як показали дослідження [6], для реальних
ГСА G ≤ 3 .
Метод ЗЛУ передбачає побудову таблиці
ЗЛУ, рядки якої позначено змінними p
g
∈∈ P, а
стовпці — станами a
m
∈ A . Якщо змінна p
g
= x
l
для стану a
m
∈ A, то логічна умова (ЛУ) x
l
∈ X
записується на перетині рядка p
g
і стовпця a
m
.
Ця таблиця є основою для формування СБФ:
P = P (T, X) . (10)
Використовуючи функції (10), системи (2)–
(3) перетворюються до наступного вигляду:
Start
Clock
T
LUTer A
X
YB
LUTer T LUTer B
YA
Рис.2. Однорівнева схема СМПА в базисі логічних
елементів
iSSN 2706-8145, control systems and computers, 2019, № 5 15
Синтез чотирирівневої схеми суміщеного автомата
∈Φ = Φ(T, P); (11)
Y
A
=Y
A
(T, P) . (12)
Система (10) визначає блок ЗЛУ в схемі ав-
томата . Як правило, для реалізації цього блоку
використовуються елементи LUT, а інша час-
тина схеми реалізується на блоці EMB [19] . Для
цього має виконуватися умова:
02 )(G R N R V+ × + ≤ . (13)
У цій статті ми розглядаємо випадок, коли
умова (13) порушується . При цьому нехай ви-
конується така умова:
02L R G V+ × ≤ . (14)
У цьому разі блок ЗЛУ можна реалізувати у
вигляді одного блоку EMB . Решту блоків схеми
реалізовано на елементах LUT . Це веде до мо-
делі U
2
(рис . 3) .
В автоматі U
2
блок EMB реалізує СБФ (10),
а блок LUTer1 — системи (11)–(12) . Блок
LUTer2 є аналогічним до блоку LUTerB ав-
томата U
1
.
Аналіз бібліотеки [16] показує, що для ряду
прикладів виконується умова:
G+R>S
L
. (15)
Для S
L
= 5 (Virtex-5) умова (15) виконується
для 28 відсотків тестових прикладів, для S
L
= 6
(Virtex-6) — для 12 відсотків . При цьому схема
блоку LUTer1 має кілька рівнів логіки .
Якщо виконується умова:
R>S
L
, (16)
то схеми блоків LUTer1 і LUTer2 є багаторівневи-
ми . Пропонований нами метод орієнтовано на
автомати, що задовольняють умови (14)–(16) .
Головна ідея
пропонованого методу
Нехай для деякого СМПА знайдено множи-
ну A, виконано кодування станів і здійснено
заміну ЛУ x
l
∈X додатковими змінними p
g
∈P .
Нехай для реалізації схеми використовують-
ся блоки EMB, що задовольняють (13) і (14),
і елементи LUT, що задовольняють (15)–(16) .
Знайдімо розбиття Π
A
= {A1, . . . , AK} множини
A на класи, що задовольняють умову:
R
k
+G
k
≤ S
L
( 1, )k K= . (17)
У (17) символ R
k
означає число змінних
τr∈τ, необхідних для кодування станів a
m
∈ Ak
кодами C(a
m
) . Параметр G
k
дорівнює чис-
лу змінних p
g
∈P, що визначають переходи зі
станів a
m
∈ Ak .
Параметр R
k
визначається формулою
2log (| | 1)k
kR A = + , ( 1, )k K= . (18)
Одиниця в (18) додається для обліку відно-
шення k
ma A∉ . Параметр R
k
визначає потуж-
ність множини τk ⊆ τ, де
|τ| = R
A
=R
1
+R
2
+ . . .+R
К
. (19)
Кожен клас Ak ∈ Π
A
визначає множини
P k ⊆ P, Φk ⊆ Φ, k
AY ⊆Y . Множині Pk належать
змінні р
g
∈P, що визначають переходи з a
m
∈Ak .
Множина Φk включає функції D
r
∈Φ, рівні
одиниці в кодах станів a
S
∈A, таких, що є пере-
ходи < a
m
, a
S
> і a
m
∈Ak . Множина k
AY включає
мікрооперації y
n
∈Y
A
, що формуються на пере-
ходах a
m
∈Ak .
Шукатимемо розбиття Π
A
, для якого вико-
нуються умови:
| | mini jP P →∩ ; (20)
| | mini J
T TA A →∩ ; (21)
| | mini J
T TY Y →∩ . (22)
У виразах (20)–(21) для індексів i і j вико-
нуються співвідношення: i, j∈{1,…, К}, i ≠ j .
Символ k
TA означає множину станів переходу
зі станів класу A k ⊆ A . Для розв’язання цьо-
го завдання можна використовувати метод із
робіт [20, 21] .
Ґрунтуючись на цих положеннях, ми пропо-
нуємо структурну схему СМПА U
3
. Ця схема
має чотири рівні логіки (рис . 4) .
Start Clock
T
P
EMB LUTer 1
X
LUTer 2
YA
YB
Рис. 3. Структурна схема СМПА U
2
16 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
О.О. Баркалов, Л.О. Тітаренко, Я.Є. Візор, О.В. Матвієнко
У СМПА U
3
блок EMB реалізує систему (10),
блоки LUTer 1 – LUTer K реалізують СБФ
Φk = Φk (τ k, P k); (23)
( , )k k k k
A AY Y Pτ= . (24)
Блок LUTer T формує мікрооперації y
n
∈Y
A
і
внутрішні змінні T
r
∈∈ T, що є виходами триге-
рів розподіленого регістра . Блок LUTer ∈ реалі-
зує систему (4) і СБФ
τ = τ(T) . (25)
У статті пропонується метод синтезу схеми
СМПА U
3
за вихідною ГСА Г . Метод включає
такі етапи:
1 . Формування множини станів A .
2 . Кодування станів a
m
∈A, які оптимізують
СБФ (4) .
3 . Заміна логічних умов x
l
∈X змінними p
g
∈P .
4 . Знаходження розбиття Π
A
, що задоволь-
няє умови (17), (20)–(22) .
5 . Кодування станів a
m
∈Ak кодами C(a
m
) .
6 . Формування таблиці EMB .
7 . Формування систем функцій (23)–(24) .
8 . Формування функцій блоку LUTer T .
9 . Формування функцій (4) і (25) .
10 . Реалізація схеми СМПА в заданому
базисі .
приклад синтезу автомата U
3
Нехай вираз U
i
(Γ
j
) означає, що автомат U
i
реа-
лізується за ГСА Γ
j
. Розглянемо приклад син-
тезу СМПА U
3
(Γ
1
), де ГСА Γ
1
приведено на
рис . 5 . Із рис . 5 можна знайти множни:
A = {a
1
,…, a
9
}, X = {x
1
,…, x
7
}, Y
A
= {y
1
,…, y
7
}, Y
B
=
= {y
10
,…, y
15
} . Це дає такі параметри: M = 9,
L = 7, N
A
=7, N
B
=5, N=12 .
Використовуючи (1), отримаємо R = 4 .
Це дає множини T={T
1
, … , T
4
} і Φ = {D
1
, . . .
… , D
4
} . Використовуючи алгоритм з [20],
закодуймо стани a
m
∈A (рис .6) . Як буде ви-
дно з подальшого тексту, коди з рис . 6 до-
зволяють мінімізувати число літералів у
СБФ (4) .
Аналіз ГСА ∈
1
показує, що G = 2 . Це дає мно-
жину P={p
1
, p
2
} . Виконаймо ЗЛУ так, як це по-
казано в табл . 1 .
З табл .1 маємо систему (26):
Φ1
LUTer 1
P1
Y 1
A
YB
ΦK
P Kτ1
τ
τK
Y K
A
LUTer K. . .
L U T e r T
LUTer τ
Start
Clock
EMB
X
YAT
P
Рис. 4. Структурна схема СМПА U
3
T3T4
*
00 01 11 10
00
01
11
10
a1 *
*a6
a7
a4
a3
a2
a9
a5
a8
T1T2
* ** *
Start
End
y1 y2
1 x1
x2
a2
a1
1 0
0
a6
a4 x3
a5
1 0
y2 y7
x6
1 0
y10 a3y9 y12
a8
y3
y1 y4
y8
y9 y11
y10 y11
y6
y3
y2 y5
a1
x4
a7y8 y9
y1
x5
a9y8 y11
y2 y3
x7
0
0
01
1
1
y1
y1 y4
y5 y6
Рис. 5. Початкова ГСА Г
1
Рис. 6. Коди станів автомата U
3
(Γ
1
)
Синтез чотирирівневої схеми суміщеного автомата
iSSN 2706-8145, control systems and computers, 2019, № 5 17
.
(26)
Нехай елементи LUT мають S
L
=4 входи . До
класу Ak можуть входити до
2 1S Lk
kNS −= − , ( 1, )k K= (27)
станів автомата . Це дає наступні пари:
<G
k
, NS
k
>, <0, 15>, <1, 7>, <2, 3>, <3, 1> .
Використовуючи метод [24, 25], знайдімо на-
ступне розбиття Π
A
= {A1, A2} з класами A1 ={a
1
,
a
4
, . . . , a
7
, a
9
}, A2 = {a
2
, a
3
, a
8
} . Це дає множини
P 1 = {p
1
}, P 2 = {p
1
, p
2
}, 1
AY = {y
1
, y
2
, y
3
, y
4
},
2
AY ={y
2
, y
5
, y
6
, y
7
}, 1
TA
= {a
2
, a
3
, a
4
, a
7
, a
8
, a
9
},
2
TA
= {a
5
, a
6
} . При цьому P1∩P2 = {p
1
}, 1
AY ∩ 2
AY = { y
2
},
1
TA ∩ 2
TA = ∅ . Таким чином, для отриманого
розбиття виконуються умови (17), (20) — (21) .
Закодуймо стани a
m
∈Ak кодами C(a
m
) . Із
(18)–(19) маємо R
1
=3,R
2
=2, R
A
=5 . Це дає змо-
гу отримати множини τ1={τ
1
, τ
2
, τ
3
}, τ2={τ
4
, τ
5
},
τ={τ
1
,…,τ
5
} . Один із варіантів кодування станів
показано в табл . 2 .
Таблиця блоку EMB включає стовпці T, X
(адреса комірки пам’яті), P (вміст комірки),
q – номер рядка таблиці . Таблиця будуєть-
ся тривіально [18] . Нехай серед конфігурацій
EMB є конфігурація <10, 1> . Оскільки p
2
=x
3
,
для реалізації функції р
2
не потрібно ресурсів
блоку EMB. Із формули р
1
(система (26) ви-
пливає, що на входи EMB мають надходити 10
змінних (T
1
–T
4
і x
1
, x
2
, x
4
, . . . , x
7
) . Таким чином,
для реалізації схеми ЗЛУ в цьому прикладі до-
статньо одного блока EMB .
Для формування СБФ (23)–(24) необхідно
побудувати таблиці блоків LUTer k . Ці табли-
ці включають стовпці a
m
, C(a
m
), a
s
, K(a
S
), k
hP ,
k
AhY , k
hΦ , h . Коди K(a
s
) беруться з рис . 6, коди
C(a
m
) — з табл . 2 . Для нашого прикладу LUTer 1
представлено табл . 3, а LUTer 2 — табл . 4 .
Пояснімо принцип заповнення таблиці бло-
ків LUTer k. Розгляньмо рядок 1 табл . 3, який
задає перехід a
1
в a
2
під дією x
1
=1 (це випливає
p
g
a
1
a
2
a
3
a
4
A
5
a
6
a
7
a
8
a
9
p
1 x
1
x
2
x
3
x
4
X
5
x
6
x
5
x
7
p
2 x
3
x
3
a
m
–
– – – – – – –
Таблиця 1. ЗЛУ автомата U
3
(Γ
1
)
( )
( )
1 1 1 2 3 2 4 4
5 6 6 7 5 9 7
2 3
p A x A A x A x
A A x A x A x
p x
= ∨ ∨ ∨ ∨
∨ ∨ ∨
=
a
m
τ
1
τ
2
τ3 τ
4
τ
5
a
m
τ
1
τ
2
τ3 τ
4
τ
5
a
m
τ
1
τ
2
τ3 τ
4
τ
5
a
1 001 00 a
4 010 00 a
7 101 00
a
2 000 01 a
5 011 00 a
8 000 11
a
3 000 10 a
6 100 00 a
9 110 00
Таблиця 2. Коди станів a
m
∈Ak
a
m C(a
m
) a
s
K(a
s
)
2
hP
2
AhY
2
hФ h
a
2 01
a
4 0100 p
1
y
2
y
5
D
2
1
a
6 0001 1p p
2
y
6
D
4
2
a
7 0010 1p 2p y
2
y
7
D
3
3
a
2 10
a
4 0100 p
1
y
2
y
5
D
2
4
a
6 0001 1p p
2
y
6
D
4
5
a
7 0010 1p 2p y
2
y
7
D
3
6
a
2 11 a
2 0010 1 y
5
y
6
D
3
7
Таблиця 3. LUTer1
a
m C(a
m
) a
s
K(a
s
)
1
hP
1
AhY
1
hФ h
a
1 001 a
2 0100 p
1
y
1
y
2
D
1
1
a
3 1001 1p y
3
D
1
D
4
2
a
4 010 a
2 1000 p
1
y
2
y
3
D
1
3
a
7 0101 1p y
1
D
2
D
4
4
a
5 011 a
1 0000 p
1
y
3
- 5
a
8 1010 1p y
1
y
4
D
1
D
3
6
a
6 100 a
1 0000 p
1
y
3
- 7
a
8 1010 1p y
1
y
4
D
1
D
1
8
a
7 101 a
2 1000 p
1
y
1
D
1
9
a
9 0110 1p - D
2
D
3
10
a
9 111 a
2 1000 p
1
y
1
y
4
D
1
11
a
1 0000 1p y
2
y
3
- 12
Таблиця 4. LUTer2
18 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
О.О. Баркалов, Л.О. Тітаренко, Я.Є. Візор, О.В. Матвієнко
з ГСА Г
1
) . З табл . 1 випливає, що p
1
=x
1
. Отже, у
стовпці 1
hP рядка 1 записано змінну p
1
. На цьому
переході формується набір y
1
y
2
. Цей набір за-
писано в рядку 1 стовпця 1
AhY . З табл . 2 маємо
C(a
1
)=001, з рис . 6 — K(a
2
)=1000 . Оскільки T
1
=1,
в стовпці 1
hФ рядка 1 записано D
1
. Решта рядків
таблиці заповнюються в аналогічний спосіб .
Із табл . 3 можна отримати функції (23)–(24)
з індексом 1 . Наприклад, можна отримати такі
функції:
1
2 1 2 3 1 1 2 3 1 1 2 3 1τ τ τ τ τ τ τ τ τy p p p= ∨ ∨
1
2 1 2 3 1 1 2 3 1τ τ τ τ τ τD p p= ∨
;
.
(28)
Із табл . 2 можна отримати функції (23)–(24)
з індексом 2 . Наприклад, можна отримати
функції:
2
2 4 5 1 2 4 5 1 2τ τ ( ) τ τ ( )y p p p p= ∨ ∨ ∨
2
2 4 5 1 4 5 1τ τ τ τD p p= ∨
; (29)
.
Функції блоку LUTerT формуються на основі
функцій (23)–(24) . Це є тривіальним процесом
і в нашому прикладі дає наступні рівняння:
1 1 2 1 1
1 2 1 2 2 3 3 4 4; ; ;y y y y y y y y y= = ∨ = =
2 2 2 1
5 5 6 6 7 7 1 2; ; ;y y y y y y y y= = = =
;
;
(30)
1 1 2
1 1 2 2 2; ;D D D D D= = ∨
1 2 1 2
3 3 3 4 4 4;D D D D D D= ∨ = ∨ .
(31)
Як випливає із системи (30) для реалізації
системи (3) в нашому прикладі потрібен тільки
один LUT для реалізації схеми блоку LUTerT .
Решта мікрооперацій y
n
∈Y
A
формуються бло-
ками LUTer 1 і LUTer 2 . Зменшення числа LUT
пов’язано з виконанням умови (7) .
Як випливає з (31) для реалізації системи (2)
досить 3 елементи LUT. Функція D
1
формуєть-
ся блоком LUTer 1.
Для формування системи (4) необхідно:
1 . Побудувати систему y
n
= f
n
(A
m
), де y
n
∈Y
B
,
A
m
— кон’юнкція змінних T
r
∈ T, що відповідає
коду K(a
m
) .
2 . Виконати мінімізацію системи, врахував-
ши коди стану автомата .
Система y
n
= f
n
(A
m
) будується за ГСА Г .
Для цього виконується аналіз вмісту опера-
торних вершин . У нашому прикладі маємо на-
ступну СБФ:
8 4 7 9 2y A A A T= ∨ ∨ =
9 3 5 7 4y A A A T= ∨ ∨ =
410 2 8 1y A A T T= ∨ =
11 6 8 9 3y A A A T= ∨ ∨ =
12 3 1 4.y A TT= =
;
;
;
;
(32)
Аналіз системи (32) показує, що функції y
8
,
y
9
, y
11
формуються як виходи блоку LUTerT .
Тому для реалізації системи (4) в цьому при-
кладі достатньо тільки два елементи LUT .
Система (25) формується на основі аналізу
кодів K(a
m
) і C(a
m
) . Наприклад, змінна τ
1
=1 в
кодах C(a
6
), C(a
7
) і C(a
9
) (табл .2) . Отже, функція
τ
1
визначається як A
6
∨A
7
∨A
9
. Використовуючи
коди K(a
m
) з рис . 6, отримаємо 11 3 2 4τ T T T T= ∨ . В
аналогічний спосіб можна отримати інші рів-
няння системи (25) . Зазначмо, що стан a
m
∈A
можна закодувати так, щоб мінімізувати число
літералів у системах (4) і (25) . Однак ми не роз-
глядаємо цю задачу .
Для реалізації схеми в базисі FPGA необхідно
використовувати стандартні промислові паке-
ти [9, 10] . Отримані бітові потоки (bit streams)
заносяться в елементи схеми за допомогою
програматорів . У статті не розглядається цей
етап для нашого прикладу .
висновок
Запропонований метод засновано на спільно-
му використанні блоку пам’яті EMB та елемен-
тів LUT. Метод може бути використано, якщо:
1) виконується умова (14) і 2) існує розбиття
Π
A
, що задовольняє умови (17) і
K ≤ S
L
. (33)
Якщо при цьому виконується умова
R≤ S
L
, (34)
то схема СМПА U
3
має чотири структурних рів-
ні, кожен із яких включає тільки один рівень
логіки . Якщо умова (34) порушується, тобто
справедливою є умова (16), то число рівнів у
блоці LUTer τ можна зменшити завдяки коду-
ванню станів a
m
∈A .
За виконання умов (21)–(22) частина функ-
цій y
n
∈Y
A
і D
r
∈Φ реалізується на блоках LUTer
k . При цьому число елементів LUT в блоці
LUTerT буде меншим, ніж N
1
+R .
iSSN 2706-8145, control systems and computers, 2019, № 5 19
Синтез чотирирівневої схеми суміщеного автомата
Запропонована модель веде до схем із регу-
лярними зв’язками . Так, змінні xi∈X пов’язано
тільки з блоком EMB, змінні p
g
∈P і τ
r
∈ τ —
тільки з блоками LUTer k . Це спрощує завдан-
ня розміщення та трасування [10] під час реа-
лізації схеми СМПА . Позитивною рисою U
3
є
те, що сигнали Clock і Start пов’язано тільки з
одним блоком схеми . Це дає змогу уникнути
проблем, пов’язаних із так званим перекосом
синхронізації [13] .
Аналіз бібліотеки [16] показав, що запропо-
нований метод доцільно використовувати для
68 відсотків тестових прикладів . Водночас для
76 відсотків прикладів може використовува-
тися й модель U
2
. Для 24 відсотків прикладів
виконується умова (8) і може використову-
ватися тільки модель U
3
. Наші дослідження з
використанням FPGA Virtex-6 [10] показали,
що мірою зростання параметрів R, L, N збіль-
шується виграш щодо апаратури, швидкодії та
споживаної енергії для автоматів U
3
у порів-
нянні з U
2
.
Подальші напрямки наших досліджень
пов’язано з розробкою подібних структур
СМПА з використанням: кодування наборів
мікрооперацій автомата Мілі; кодування тер-
мів систем (2)–(3) і перетворенням кодів псев-
доеквівалентних станів автомата Мура .
ЛІТЕРАТУРА
1 . Gajski D., Abdi S ., Gerstlager A ., Schirner G . Embedded System Design . New York: Springer, 2009, 416 p .
2 . Marwedel P. Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems . Berlin:
Springer, 2018, 259 p .
3 . Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В., Горина В.В. Уменьшение числа LUT элементов в
схеме совмещенного автомата . УСиМ . 2016, №3 . С . 16–22 .
4 . Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного микропро-
граммного автомата в базисе FPGA . Проблеми інформатизації та управління: Зб . наук . праць . Нац . авіаційний
ун-т . Київ, 2015 . Вип . 3(51) . С . 5–13 .
5 . Соловьев В.В. Проектирование цифровых схем на основе программируемых логических интегральных схем .
М .: Горячая линия – ТЕЛЕКОМ, 2001 . 636 с .
6 . Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA–based circuits using Hierarchical Finite State Machines .
Tallinn: TUT Press, 2012 . 240 p .
7 . Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Структурная редукция в совмещенных автома-
тах . Проблеми інформатизації та управління: Зб . наук . праць . Нац . авіаційний ун-т . Київ, 2017 Вип . 1-2 (57-58) .
С . 14–19 .
8 . Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Кодирование выходных переменных в со-
вмещенном автомате . Комп’ютернi засоби, мережi та системи . К .: Ін-т кібернетики ім . В .М .Глушкова НАН
України, 2018 . №17 . С . 73–80 .
9 . www.altera.com.
10 . www.xilinx.com
11 . Baranov S. Logic Synthesis for Control Automata . Dordrecht: Kluwer Academic Publishers, 1994 . 312 p .
12 . Grout I . Digital Systems Design with FPGAs and CPLDs . Amsterdam: Elseveit, 2008 . 784 p .
13 . C. Maxfield C. The Design Warrior’s Guide to FPGAs . – Orlando: Academic Press, 2004 . 542 p .
14 . Rawski, M ., Tomaszewicz P., Borowski G ., τuba T. (2011) . Logic Synthesis Method of Digital Circuits Designed for
Implementation with Embedded Memory Blocks on FPGAs, Design of Digital Systems and Dev44ises. LNEE 70, Springer,
Berlin . P . 121–144 .
15 . Wisniewski R., Gomes L., Costa A. Dynamic Partial Reconfiguration of Concurrent Control Systems Implemented in
FPGA Devices .-IEEE Transactions on industrial informatics . 2017, V . 13, № 4 . pp . 1734–1741 .
16 . Yang S. Logic Synthesis and optimization benchmarks user guide . Microelectronics Center of North Carolina . 1991, 43 p .
17 . Garcia–Vargas L., Senhadji–Navarro R .M., Civit–Balcells A ., Guerra–Gutierrezz P. (2007) . ROM–Based Finite
State Machine Implementation in Low Cost FPGAs, IEEE International Simposium on Industrial Electronics, Vigo,
pp . 2342–2347 .
20 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
О.О. Баркалов, Л.О. Тітаренко, Я.Є. Візор, О.В. Матвієнко
18 . Barkalo A., Titarenko L. Logic Synthesis for FSM – based Control Units . Berlin: Springer, 2009 . 233 p .
19 . Das N ., Ptija P. FPGA Implementation of Reconfigurable FSMs with Input Multiplexing Architecture using
Hungarian Method .-International Journal of Reconfigurable Computing . 2018, 14 (5), pp . 1–15
20 . Barkalov A, Titarenko L., Mielcatek K . Twofold state assignment for FPGA – based Mealy FSMs . In: Proceedings of
International Conference MOCAST-18 . Thessaloniki, Greece . New York, IEEE Explore, 2018, pp . 1–4 .
21 . Barkalov A, Titarenko L., Mielcatek K . Hardware Reduction for LUT-based Mealy FSMs . Int . J . of Applied
Mathematics and Computer Science . 2018, 28 (3), pp . 28–41 .
Надійшла 12 .09 .2019
REFERENCES
1 . Gajski, D ., Abdi, S ., Gerstlager, A ., Schirner, G ., 2009 . Embedded System Design, New York: Springer, 416 p .
2 . Marwedel, P ., 2018 . Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, Berlin:
Springer, 259 p .
3 . Barkalov, A .A ., Titarenko, L .A ., Vizor, Ya .Ye ., Matvienko, A .V ., Gorina, V .V ., 2016 . “Synthesis of Combined Finite
State Machine with FPGAs”, Upr . sist . mas ., 3, pp . 16–22 . (In Russian) .
4 . Barkalov, A .A ., Titarenko, L .A ., Vizor, Ya .Ye ., Matviyenko, A .V ., 2015 . “Realizatsiya skhemy sovmeshchennogo mik-
roprogrammnogo avtomata v bazise FPGA”, Problemy informatyzatsiyi ta upravlinnya: Zb . nauk . prats . Natsionalnyy avi-
atsiynyy universytet, Kyiv, 3 (51), pp . 5–13 . (In Russian) .
5 . Solovyev, V .V ., 2001 . Proyektirovaniye tsifrovykh skhem na osnove programmiruyemykh logicheskikh integralnykh
skhem . M .: Goryachaya liniya – TELEKOM, 636 p . (In Russian) .
6 . Skliarova, I ., Sklyarov, V ., Sudnitson, A ., 2012 . Design of FPGA–based circuits using Hierarchical Finite State
Machines, Tallinn: TUT Press, 240 p .
7 . Barkalov, A .A ., Titarenko, L .A ., Vizor, Ya .Ye ., Matviyenko, A .V ., 2017 . “Strukturnaya reduktsiya v sovmeshchen-
nykh avtomatakh”, Problemy informatyzatsiyi ta upravlinnya: Zb . nauk . prats . Natsionalnyy aviatsiynyy universytet, Kyiv,
1 (57-58) . pp . 12–19 (In Russian) .
8 . Barkalov, A .A ., Titarenko, L .A ., Vizor, Ya .Ye ., Matviyenko, A .V ., 2018 . “Kodirovaniye vykhodnykh peremennykh
v sovmeshchennom avtomate”, Komputerni zasoby, merezhi ta systemy, K .: In-t kibernetyky im . V .M .Hlushkova NAN
Ukrayiny, 17, pp . 73–80 .
9 . Intel FPGas and Programmable Device, [online] . Available at: <www .altera .com> [Accessed 05 Jan . 2019] .
10 . Xilinx, [online] . Available at: <www .xilinx .com> [Accessed 10 Feb . 2019] .
11 . Baranov, S ., 1994 . Logic Synthesis for Control Automata, Dordrecht: Kluwer Academic Publishers, 312 p .
12 . Grout, I ., 2008 . Digital Systems Design with FPGAs and CPLDs, Amsterdam: Elseveit, 784 p .
13 . Maxfield, C ., 2004 . The Design Warrior’s Guide to FPGAs, Orlando: Academic Press, 542 p .
14 . Rawski, M ., Tomaszewicz, P ., Borowski, G . and ∈uba, T ., 2011 . “Logic Synthesis Method of Digital Circuits
Designed for Implementation with Embedded Memory Blocks on FPGAs, Design of Digital Systems and Devises”, LNEE
70, Springer, Berlin, pp . 121–144 .
15 . Wisniewski, R ., Gomes, L ., Costa, A ., 2017 . “Dynamic Partial Reconfiguration of Concurrent Control Systems
Implemented in FPGA Devices”, IEEE Transactions on industrial informatics, 13 (4), pp . 1734–1741 .
16 . Yang, S ., 1991 . Logic Synthesis and optimization benchmarks user guide, Microelectronics Center of North
Carolina, 43 p .
17 . Garcia–Vargas, L ., Senhadji–Navarro, R ., M . Civit–Balcells, A . and Guerra–Gutierrezz, P ., 2007 . “ROM–Based
Finite State Machine Implementation in Low Cost FPGAs”, IEEE International Simposium on Industrial Electronics,
Vigo ., pp . 2342–2347 .
18 . Barkalov, A ., Titarenko, L ., 2009 . Logic Synthesis for FSM – based Control Units, Berlin: Springer, 233 p .
19 . Das, N ., Ptija, P ., 2018 . “FPGA Implementation of Reconfigurable FSMs with Input Multiplexing Architecture
using Hungarian Method”, International Journal of Reconfigurable Computing, 14 (5) . pp . 1–15 .
20 . Barkalov, A ., Titarenko, L ., Mielcatek, K ., 2018 . “Twofold state assignment for FPGA – based Mealy FSMs” . In:
Proceedings of International Conference MOCAST-18, Thessaloniki, Greece, New York, IEEE Explore, pp . 1–4 .
21 . Barkalov, A ., Titarenko, L ., Mielcatek, K ., 2018 . “Hardware Reduction for LUT – based Mealy FSMs”, International
Journal of Applied Mathematics and Computer Science, 28 (3), pp . 28–41 .
Received 12 .09 .2019
iSSN 2706-8145, control systems and computers, 2019, № 5 21
Синтез чотирирівневої схеми суміщеного автомата
A.A. Barkalov, Doctor in Techn . Sciences, Professor, University of Zielona Gora (Poland),
Podgorna str ., 50, Zielona Gora, 65246, Poland,
a .barkalov@iie .uz .zgora .pl
L.A. Titarenko, Doctor of Technical Sciences, Professor of the University of Zelenogorsk (Poland),
Podgorna str ., 50, Zielona Gora, 65246, Poland
L .Titarenko@iie .uz .zgora .pl, D_ts@nure .ua
Y.E. Visor, Ph .D ., Senior Researcher, Institute of Cybernetics of NAS of Ukraine,
03187, Kiev, Glushkov Avenue, 40, Ukraine,
yaviz@ukr .net
O.V. Matvienko, Researcher Associate, Institute of Cybernetics of NAS of Ukraine,
03187, Kiev, Glushkov Avenue, 40, Ukraine,
matv@online .ua
SYNTHESIS OF A FOUR-LEVEL SCHEMA OF A COMBINED AUTOMATON
Introduction . A method is proposed targeting hardware decrease in the circuit of combined automation, implemented
with LUTs and EMBs . The method is based on replacement of logical conditions and partition of the set of states by
classes . Each class corresponds to a single block of the circuit . This approach leads to circuits with regular structure and
four levels of logic .
Purpose . The proposed model leads to schemes with regular connections . This simplifies the placement and tracing
tasks when implementing the SMPA scheme . A positive feature of the proposed model is the fact that the Clock and Start
signals are associated with only one block of the circuit . This avoids the problems associated with the so-called distortion
synchronization .
Results . Analysis of a special library showed that the proposed method is advisable to use for 68% of test cases . Moreover,
for 76% of the examples, the original model can be used . For 24% of the examples, if the corresponding condition is met,
only the proposed model can be used . Our studies using Virtex-6 FPGAs showed that as the parameters R, L, N increase,
the gain in equipment, speed and energy consumption for the proposed machines compared to the original ones is increased
An example is shown for using of proposed method . The conditions of its application are shown .
Conclusion . Further areas of our research are related to the development of similar SMPA structures using: coding of sets
of microoperations of the Mealy automaton; the coding of the terms of systems; and the conversion of codes of pseudo-
equivalent states of the Moore automaton .
Keywords: combined automaton, synthesis, LUT, EMB, partition, FPGA.
22 iSSN 2706-8145, системи керування та комп'ютери, 2019, № 5
О.О. Баркалов, Л.О. Тітаренко, Я.Є. Візор, О.В. Матвієнко
А.А. Баркалов, д-р техн . наук, профессор, Университет Зеленогурский (Польша),
ул . Подгорная, 50, 65-246, Зеленая Гура (Польша),
a .barkalov@iie .uz .zgora .pl
Л.А. Титаренко, д-р техн . наук, профессор, Университет Зеленогурский (Польша),
ул . Подгорная, 50, 65-246, Зеленая Гура (Польша),
L .Titarenko@iie .uz .zgora .pl, D_ts@nure .ua
Я.Е. Визор, канд . техн . наук, ст . научн . сотрудник, Институт кибернетики им . В .М . Глушкова
НАН Украины, 03187, г . Киев, пр . Акад . Глушкова, 40, Украина,
yaviz@ukr .net
А.В. Матвиенко, научн . сотрудник, Институт кибернетики им . В .М . Глушкова
НАН Украины, 03187, г . Киев, пр . Акад . Глушкова, 40, Украина,
matv@online .ua
СИНТЕЗ ЧЕТЫРЕХУРОВНЕВОЙ СХЕМЫ СОВМЕЩЕННОГО АВТОМАТА
Вступление. Предложен метод уменьшения аппаратурных затрат в схеме совмещенного автомата, реализуемой
в совместном базисе элементов LUT и блоков памяти EMB . Метод основан на замене логических условий и раз-
биении множества логических состояний на классы . Каждый класс соответствует отдельному блоку схемы . Такой
подход приводит к схемам с регулярной структурой и четырьмя логическими уровнями .
Цель . Предложенная модель приводит к схемам с регулярными связями . Это упрощает задачи размещения и
трассировки при реализации схемы СМПА . Положительной чертой предложенной модели является тот факт, что
сигналы Clock и Start связаны только с одним блоком схемы . Это позволяет избежать проблем, связанных с так
называемым перекосом синхронизации .
Результаты . Анализ специальной библиотеки показал, что предложенный метод целесообразно использовать
для 68 процентов тестовых примеров . При этом для 76 процентов примеров может быть использована исходная
модель . Для 24 процентов примеров, при выполнении соответствующего условия, может быть использована толь-
ко предложенная модель . Наши исследования с использованием FPGA Virtex-6 показали, что по мере роста пара-
метров R, L, N увеличивается выигрыш в быстродействии и потребляемой энергии используемой аппаратуры с
применением предложенных автоматов в сравнении с исходными . Приведен пример использования предложен-
ного метода и показаны условия его применения
Выводы . Дальнейшие направления наших исследований связаны с разработкой подобных структур СМПА
с использованием: кодирования наборов микроопераций автомата Мили; кодирования термов систем и преоб-
разованием кодов псевдоэквивалентных состояний автомата Мура .
Ключевые слова: совмещенный автомат, синтез, LUT, EMB, разбиение, FPGA .
|