Dissertation

 
Kořenek, J.: Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA, Brno, CZ, UPSY FIT VUT, 2010, p. 105
Publication language:czech
Original title:Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA
Title (en):Fast Regular Expression Matching Using FPGA
Pages:105
Place:Brno, CZ
Year:2010
Publisher:Department of Computer Systems FIT BUT
URL:https://wis.fit.vutbr.cz/FIT/st/rp.php/rp/2010/PD/162.pdf [PDF]
Keywords
Regular expression, matching, nondeterministic automaton, FPGA.

Annotation
This thesis deals with fast regular expression matching using FPGA. Regular expression matching is time critical operation, which is used in network security and monitoring devices.  Current processors are not able to achieve multi-gigabit speed even if they use the fastest algorithms.  Therefore many hardware architectures have been proposed for a string or a regular expression matching. Unfortunately all these architectures are able to achieve a high throughput only for small sets of regular expressions. The capacity and the speed of available memories is a limitation for architectures based on a deterministic finite automaton and the capacity of available FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore the goal of this thesis is to reduce the amount of consumed FPGA logic for a high speed regular expression matching using a nondeterministic automaton. New algorithm is proposed to find a non-collision set of states which enables to map a part of the transition table to the memory instead of the FPGA logic cells. For all analysed sets of regular expressions, the algorithm was able to find a non-collision set with 61,4 % of states in average and a non-collision set with 83,6 % of states for the best case. The proposed algorithm was extended to find k non-collision sets, which enables for k=8 to increase the amount of states represented by non-collision sets to 84,7 % in average. Parallel Parts of Automaton model is introduced to represent a division of the nondeterministic automaton by sets of states.  Every set of states is represented by a one part of the automaton. The model enables to optimize the mapping to the FPGA with respect to known characteristics of the automaton parts. It was proved that the created model has the same expressing power as finite automaton and can represent any set of regular expressions.  New NFA Split and NFA k Split architectures were designed for mapping Parallel Parts of the Automaton to FPGA. As non-collision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flip-flop registers and look-up tables is is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flip-flops to 43,3 % and look-up tables to 66,8 % in average.  

BibTeX:
@PHDTHESIS{
   author = {Jan Kořenek},
   title = {Rychlé vyhledávání regulárních výrazů s využitím technologie
	FPGA},
   pages = {105},
   year = {2010},
   location = {Brno, CZ},
   publisher = {Department of Computer Systems FIT BUT},
   language = {czech},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9415}
}