# Changeset 3486

Ignore:
Timestamp:
Sep 14, 2013, 6:51:25 PM (6 years ago)
Message:

Conclusions

Location:
docs/Working/re
Files:
 r3485 This approach relies on a bitwise data parallel view of text streams as well as a surprising use of addition to match runs of characters in a single step.  The closest previous runs of characters in a single step.  The closest previous work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD technology together with a parallel scanning primitive also addition technique involving a further application of MatchStar that enables us to scale the technique to $n$-bit addition in $\lceil\lg_{64}{n}\rceil)$ steps.   We ultimately apply this technique, in $\lceil\log_{64}{n}\rceil$ steps.   We ultimately apply this technique, for example, to perform synchronized 4096-bit addition on GPU warps of 64 threads. performance, so we include them in our comparative evaluation. The remainder of this paper is organized as follows. Section \ref{sec:grep} briefly describes regular expression notation and the grep problem. Section \ref{sec:bitwise} presents our basic algorithm and MatchStar using a model of arbitrary-length bit-parallel data streams. Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work. \section{Regular Expression Notation and Grep}\label{sec:grep} We follow common Posix notation for regular expressions. A regular expression specifies a set of strings through a pattern notation.   Individual characters normally stand for themselves, unless they are one of the special characters \verb:*+?[{\(|^$.: that serve as metacharacters of the notation system. Thus the regular expression \verb:cat: is a pattern for the set consisting of the single 3-character string \verb:cat:''. The special characters must be escaped with a backslash to prevent interpretation as metacharacter, thus \verb:\$: represents the dollar-sign and \verb:\\\\: represent the string consisting of two backslash characters. Character class bracket expressions are pattern elements that allow any character in a given class to be used in a particular context.  For example, \verb:[@#%]: is a regular expression that stands for any of the three given symbols.  Contiguous ranges of characters may be specified using hyphens; for example \verb:[0-9]: for digits and \verb:[A-Za-z0-9_]: for any alphanumeric character or underscore.  If the caret character immediately follows the opening bracket, the class is negated, thus \verb:[^0-9]: stands for any character except a digit.  The period metacharacter \verb:.: stands for the class of all characters. Consecutive pattern elements stand for strings formed by concatenation, thus \verb:[cd][ao][tg]: stands for the set of 8 three-letter strings \verb:cat:'' through \verb:dog:''. The alternation operator \verb:|: allows a pattern to be defined to have to alternative forms, thus \verb:cat|dog: matches either \verb:cat:'' or \verb:dog:''.  Concatenation takes precedence over alternation, but parenthesis may be used to change this, thus \verb:(ab|cd)[0-9]: stands for any digit following one of the two prefixes  \verb:ab:'' or \verb:cd:''. Repetition operators may be appended to a pattern to specify a variable number of occurrences of that pattern. The Kleene \verb:*: specifies zero-or-more occurrences matching the previous pattern, while \verb:+: specifies one-or more occurrences.  Thus \verb:[a-z][a-z]*: and \verb:[a-z]+: both specify the same set: strings of at least one lower-case letter.  The postfix operator \verb:?: specifies an optional component, i.e., zero-or-one occurrence of strings matching the element.  Specific bounds may be given within braces: \verb:(ab){3}: specifies the string `\verb:ababab:'', \verb:[0-9A-Fa-f]{2,4}: specifies strings of two, three or four hexadecimal digits, and \verb:[A-Z]{4,}: specifies strings of at least 4 consecutive capital letters. The grep program searches a file for lines containing matches to a regular expression using any of the above notations. In addition, the pattern elements \verb:^: and \verb:$: may be used to match respectively the beginning or the end of a line. In line-based tools such as grep, \verb:.: matches any character except newlines; matches cannot extend over lines. Normally, grep prints all matching lines to its output. However, grep programs typically allow a command line flag such as \verb:-c: to specify that only a count of matching lines be produced; we use this option in our experimental evaluation to focus our comparisons on the performance of the underlying matching algorithms. \section{Matching with Bit-Parallel Data Streams}\label{sec:bitwise} in both our AVX2 and GPU implementations. In principle, one can extend the technique to additional levels. Using 64-bit adders throughout,$\lceil\lg_{64}{n}\rceil)$steps are needed for$n$-bit addition.$\lceil\log_{64}{n}\rceil$steps are needed for$n\$-bit addition. A three-level scheme could coordinate 64 groups each performing 4096-bit long additions in a two-level structure. \section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2} \subsection{Implementation Notes} \subsection{Evaluation Methodology} \addplot file {data/cycles3.dat}; \legend{Bitstreams,NRGrep,Grep,Annot} \end{axis} \caption{Cycles per Byte} \end{figure} \begin{figure} \begin{center} \addplot file {data/instructions3.dat}; \legend{Bitstreams,NRGrep,Grep,Annot} \end{axis} \caption{Branch Misses per Byte} \end{figure} \section{SIMD Scalability}\label{sec:AVX2} \end{center} \caption{Match Star} \label{fig:matchstar1} \caption{AVX2 256-bit Addition} \label{fig:AVX2add} \end{figure*} \section{Miscellaneous} \subsection{Skipping} \subsection{Unicode} \section{Conclusion}\label{sec:Concl} \subsection{Contributions} \begin{enumerate} \item New Algorithm Class for Regular Expression Matching \item MatchStar for Character Class Repetition \item Long Stream Addition \item Implementations showing performance and scalability \end{enumerate} \subsection{Future Work} \begin{enumerate} \item Substring capture \item Unicode character classes \item Nonregular regexp features: zero-width assertions, backreferences \item Multicore for ruleset parallelism \end{enumerate} \input{re-Unicode} \input{conclusion}