# Changeset 3468

Ignore:
Timestamp:
Sep 13, 2013, 1:16:01 AM (5 years ago)
Message:

Added a brief history section. Partially added a review of state-of-the-art section.

Location:
docs/Working/re
Files:
2 edited

### Legend:

Unmodified
 r3467 of string patterns has a long history and remains a pervasive technique throughout computing applications today. {\em a brief history} % {\em a brief history} The origins of regular expression matching date back to automata theory developed by Kleene in the 1950s \cite{kleene1951}. Thompson \cite{thompson1968} is credited with the first construction to convert regular expressions to nondeterministic finite automata (NFA). Following Thompson's approach, a regular expression of length m is first converted to an NFA with O(m) nodes. It is then possible to search a text of length n using the NFA in worst case O(mn) time. Often, a more efficient choice is to convert the NFA into a DFA. A DFA has only a single active state at any time in the matching process and hence it is possible to search a text at of length n in worst-case O(n) optimal. However, it is well known that the conversion of an NFA to an equivalent DFA may result in state explosion. That is, the number of resultant DFA states may increase exponentially. In \cite{Baeza-yates_anew} a new approach to text searching was proposed based on bit-parallelism \cite{baeza1992new}. This technique takes advantage of the intrinsic parallelism of bitwise operations within a computer word. Given a w-bit word, the Shift-Or algorithm \cite{Baeza-yates_anew} algorithm uses the bit-parallel approach to simulate an NFA in O($nm/w$) worst-case time. A disadvantage of the bit-parallel Shift-Or pattern matching approach in comparison to simple string matching algorithms is an inability to skip input characters. For example, the Boyer-Moore family of algorithms \cite{boyer1977fast} skip input characters to achieve sublinear times in the average case. Backward Dawg Matching (BDM) string matching algorithms \cite{crochemore1994text} based on suffix automata are able to skip characters. The Backward Nondeterministic Dawg Matching (BNDM) pattern matching algorithm \cite{wu1992fast} combines the bit-parallel advantages of Shift-Or and with the character skipping advantages of the BDM algorithm. The nrgrep pattern matching tool is built over the BNDM algorithm, and hence the name nrgrep \cite{navarro2000}. There has been considerable interest in using parallelization techniques to improve the performance of regular expression matching. {\em a brief review}  \cite{scarpazza2011top} GPUs\cite{lin2013accelerating} FPGAs\cite{lee2007high} {\em a brief review} Scarpazza and Braudaway demonstrate that irregular, control-flow dominated text processing algorithms can be efficiently executed on multicore hardware \cite{scarpazza2008fast}. In related work, Pasetto et al. present a flexible tool that performs small-ruleset regular expression matching at a rate of 2.88 Gbps per chip on Intel Xeon E5472 hardware \cite{pasetto2010}. Naghmouchi et al. demonstrate that the Aho-Corasick string matching algorithm is well suited for implementation on commodity multicore, the Cell Broadband Engine and GPGPU hardware \cite{scarpazza2011top, naghmouchi2010}. In each case, both thread- level (additional cores) and data-level (SIMD units) hardware features are leveraged for performance. On the Cell Broadband Engine, Scarpazzaâs implementation delivers a throughput of 40 Gbps for a small dictionary size of approximately 100 patterns, and a throughput of 3.3-3.4 Gbps for a larger dictionary of tens of thousands of patterns. Scarpazza and Russell present a SIMD tokenizer that delivers 1.00â1.78 Gbps on a single Cell Broadband Engine chip \cite{scarpazza2008} and extend this approach for emulation on the Intel Larrabee instruction set \cite{scarpazza2009larrabee}. Iorio and van Lunteren describe a string matching implementation for automata that achieves 4 Gbps on the Cell Broadband Engine \cite{iorio2008}. In more recent work, TODO SIMD\cite{salapura2012accelerating} Cell BE\cite{scarpazza2011top} and % GPUs\cite{lin2013accelerating} TODO Whereas the existing approaches to parallelization have been