acm sigcomm

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.