| Русский Русский | English English |
   
Главная Архив номеров
24 | 02 | 2020
10.14489/vkit.2014.05.pp.003-007

DOI: 10.14489/vkit.2014.05.pp.003-007

Левин И. И., Ильченко Д. Н.
КОМПЛЕКСНАЯ МИНИМИЗАЦИЯ ЦИФРОВЫХ АВТОМАТОВ ПРИ РЕШЕНИИ ЗАДАЧИ ПОИСКА ШАБЛОНОВ
(с. 3–7)

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

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

 

Levin I. I., Ilchenko D. N.
COMPLEX MINIMIZATION OF DIGITAL STATE MACHINES FOR THE PROBLEM OF PATTERN MATCHING
(pp. 3–7)

Abstract. This article proposes new methods for optimization of digital state machines which perform automatic based search algorithms of patterns with masks on FPGA (Field-Programmable Gate Array). The aim of traditional methods of state machines minimization is reduction of the number of their internal states that leads to reduction of the number of memory units needed for implementation. Effective synthesis of the state machine within FPGA requires not only reduction of the number of memory units, but also reduction of the number of used LUT (Look-Up Tables) which on architectural features of the up-to-date FPGA families. The developed methods are directed to transformation of logic structure of state machines for complex minimization of hardware burden. Optimization of digital state machines consists of several phases. The first phase is creation of a state machine graph for each pattern. Then a group of state machines is united into a single state machine by means of minimization of equivalent states. This leads to minimization of memory units needed for implementation of states of the state machine. The next phase is state vectorization. Transitions in these states correspond to pattern masks. Such states are united into a state array vertex and then a unit, which controls states in the state array vertex, is created. State vectorization does not reduce the total number of states, but considerably simplifies the structure of the digital state machine and leads to minimization of the number of LUTs. After state vectorization it is possible to perform vectorization of the graph vertices. In this phase the graph vertices are replaced with memory units, an address unit and a unit, which compares storage contents and an input data stream, are created. This also reduces the number of LUTs. Use of complex transformations of digital state machine structure reduces the number of LUTs, used for its implementation, and simplifies its synthesis. The article presents the mathematical equation of hardware resource cost evaluation and the graphics of efficiency for each optimization method. The developed methods can be effectively used in development of software and hardware complex of antivirus protection on a reconfigurable computing system.

Keywords: Reconfigurable computer system; Field-programmable gate arrays; Digital state machine; Pattern search; Equivalent states of digital state machines; Vectoring states; Classic vectoring vertex.

Рус

И. И. Левин, Д. Н. Ильченко (Научно-исследовательский институт многопроцессорных вычислительных систем им. акад. А. В. Каляева Южного федерального университета, Таганрог) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

 I. I. Levin, D. N. Ilchenko (Scientific Research Institute of Multiprocessor Computer Systems of Southern Federal University, Taganrog) ) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Рус

1. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.
2. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб.: СПбГПУ, 2008. 227 с.
3. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: пер. с англ. 2-е изд. М.: Вильямс, 2002. 528 с.
4. Мельников Б. Ф., Мельникова А. А. Многоаспектная минимизация недетерминированных конечных автоматов (Часть I. Вспомогательные факты и алгоритмы) // Изв. вузов. Поволжский регион. Физико-математические науки. 2011. № 4. С. 59 – 69.
5. Мельников Б. Ф., Сайфуллина М. Р. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов // Изв. вузов. Математика. 2009. № 4. С. 67 – 71.
6. Каляев А. В., Левин И. И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. 380 с.
7. Ильченко Д. Н. Применение операции векторизации состояний для синтеза цифровых автоматов [Электронный ресурс] // Инженерный вестник Дона. 2013. № 4. URL: http://www.ivdon.ru/magazine/archive/n4y2013/2028 (дата обращения: 10.03.2014).

Eng

1. Glushkov V. M. (1962). Synthesis of digital automata. Moscow: Fizmatgiz.
2. Polikarpova N. I., Shalyto A. A. (2008). Programming for automata. St. Petersburg: SPbGU.
3. Khopkroft D., Motvani R., Ul'man Dzh. (2002). Introduction to automata theory, languages and computation. (2nd ed.). Moscow: Williams.
4. Mel'nikov B. F., Mel'nikova A. A. (2011). Multidimensional minimization of non-deterministic finite automata. (Part I, auxiliary facts and algorithms). Izvestiia vuzov. Povolzhskii region. Fiziko-matematicheskie nauki, (4), pp. 59–69.
5. Mel'nikov B. F., Saifullina M. R. (2009). On certain algorithms of equivalent transformation of a non-deterministic finite automata. Izvestiia vuzov. Matematika, (4), pp. 67-71.
6. Kaliaev A. V., Levin I. I. (2003). Modular and scalable multiprocessor systems with structural and procedural organization of calculations. Moscow: Ianus-K.
7. Il'chenko D. N. (2013). Implementation of vectorization conditions for the synthesis of digital automata. Inzhenernyi vestnik Dona, (4). Available at: http://www.ivdon.ru/magazine/archive/n4y2013/2028 (Accessed: 10.03.2014)

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 250 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2014.05.pp.003-007}

.

Eng

This article  is available in electronic format (PDF).

The cost of a single article is 250 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2014.05.pp.003-007}

 

 

 

 

 

.

.

 

 
Поиск
Баннер
Баннер
Баннер
Баннер
Баннер
Журнал КОНТРОЛЬ. ДИАГНОСТИКА
Баннер
Rambler's Top100 Яндекс цитирования