iNFAnt: Nfa Pattern Matching on GPGPU Devices

By: 
Niccolo' Cascarano, Pierluigi Rolando, Fulvio Risso, and Riccardo Sisto
Appears in: 
CCR October 2010

This paper presents iNFAnt, a parallel engine for regular expression pattern matching. In contrast with traditional approaches, iNFAnt adopts non-deterministic automata, al- lowing the compilation of very large and complex rule sets that are otherwise hard to treat.

iNFAnt is explicitly designed and developed to run on graphical processing units that provide large amounts of concurrent threads; this parallelism is exploited to handle the non-determinism of the model and to process multiple packets at once, thus achieving high performance levels.

Public Review By: 
Y. Zhang

This paper proposes iNFAnt, a parallel engine for regular expression pattern matching based on generalpurpose computation on graphical processing units (GPGPU). Pattern matching is an important research area and GPGPU-based pattern matching is a timely and novel research direction. While there are previous approaches that use GPGPU to speed up deterministic finite automata (DFA) based pattern matching, this paper represents the first attempt to speed up pattern matching based on non-deterministic finite automata (NFA). The authors make good justifications on the use of GPGPU for speeding up NFA instead of DFA – large amounts of concurrent threads in GPU to offset the complexityof NFA as compared to DFA, and high memory bandwidth to transfer ablock of memory contents for NFA rather than supporting random access caused by DFA. The Compute Unified Device Architecture (CUDA) implemented by GPU devices also provides a nice programming model for easy deployment. The design of iNFAnt incorporates a few useful techniques specifically tailored for GPU environment (such as multistriding and self-loop handling). Experimental evaluation confirms the good performance of iNFAnt. The paper also sheds some light on the performance bottleneck of iNFAnt. These results are interesting and will likely inspire more follow-up research on GPGPU-based pattern matching.