# Changeset 3464 for docs/Working

Ignore:
Timestamp:
Sep 12, 2013, 7:18:49 AM (6 years ago)
Message:

Intro outline

Location:
docs/Working/re
Files:
2 edited

### Legend:

Unmodified
 r3463 \section{Introduction} Parallelism in regular expressions. \begin{enumerate} \item stream parallelism \item NFA state parallelism \item ruleset parallelism \item data parallelism \end{enumerate} The use of regular expressions to search texts for occurrences of string patterns has a long history and remains a pervasive technique throughout computing applications today. {\em a brief history} There has been considerable interest in using parallelization techniques to improve the performance of regular expression matching. {\em a brief review} Whereas the existing approaches to parallelization have been based on adapting traditional sequential algorithms to emergent parallel architectures, we introduce both a new algorithmic approach and its implementation on SIMD and GPU architectures. This approach relies on a bitwise data parallel view of text streams as well as a surprising use of addition to implement matching operations.   The closest previous work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD technology together with a parallel scanning primitive also based on addition \cite{cameron2011parallel}. However, in contrast to the deterministic, longest-match scanning associated with the ScanThru primitive of that work, we introduce here a new primitive MatchStar that can be used in full generality for nondeterministic regular expression matching.   We also introduce a long-stream addition technique involving a further application of MatchStar that enables us to scale the technique to $n$-bit addition in $log_{64} n$ steps. There is also a strong keyword match between the bit-parallel data streams used in our approach and the bit-parallelism of regular expression using the bitap and Wu-Manber NFA (nondeterministic finite automata) algorithms \cite{}. However those algorithms use bit-parallelism in a fundamentally different way: to represent all possible current NFA states as a bit vector and to perform byte-at-a-time transitions using the bitwise operations.   Nevertheless, the agrep and nrgrep programs implemented using these techniques remain among the strongest competitors in overall performance to our implementations.