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.