Двойное кодирование состояний в совмещенном автомате

Предложен метод уменьшения аппаратурных затрат в схеме совмещенного микропрограммного автомата, реализуемого в базисе FPGA. Метод основан на разбиении множества состояний на классы, каждый из которых соответствует отдельному блоку схемы. Такой подход приводит к схемам с регулярной структурой и тремя...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автори:	Баркалов, А.А., Титаренко, Л.А., Визор, Я.Е., Матвиенко, А.В., Сабурова, С.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Назва видання:	Комп’ютерні засоби, мережі та системи
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/168470
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Двойное кодирование состояний в совмещенном автомате / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, С.А. Сабурова // Комп’ютерні засоби, мережі та системи. — 2019. — № 18. — С. 11-17. — Бібліогр.: 22 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-168470
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1684702025-02-23T18:32:35Z Двойное кодирование состояний в совмещенном автомате Two fold state assignment for combined automation Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Сабурова, С.А. Предложен метод уменьшения аппаратурных затрат в схеме совмещенного микропрограммного автомата, реализуемого в базисе FPGA. Метод основан на разбиении множества состояний на классы, каждый из которых соответствует отдельному блоку схемы. Такой подход приводит к схемам с регулярной структурой и тремя логическими уровнями. Приведен пример синтеза схемы автомата с использованием предложенного метода. Показаны условия его применения. У статті запропоновано метод зменшення апаратурних витрат при розробці пристроїв управління цифрових систем. Зниження витрат апаратури дозволяє підвищити якість цифрової системи за рахунок зменшення площі кристала НВІС, зниження споживання енергії та підвищення швидкодії. Метод заснований на розбитті множини станів автомата на класи, кожен з яких відповідає окремому блоку схеми. Такий підхід призводить до схем з регулярною структурою і трьома логічними рівнями. У статті наведено приклад синтезу схеми автомата з використанням запропонованого методу. Показані умови його застосування. The article proposes a method of reducing hardware costs in the development of control devices for digital systems. Reducing hardware costs can improve the quality of a digital system by reducing the size of the VLSI chip, reducing energy consumption and increasing speed. The method is based on splitting the set of states of an automaton into classes, each of which corresponds to a separate block of the circuit. This approach leads to circuit with a regular structure having three levels of logic. The article provides an example of the synthesis of an automaton circuit using the proposed method. The conditions of its application are shown. 2019 Article Двойное кодирование состояний в совмещенном автомате / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, С.А. Сабурова // Комп’ютерні засоби, мережі та системи. — 2019. — № 18. — С. 11-17. — Бібліогр.: 22 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/168470 ru Комп’ютерні засоби, мережі та системи application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Предложен метод уменьшения аппаратурных затрат в схеме совмещенного микропрограммного автомата, реализуемого в базисе FPGA. Метод основан на разбиении множества состояний на классы, каждый из которых соответствует отдельному блоку схемы. Такой подход приводит к схемам с регулярной структурой и тремя логическими уровнями. Приведен пример синтеза схемы автомата с использованием предложенного метода. Показаны условия его применения.
format	Article
author	Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Сабурова, С.А.
spellingShingle	Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Сабурова, С.А. Двойное кодирование состояний в совмещенном автомате Комп’ютерні засоби, мережі та системи
author_facet	Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Сабурова, С.А.
author_sort	Баркалов, А.А.
title	Двойное кодирование состояний в совмещенном автомате
title_short	Двойное кодирование состояний в совмещенном автомате
title_full	Двойное кодирование состояний в совмещенном автомате
title_fullStr	Двойное кодирование состояний в совмещенном автомате
title_full_unstemmed	Двойное кодирование состояний в совмещенном автомате
title_sort	двойное кодирование состояний в совмещенном автомате
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
url	https://nasplib.isofts.kiev.ua/handle/123456789/168470
citation_txt	Двойное кодирование состояний в совмещенном автомате / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, С.А. Сабурова // Комп’ютерні засоби, мережі та системи. — 2019. — № 18. — С. 11-17. — Бібліогр.: 22 назв. — рос.
series	Комп’ютерні засоби, мережі та системи
work_keys_str_mv	AT barkalovaa dvojnoekodirovaniesostoânijvsovmeŝennomavtomate AT titarenkola dvojnoekodirovaniesostoânijvsovmeŝennomavtomate AT vizorâe dvojnoekodirovaniesostoânijvsovmeŝennomavtomate AT matvienkoav dvojnoekodirovaniesostoânijvsovmeŝennomavtomate AT saburovasa dvojnoekodirovaniesostoânijvsovmeŝennomavtomate AT barkalovaa twofoldstateassignmentforcombinedautomation AT titarenkola twofoldstateassignmentforcombinedautomation AT vizorâe twofoldstateassignmentforcombinedautomation AT matvienkoav twofoldstateassignmentforcombinedautomation AT saburovasa twofoldstateassignmentforcombinedautomation
first_indexed	2025-11-24T10:33:11Z
last_indexed	2025-11-24T10:33:11Z
_version_	1849667502529839104
fulltext	Computer means, networks and systems. 2019, N 18 11 Двойное кодирование состояний в совмещенном автомате А.А. Баркалов1, Л.А. Титаренко2, Я.Е. Визор3, А.В. Матвиенко4, С.А. Сабурова5 1 – Institute of Informatics and Electronics. University of Zielona Gora, ul. Podgorna, 50, Zielona Gora, 65-246, POLAND, A.Barkalov@iie.uz.zgora.pl 2 – Institute of Informatics and Electronics. University of Zielona Gora, ul. Podgorna, 50, Zielona Gora, 65-246, POLAND; ХНУРЭ, 61166, г. Харьков, проспект Науки, 14, L.Titarenko@iie.uz.zgora.pl, 3, 4 – Институт кибернетики имени В.М. Глушкова НАН Украины, 03187, г. Киев, проспект Академика Глушкова, 40, yaviz@ukr.net, matv@online.ua, 5 – ХНУРЭ, 61166, г. Харьков, проспект Науки, 14, sabsvet@gmail.com A.A. Barkalov, L.A. Titarenko, Y.E. Vizor, A.V. Matvienko, S.A. Saburova TWO FOLD STATE ASSIGNMENT FOR COMBINED AUTOMATION Abstract. The article proposes a method of reducing hardware costs in the development of control devices for digital systems. Reducing hardware costs can improve the quality of a digital system by reducing the size of the VLSI chip, reducing energy consumption and increasing speed. The methods for solving this problem largely depend on the model representing the control device and the characteristics of the elemental basis in which the circuit is implemented. The proposed method uses the model of combined microprogrammed automaton (CMPA) implemented in the FPGA (field-programmable logic arrays) basis. To set the behavior of the automaton, the language of the graph diagrams of the algorithm is used. A characteristic feature of the SMPA model is the presence of two types of output signals. The output signals of the Mealy machine exist during transitions between the states of the machine. The outputs of the Moore automaton are determined only by the states of the automaton. The main elements of FPGA that are used to implement CMPA are elements of the table type LUT (look-up table), programmable triggers and built-in memory blocks EMB (embedded memory blocks). EMBs are heavily used to implement the operational devices of digital systems. The proposed method allows to use only LUT elements in the design of the control device. The method is based on splitting the set of states of an automaton into classes, each of which corresponds to a separate block of the circuit. This approach leads to circuit with a regular structure having three levels of logic. The article provides an example of the synthesis of an automaton circuit using the proposed method. The conditions of its application are shown. Key words: combined microprogrammed automaton, synthesis, FPGA, LUT, partitioning. Аннотация. Предложен метод уменьшения аппаратурных затрат в схеме совмещенного микропрограммного авто-  А.А. БАРКАЛОВ, Л.А. ТИТАРЕНКО, Я.Е. ВИЗОР, А.В. МАТВИЕНКО, С.А. САБУРОВА, 2019 мата, реализуемого в базисе FPGA. Метод основан на разбиении множества состояний на классы, каждый из которых соответствует отдельному блоку схемы. Такой подход приводит к схемам с регулярной структурой и тремя логическими уровнями. Приведен пример синтеза схемы автомата с использованием предложенного метода. Показаны условия его применения. Ключевые слова: совмещенный микропрограммный автомат, синтез, FPGA, LUT, разбиение. Анотація. У статті запропоновано метод зменшення апаратурних витрат при розробці пристроїв управління цифрових систем. Зниження витрат апаратури дозволяє підвищити якість цифрової системи за рахунок зменшення площі кристала НВІС, зниження споживання енергії та підвищення швидкодії. Методи вирішення цього завдання в значній мірі залежать від моделі, що представляє пристрій управління, і характеристик елементного базису, в якому реалізується схема. Запропонований метод використовує модель суміщеного мікропрограмного автомата (СМПА), що реалізується в базисі FPGA (field-programmable logic arrays). Для завдання поведінки автомата вико- ристовується мова граф-схем алгоритму. Характерною рисою моделі СМПА є наявність двох типів вихідних сигналів. Вихідні сигнали автомата Мілі існують при переходах між станами автомата. Вихідні сигнали автомата Мура визначаються тільки станами автомата. Основними елементами FPGA, які використовуються для реалізації СМПА, є елементи табличного типу LUT (look- up table), програмовані тригери і вбудовані блоки пам'яті EMB (embedded memory blocks). Блоки EMB інтенсивно використовуються для реалізації операційних пристроїв цифрових систем. Пропонований метод дозволяє застосовувати при проектуванні пристрою управління тільки елементи LUT. Метод заснований на розбитті множини станів автомата на класи, кожен з яких відповідає окремому блоку схеми. Такий підхід призводить до схем з регулярною структурою і трьома логічними рівнями. У статті наведено приклад синтезу схеми автомата з використанням запропонованого методу. Показані умови його застосування. Ключові слова: суміщений мікропрограмний автомат, синтез, FPGA, LUT, розбиття. mailto:A.Barkalov@iie.uz.zgora.pl mailto:A.Barkalov@iie.uz.zgora.pl mailto:yaviz@ukr.net mailto:matv@online.ua mailto:sabsvet@gmail.com А.А. БАРКАЛОВ, Л.А. ТИТАРЕНКО, Я.Е. ВИЗОР, А.В. МАТВИЕНКО, С.А. САБУРОВА Комп'ютерні засоби, мережі та системи. 2019, № 18 12 Введение. Одним из главных блоков цифровых систем является устройство управ- ления (УУ) [1, 2]. Для повышения качества цифровых систем (уменьшение площади кри- сталла, снижение потребления энергии, повы- шение быстродействия) необходимо уменьшать площадь кристалла СБИС, занимаемую схемой УУ [3, 4]. Методы решения этой задачи в значительной степени зависят от модели, представляющей УУ, и характеристик элемент- ного базиса, в котором реализуется схема УУ [5]. В настоящее время модели микропро- граммных автоматов (МПА) широко исполь- зуются для задания поведения УУ [6, 7]. К одной из таких моделей относится совмещенный МПА (СМПА), который имеет два типа выходных сигналов: выходные сигналы автомата Мили и выходные сигналы автомата Мура. Наиболее популярным базисом для реа- лизации цифровых систем являются микросхемы FPGA (field-programmable logic arrays) [8]. Основными элементами FPGA являются эле- менты табличного типа LUT (look-up table), программируемые триггера и программируемые межсоединения [5]. В данной работе мы предлагаем метод уменьшения числа LUT элементов и количества их уровней в схеме СМПА. Для задания по- ведения УУ используется язык граф-схем алгоритма [1]. Реализация СМПА в базисе FPGA. Для реализации схемы СМПА необходимо получить три системы булевых функций [6, 7]: YM 1= YM 1 (T, X); (1) YM 2= YM 2 (T); (2) Φ = Φ(T, X). (3) В системах (1) – (3) используются сле- дующие обозначения: YM1  Y – множество микроопераций (МО) автомата Мили, \|YM 1\|=N1; YM 2  Y – множество МО автомата Мура, \|YM 2\| = N2; Φ – множество функций возбуждения памяти МПА; T – множество внутренних переменных, используемых для кодирования состояний amA; A={a1,…, aM} – множество состояний. При этом YM1UYM2 = Y, где Y – множество МО СМПА (Y = {y1,…, yN}) и выполняется условие: YM 1∩ Y M 2 = Ø. Множества Φ и T имеют одинаковое количество элементов определяющееся соотно- шением 2 logR M    . (4) При этом Φ = {D1,..., DR} и T={T1,...,TR}. Состояния amA кодируются кодами K(am), хранящиеся во внутренней памяти СМПА. Эта память представлена регистром RG. Как правило, RG имеет информационные входы типа D [3]. Чтобы найти системы (1) – (3), необходимо построить прямую структурную таблицу (ПСТ) совмещенного МПА. Эта таблица формируется на основе исходной ГСА Γ, отмеченной состояниями МПА Мура [6, 7]. Будем рассматривать проблему реализации схемы СМПА в базисе LUT элементов. Пусть LUTer означает блок, состоящий из элементов LUT, триггеров и программируемых межсо- единений, показанных на рис. 1. Start ClockLUT S1 SL . . . . TT C D R fC fR y0 fL MX РИС. 1. Логический элемент блока LUTer Элемент LUT реализует произвольную логическую функцию fC, которая зависит от не более, чем SL аргументов. Выход fC подается на вход D двухтактного триггера. Импульс Start используется для операции fR := 0. Импульс Clock инициирует операцию fR := fC. Выход логического элемента может быть либо комбинационным (fL = fC), либо нет (fL = fR). Для выбора типа выхода используетс мульти- плексор MX и сигнал y0. Поставим в соответствие системе (1) блок LUTer 1, системе (2) – блок LUTer 2 и системе (3) – блок LUTer T. Это приводит к СМПА U1 (рис. 2). В U1 регистр RG распределен между триггерами блока LUTer T. Поэтому блок LUTer T имеет входы синхронизации (Clock) и обнуления (Start). ДВОЙНОЕ КОДИРОВАНИЕ СОСТОЯНИЙ В СОВМЕЩЕННОМ АВТОМАТЕ Computer means, networks and systems. 2019, N 18 13 Start Clock T LUTer 1 X YM2 LUTer T LUTer 2 YM1 РИС. 2. Структурная схема СМПА U1 Оптимизация схемы СМПА. При синтезе СМПА в базисе FPGA возникает проблема, связанная с ограниченным числом SL входов LUT [9]. Обычно величина SL не превышает 6 [10, 11]. Пусть L(fi) – число аргументов в функции fi  Φ U Y. Если выполняется условие L(fi) ≤ SL , (5) то для реализации схемы соответствующей функции fi , достаточно одного элемента LUT. Если условие (5) выполняется для всех функций ΦUY, схема U1 содержит N+R элементов LUT и только один логический уровень. Такая схема имеет минимальное число межсоединений, потребляемую мощность и время задержки (максимальное быстродействие). Однако анализ библиотеки [12] показывает, что функции (1) и (3) могут зависеть от L+R≈30 аргументов и условие (5) может выполняться только для ограниченного числа функций fi  ΦUY. Поэтому соответствующие функции представляются в виде композиции подфункций, для каждой из которых выполняется условие (5). Для этой цели используются методы функ- циональной декомпозиции [13, 14]. Их приме нение приводит к многоуровневым схемам, имеющим гораздо худшие характеристики по сравнению с одноуровневыми схемами МПА [15]. Если условие (5) нарушается, то необходимо оптимизировать схему СМПА. Для этого могут быть использованы методы [5]. 1. Оптимальное кодирование состояний. Под оптимальным понимается кодирование, умень- шающее число аргументов в функциях (1) – (3). Одним из лучших методов кодирования счи- тается метод JEDI [16]. Однако для сложных автоматов (M >50) ни один из методов не гаран- тирует выполнения условия (5) [17]. 2. Использование внутренних блоков памяти. Современные FPGA имеют в своем составе блоки памяти EMB (embedded memory blocks). Один блок EMB может заменить сотни элементов LUT [18]. Однако эти блоки широко используются для реализации операционных блоков цифровых систем [4]. Поэтому вполне вероятна ситуация, когда для реализации схемы УУ остаются только элементы LUT. 3. Структурная декомпозиция. Этот подход связан с увеличением числа структурных уровней схемы МПА [17]. Каждый уровень характеризуется собственными выходными переменными и выходными функциями. При этом выходные функции уровня i служат входными переменными уровня i+1. Известны следующие методы структурной декомпозиции: кодирование логических условий, кодирование наборов микроопераций, преобразование объек- тов [5]. В работах [20, 21] предлагается метод структурной декомпозиции, ведущий к схемам МПА с тремя структурными уровнями. В настоящей работе предлагается адаптировать этот подход к особенностям совмещенного МПА. Основная идея предлагаемого метода. Пусть задана ГСА Γ, представляющая поведение СМПА и отмеченная состояниями amA. Найдем разбиение A = {A1,…, AK} множества A на классы, для каждого из которых выполняется условие Rk+Lk ≤ S (k  {1,...,k}). (6) В условии (6) символ Rk означает число переменных, необходимых для кодирования состояний amAk, Lk – число входных пере- менных xiX, определяющих переходы из этих состояний и образующих множество Xk X. Параметр Rk определяется формулой 2log ( 1)k kR A     (k  {1,...,K}). (7) Единица в (7) прибавляется для кода, соответствующего отношению .Aam  Исполь- зуем для кодирования состояний amAk переменные из множества τk  τ, где \| τ \| = RA = R1 + R2 + …+ RK. (8) Очевидно, каждый класс k AA  опреде- ляет множества kX X , 11 M k M YY  , 22 M k M YY  и . k Смысл этих множеств ясен из по- следующего материала. А.А. БАРКАЛОВ, Л.А. ТИТАРЕНКО, Я.Е. ВИЗОР, А.В. МАТВИЕНКО, С.А. САБУРОВА Комп'ютерні засоби, мережі та системи. 2019, № 18 14 Закодируем состояния amA кодами K(am) разрядности R. Теперь каждое состояние имеет два кода. Код K(am) определяет amA, а код C(am) – amAk. Основываясь на таком подходе, мы предлагаем СМПА U2 (рис. 3). Φ 1 LUTer 1 YM 1 X 1 Y 1 M1 YM 2 Φ K X K 1  K Y K M1 LUTer K. . . L U T e r T LUTer  T Start Clock РИС. 3. Структурная схема СМПА U2 В автомате U2 блок LUTer k формирует функции τ ,( )k k k kx  ; (9) 1( ),k k kk MY Y x . (10) Блок LUTer T формирует микрооперации ynYM1 и внутренние переменные TrT. Сигналы Start и Clock управляют распределенным регистром RG. Для формирования функций используются следующие уравнения: K rrrr DDDD  ....21 , (r{1,…,R}); (11) K nnnn yyyy  ....21 (yn YM1). (12) Блок LUTer τ формирует систему (2) и переменные τr  τ: τr = τr(T), (r {1,…, RA}). (13) В силу справедливости (6) только один LUT для реализации любой функции блоками LUTer 1 – LUTer K требуется только один LUT. Поэтому число LUT NLk в блоке LUTer k определяется формулой 1 k k k MNL Y   , (k {1,…, K}). Следовательно, для уменьшения числа LUT необходимо находить такое разбиение A, для которого: min ji  ; (14) min11  j M i M YY  . (15) Для параметров i, j из (14), (15) выполняется следующее: i, j {1,…, K}, i ≠ j. Метод поиска разбиения A, удов- летворяющего (14), (15), предложен в [21], поэтому мы его не будем рассматривать. Предлагаемый метод синтеза схемы СМПА U2 включает следующие этапы: - формирование множества состояний по исходной ГСА; - кодирование состояний amA, оптимизи- рующее систему (2); - нахождение разбиения A удовлетво- ряющего (14), (15); - кодирование состояний amAk; - формирование систем функций (9), (10); - формирование систем функций (11), (12); - формирование систем функций (2) и (13); - реализацию схемы СМПА в заданном базисе. Пример синтеза автомата U2. Пусть Ui (Γj) означает, что автомат Ui реализуется по ГСА Γj. Рассмотрим пример синтеза СМПА U2(Γ1). На рис. 4 показана ГСА Γ1. Пусть S = 4. Start End y1 y4 y6 y8 1 x1 a5 x2 a2 a1 1 0 0 a8 a7 a4 y9 y10 x3 a6 1 0 y2 y5 x1 1 0 y8 a3y9 y10 a9 y1 y2 y7 y1 y2 y7 y8 y10 y8 y12 y11 y12 y9 y10 y11 y2 y3 y5 y3 y6 y1 y2 y3 y6 РИС. 4. Исходная ГСА Γ1 ДВОЙНОЕ КОДИРОВАНИЕ СОСТОЯНИЙ В СОВМЕЩЕННОМ АВТОМАТЕ Computer means, networks and systems. 2019, N 18 15 Анализ ГСА Γ1 показывает, что M = 9, L = 3, N1 = 7, N2 = 5, N = 12. Из (4), получим R = 4, что определяет множества T = {T1,...,T4} и Φ = {D1,..., D4}. Закодируем состояния amA кодами K(am) так, чтобы уменьшить число литералов в сис- теме (2). Для этих целей используем алгоритм из работы [19]. Отметим, что такое кодирование может нарушить условие (14). Однако алгоритм [19] приводит к минимизации числа элементов LUT и их межсоединений в схеме блока LUTer τ. Один из вариантов кодирования показан на рис. 5. T3T4 * 00 01 11 10 00 01 11 10 a1 * a7 a4 a2 a8 a3 a6 a5 a9 T1T2 * * * РИС. 5. Коды состояний автомата U2(Γ1) Используя ГСА Γ1 и коды состояний (рис. 5), можно получить следующую систему функций: 8 2 4 5 6 2y A A A A T     , 9 3 8 9 1y A A A T    , 10 3 4 8 9 1 3 4y A ТA A A TT      , (16) 11 7 9 2 3y A A Т T   , 12 6 7 3 4y A A T T   . В функциях (16) символ Am означает конъюнкцию переменных TrT, соответствую- щая коду K(am) состояния amA. Если блок LUTer k имеет \| x k\| = Lk , то в класс Ak можно поместить до 12   k LS k NS , (k{1,…, K}) состояний amA. При S = 4 имеем следующие пары: <Lk, NSk>: <0, 15>, <1, 7>, <2, 3>, <3, 1>. Используя подход [21], найдем следующее разбиение: A = {A1, A2}, где A1={a1, a4, a5, a6, a7, a8, a9} и A2={ a2, a3}. При этом X 1 = {x1}, X 2 ={x2, x3}, то есть выполняются условия (6) и X 1 ∩ X 2 = Ø. Используя (7), (8), получим R1 = 3, R2 = 2, R3 = 5. Это дает множества τ1={τ1, τ2, τ3} τ2={τ4, τ5} и τ = {τ1,…,τ5}. Закодируем состояния авто- мата так, как приведено в табл. 1. Для формирования систем (9), (10) необ- ходимо построить прямые структурные таб- лицы для каждого класса AkA. Для нашего примера это табл. 2 и 3. ТАБЛИЦА 1. КОДЫ СОСТОЯНИЙ AMAK am τ1τ2τ3 τ4τ5 am τ1τ2τ3 τ4τ5 am τ1τ2τ3 τ4τ5 a1 0 0 1 0 0 a4 0 1 0 0 0 a7 1 0 1 0 0 a2 0 0 0 0 1 a5 0 1 1 0 0 a8 1 1 0 0 0 a3 0 0 0 1 1 a6 1 0 0 0 0 a9 1 1 1 0 0 В табл. 2 и 3 используются коды C(am) из табл. 1, коды K(as) – из рис. 5. При этом учтен факт, что состояния a6, a7 – псевдоэкви- валентны [5], как и состояния a6, a7A2. Из табл. 2 имеем множества X 1={x1}, Y 1={y1, y2, y3, y4, y6, y7} и Φ1 = Φ. Из табл. 3 имеем множества X 2 = {x2, x3}, Y2 = {y2, y3, y5, y6}, Φ2 = {D2, D3, D4}. Таким образом, \| X 1 ∩ X 2\| = 0, \| Y 1 ∩ Y2\| = 3 < N1, \| Φ1 ∩ Φ2\| = 3 < R. LUTerT не имеет элементов LUT для реализации функций y1, y4, y5, y7, D1. ТАБЛИЦА 2. ПСТ ДЛЯ КЛАССА A1 am C(am) as K(as) 1 h X 1 h Y 1 h  h a1 001 a2 0100 1 х y1 y4 y6 D2 1 a3 1000 1 х y1 y2 y7 D1 2 a4 010 a5 0111 1 y1 D2 D3 D4 3 a5 011 a8 1001 1 y2 D1 D4 4 a6 a7 10* a1 0000 1 х y3 y6 - 5 a9 1011 1 х y1 y2 y7 D1 D3 D4 6 a8 110 a1 0000 1 - - 7 a9 111 a` 0000 1 х y3 y6 - 8 a9 1011 1 х y1 y2 y7 D1 D3 D4 9 ТАБЛИЦА 3. ПСТ ДЛЯ КЛАССА A2 am C(am) as K(as) 2 h X 2 h Y 2 h  h a2 a3 *1 a4 0101 2 х y3 y6 D2 D4 1 a6 0110 32 xх y2 y3 y5 D2 D3 2 a7 0010 32 xх y2 y5 D3 3 Функции (9), (10) формируются три- виальным образом. Например, из табл. 2 можно получить функции: ,1321121 1 3 xxy  .3211321 1 2  xD Из табл. 3 можно полу- чить следующие функции: ,3525 2 3 xxy  2 3 1 2 yD  . А.А. БАРКАЛОВ, Л.А. ТИТАРЕНКО, Я.Е. ВИЗОР, А.В. МАТВИЕНКО, С.А. САБУРОВА Комп'ютерні засоби, мережі та системи. 2019, № 18 16 Функции (11), (12) также формируются три- виально: 2 3 1 33 yyy  и 2 3 1 22 yDD  . Функции (13) формируются по табл. 1. Например, пере- менная τ1 = 1 для состояний a6, a7 a8 и a9 . Это дает 14398761τ TTTAAAA  . Анало- гичным образом формируются остальные уравнения системы (13). Функции (2) уже были получены ранее и представлены в виде (16). Теперь имеются все системы функций, задающие схемы блоков СМПА U2(Γ1). Последний этап предложенного метода связан с применением стандартных индустриаль- ных пакетов [10, 11]. Выводы. Предложенный метод дает наи- лучшие результаты при выполнении условий R ≤ S, (17) K ≤ S. (18) При выполнении (17) блок LUTer τ имеет только один уровень логики. При этом число элементов LUT не превышает N2+RA. При выполнении (18) блок LUTer T имеет один уровень логики, состоящий из не более, чем N1+R элементов. Предложенный метод позволяет получить схемы с тремя уровнями логики. Схема имеет регулярный характер межсоединений. Напри- мер, переменные xlX поступают только на первый уровень, а переменные TrT – только на третий. Регулярность связей позволяет упростить решение задачи размещения и трассировки [22]. Оптимизация системы (2) позволяет уменьшить число межсоединений в схеме LUTer τ. Максимальное число связей определяется произведением N2×R. В рассмотренном примере это 5×4 = 20. Однако анализ системы (16) показывает, что для реализации микроопераций требуется только 7 межсоединений. Анализ библиотеки [12] показал, что условия (17), (18) имеют место для 78 % всех тестовых примеров. Исследования проводились для микросхем семейства Virtex-6 (S = 6). При этом схемы СМПА U2 отличались большим быстродействием, чем их аналоги, имеющие структуру U1. Для оставшихся 22 % тестовых примеров выигрыш был значительно меньше, так как блоки LUTer T и LUTer τ были реализованы в виде многоуровневых схем. Дальнейшие направления наших исследо- ваний связано с: 1) заменой некоторых LUT блоками EMB и 2) использованием методов кодирования логических условий для умень- шения параметра K. СПИСОК ЛИТЕРАТУРЫ 1. Grout I. Digital Systems Design with FPGAs and CPLDs. Amsterdam: Elseveit, 2008. 784 p. 2. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В., Горина В.В. Уменьшение числа LUT элементов в схеме совмещенного автомата. Управляющие системы и машины. 2016. № 3. С. 16 – 22. 3. Грушницкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем с использованием микросхем программируемой логики. СПб: БХВ. Петербург, 2002. 608 с. 4. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA– based circuits using Hierarchical Finite State Machines. Tallinn: TUT Press, 2012. 240 p. 5. Jozwiak L., Chojnski A. Effective and efficient FPGA synthesis through general functional decomposition. – Journal of System Architecture. 2003. N 4. Р. 247 – 265. 6. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Уменьшение аппаратурных затрат в совмещенных автоматах. Управляющие системы и машины. 2017. № 4. С. 43–50. 7. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного автомата в базисе FPGA. Комп’ютернi засоби, мережi та системи. К.: Ін-т кібернетики ім. В.М.Глушкова НАН України. 2016. № 15. С. 10 – 19. 8. Baranov S. Logic Synthesis for Control Automata. Dordrecht: Kluwer Academic Publishers. 1994. 312 p. 9. www.altera.com. 10. www.xilinx.com. 11. Yang S. Logic Synthesis and optimization benchmarks user guide. Microelectronics Center of North Carolina. 1991. 43 p. 12. Kubica M., Kania D., Kulisz J. A technology mapping of FSMs based on a graph of excitations and outputs. IEEE Access. 2018. N 6. P. 16123 – 16131. 13. Rawski M., Tomaszewicz P., Borowski G. and Łuba T. 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. 2011. P. 121 – 144. 14. Barkalov A., Titarenko L. Logic Synthesis for FSM – based Control Units. Berlin: Springer, 2009. 233 p. 15. Barkalov A., Titarenko L., Mazurkiewicz M. Foundations of embedded systems. Berlin: Springer, 2019. 196 p. 16. Баркалов А.А., Титаренко Л.А., Визор Я.Е., Матвиенко А.В. Реализация схемы совмещенного микро- программного автомата в базисе FPGA. Проблеми інформатизації та управління. Збірник наукових праць. Національний авіаційний університет. Київ. 2015. Вип. 3(51). С. 5–13. 17. Соловьев В.В. Проектирование цифровых схем на основе программируемых логических интегральных схем. М.: Горячая линия – ТЕЛЕКОМ, 2001. 636 с. ДВОЙНОЕ КОДИРОВАНИЕ СОСТОЯНИЙ В СОВМЕЩЕННОМ АВТОМАТЕ Computer means, networks and systems. 2019, N 18 17 18. Jozwiak L. Using FPGAs in Cyber-Physical Synthesis. Journal of System Architecture. 2013. N 2. Р. 124 – 1365. 19. Opara A., Kubica M., Kania D. Method of improving time efficiency of decomposition dedicated at FPGA structures and using BDD in process of cyber-physical synthesis. IEEE Access. 2019. N 1. P. 18101 – 18113. 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. P. 1 – 4. 21. Barkalov A., Titarenko L., Mielcatek K. Hardware Reduction for LUT-based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. Vol. 28, N 3. P. 28–41. 22. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and Optimization of FPGA-based Systems. Berlin: Springer. 2014. 432 p. REFERENCES 1. Grout I. Digital Systems Design with FPGAs and CPLDs. Amsterdam: Elseveit, 2008. 784 p. 2. Barkalov A.A., Titarenko L.A., Vizor Y.E., Matvienko A.V., Gorina V.V. Reducing the number of LUT elements in a combined automaton circuit. Control systems and computers. 2016. № 3. P. 16 – 22. 3. Grushnitsky R.I., Mursaev A.Kh., Ugryumov E.P. Designing systems using programmable logic chips. St. Petersburg: BHV. Petersburg, 2002. 608 p. 4. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA– based circuits using Hierarchical Finite State Machines. Tallinn: TUT Press, 2012. 240 p. 5. Jozwiak L., Chojnski A. Effective and efficient FPGA synthesis through general functional decomposition. Journal of System Architecture. 2003. N 4. P. 247 – 265. 6. Barkalov A.A., Titarenko L.A., Vizor Y.E., Matvienko A.V. Reducing hardware amount for combined automata. Control systems and computers. 2017, N 4. P. 43 – 50. 7. Barkalov A.A., Titarenko L.A., Vizor Y.E., Matvienko A.V. Synthesis of combined finite state machine with FPGAs. Computer means, networks and systems. K.: V.M. Glushkov Institute of cybernetics NAS of Ukraine. 2016. P. 10 – 19. 8. Baranov S. Logic Synthesis for Control Automata. – Dordrecht: Kluwer Academic Publishers. 1994. 312 p. 9. www.altera.com. 10. www.xilinx.com. 11. Yang S. Logic Synthesis and optimization benchmarks user guide. Microelectronics Center of North Carolina. 1991. 43 p. 12. Kubica M., Kania D., Kulisz J. A technology mapping of FSMs based on a graph of excitations and outputs. IEEE Access, 2018, N 6. P. 16123 – 16131. 13. 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. P. 121 – 144. 14. Barkalov A., Titarenko L. Logic Synthesis for FSM –based Control Units. Berlin: Springer, 2009. 233 p. 15. Barkalov A., Titarenko L., Mazurkiewicz M. Foundations of embedded systems. Berlin: Springer, 2019. 196 p. 16. Barkalov A.A., Titarenko L.A., Vizor Y.E., Matvienko A.V. Implementing circuit of combined finite state machine with FPGAs. Information and management problems. Collection of scientific works. National Aviation University. Kyiv. 2015. Issue 3 (51). 5 – 13 p. 17. Soloviev V.V. Designing digital circuits based on programmable logic integrated circuits. M.: Hot line – TELECOM. 2001. 636 p. 18. Jozwiak L. Using FPGAs in Cyber-Physical Synthesis. Journal of System Architecture. 2013. N 2. P. 124 – 1365. 19. Opara A., Kubica M., Kania D. Method of improving time efficiency of decomposition dedicated at FPGA structures and using BDD in process of cyber-physical synthesis. IEEE Access. 2019. N 1. P. 18101 – 18113. 20. A.Barkalov, L.Titarenko, K.Mielcatek. 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. International Journal of Applied Mathematics and Computer Science. 2018. Vol. 28, N 3. P. 28 – 41. 22. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and Optimization of FPGA-based Systems. Berlin: Springer. 2014. 432 p. Получено 12.09.2019

Двойное кодирование состояний в совмещенном автомате

Репозитарії

Схожі ресурси