A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton

Hiroki NAKAHARA  Tsutomu SASAO  Munehiro MATSUURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.2   pp.364-373
Publication Date: 2012/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.364
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Design Methodology
Keyword: 
regular expression,  NFA,  DFA,  MNFAU,  FPGA,  

Full Text: PDF(780.2KB)>>
Buy this Article




Summary: 
This paper shows a design method for a regular expression matching circuit based on a decomposed automaton. To implement a regular expression matching circuit, first, we convert a regular expression into a non-deterministic finite automaton (NFA). Then, to reduce the number of states, we convert the NFA into a merged-states non-deterministic finite automaton with unbounded string transition (MNFAU) using a greedy algorithm. Next, to realize it by a feasible amount of hardware, we decompose the MNFAU into a deterministic finite automaton (DFA) and an NFA. The DFA part is implemented by an off-chip memory and a simple sequencer, while the NFA part is implemented by a cascade of logic cells. Also, in this paper, we show that the MNFAU based implementation has lower area complexity than the DFA and the NFA based ones. Experiments using regular expressions form SNORT shows that, as for the embedded memory size per a character, the MNFAU is 17.17-148.70 times smaller than DFA methods. Also, as for the number of LCs (Logic Cells) per a character, the MNFAU is 1.56-5.12 times smaller than NFA methods. This paper describes detail of the MEMOCODE2010 HW/SW co-design contest for which we won the first place award.