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

Conclusions

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/ppopp-re.tex

    r3485 r3486  
    163163This approach relies on a bitwise data parallel view of text
    164164streams as well as a surprising use of addition to match
    165 runs of characters in a sin`gle step.  The closest previous
     165runs of characters in a single step.  The closest previous
    166166work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD
    167167technology together with a parallel scanning primitive also
     
    174174addition technique involving a further application of MatchStar
    175175that enables us to scale the technique to $n$-bit addition
    176 in $\lceil\lg_{64}{n}\rceil)$ steps.   We ultimately apply this technique,
     176in $\lceil\log_{64}{n}\rceil$ steps.   We ultimately apply this technique,
    177177for example, to perform
    178178synchronized 4096-bit addition on GPU warps of 64 threads.
     
    194194performance, so we include them in our comparative evaluation.
    195195
    196 
    197196The remainder of this paper is organized as follows.
     197Section \ref{sec:grep} briefly describes regular expression
     198notation and the grep problem.
    198199Section \ref{sec:bitwise} presents our basic algorithm and MatchStar
    199200using a model of arbitrary-length bit-parallel data streams.
     
    208209Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work.
    209210
     211\section{Regular Expression Notation and Grep}\label{sec:grep}
     212
     213We follow common Posix notation for regular expressions.
     214A regular expression specifies a set of strings through
     215a pattern notation.   Individual characters normally
     216stand for themselves, unless they are one of the
     217special characters \verb:*+?[{\(|^$.: that serve as metacharacters
     218of the notation system.  Thus the regular expression \verb:cat:
     219is a pattern for the set consisting of the single 3-character
     220string ``\verb:cat:''.   The special characters must be escaped
     221with a backslash to prevent interpretation as metacharacter, thus
     222\verb:\$: represents the dollar-sign and \verb:\\\\: represent
     223the string consisting of two backslash characters.
     224Character class bracket expressions are pattern elements
     225that allow any character in a given class to be used in a particular
     226context.  For example, \verb:[@#%]: is a regular expression
     227that stands for any of the three given symbols.  Contiguous
     228ranges of characters may be specified using hyphens;
     229for example \verb:[0-9]: for digits and \verb:[A-Za-z0-9_]:
     230for any alphanumeric character or underscore.  If the
     231caret character immediately follows the opening bracket,
     232the class is negated, thus \verb:[^0-9]: stands for
     233any character except a digit.  The period metacharacter
     234\verb:.: stands for the class of all characters.
     235
     236Consecutive pattern elements stand for strings formed by
     237concatenation, thus \verb:[cd][ao][tg]: stands for the
     238set of 8 three-letter strings ``\verb:cat:'' through ``\verb:dog:''.
     239The alternation operator \verb:|: allows a pattern to be
     240defined to have to alternative forms, thus \verb:cat|dog:
     241matches either ``\verb:cat:'' or ``\verb:dog:''.  Concatenation
     242takes precedence over alternation, but parenthesis may be
     243used to change this, thus \verb:(ab|cd)[0-9]: stands for any
     244digit following one of the two prefixes  ``\verb:ab:'' or ``\verb:cd:''.
     245
     246Repetition operators may be appended to a pattern to specify
     247a variable number of occurrences of that pattern. 
     248The Kleene \verb:*: specifies zero-or-more occurrences
     249matching the previous pattern, while \verb:+: specifies one-or
     250more occurrences.  Thus \verb:[a-z][a-z]*: and \verb:[a-z]+:
     251both specify the same set: strings of at least one lower-case
     252letter.  The postfix operator \verb:?: specifies an optional
     253component, i.e., zero-or-one occurrence of strings matching
     254the element.  Specific bounds may be given within braces:
     255\verb:(ab){3}: specifies the string ``\verb:ababab:'',
     256\verb:[0-9A-Fa-f]{2,4}: specifies strings of two, three
     257or four hexadecimal digits, and \verb:[A-Z]{4,}: specifies
     258strings of at least 4 consecutive capital letters.
     259
     260The grep program searches a file for lines containing matches
     261to a regular expression using any of the above notations.
     262In addition, the pattern elements \verb:^: and \verb:$:
     263may be used to match respectively the beginning or the
     264end of a line.  In line-based tools such as grep, \verb:.:
     265matches any character except newlines; matches cannot extend
     266over lines.
     267Normally, grep prints all matching
     268lines to its output.  However, grep programs typically
     269allow a command line flag such as \verb:-c: to specify
     270that only a count of matching lines be produced; we use
     271this option in our experimental evaluation to focus
     272our comparisons on the performance of the underlying matching
     273algorithms.
    210274
    211275\section{Matching with Bit-Parallel Data Streams}\label{sec:bitwise}
     
    435499in both our AVX2 and GPU implementations.  In principle, one can extend
    436500the technique to additional levels.  Using 64-bit adders throughout,
    437 $\lceil\lg_{64}{n}\rceil)$ steps are needed for $n$-bit addition.
     501$\lceil\log_{64}{n}\rceil$ steps are needed for $n$-bit addition.
    438502A three-level scheme could coordinate
    43950364 groups each performing 4096-bit long additions in a two-level structure.
     
    461525
    462526\section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2}
     527
     528
    463529\subsection{Implementation Notes}
    464530\subsection{Evaluation Methodology}
     
    485551\addplot
    486552file {data/cycles3.dat};
    487 
     553 
    488554\legend{Bitstreams,NRGrep,Grep,Annot}
    489555\end{axis}
     
    492558\caption{Cycles per Byte}
    493559\end{figure}
    494 
     560 
    495561\begin{figure}
    496562\begin{center}
     
    514580\addplot
    515581file {data/instructions3.dat};
    516 
     582 
    517583\legend{Bitstreams,NRGrep,Grep,Annot}
    518584\end{axis}
     
    578644\caption{Branch Misses per Byte}
    579645\end{figure}
     646
     647
    580648
    581649\section{SIMD Scalability}\label{sec:AVX2}
     
    715783
    716784\end{center}
    717 \caption{Match Star}
    718 \label{fig:matchstar1}
     785\caption{AVX2 256-bit Addition}
     786\label{fig:AVX2add}
    719787\end{figure*}
    720788
     
    753821\section{Miscellaneous}
    754822\subsection{Skipping}
    755 \subsection{Unicode}
    756 
    757 \section{Conclusion}\label{sec:Concl}
    758 \subsection{Contributions}
    759 \begin{enumerate}
    760 \item New Algorithm Class for Regular Expression Matching
    761 \item MatchStar for Character Class Repetition
    762 \item Long Stream Addition
    763 \item Implementations showing performance and scalability
    764 \end{enumerate}
    765 \subsection{Future Work}
    766 \begin{enumerate}
    767 \item Substring capture
    768 \item Unicode character classes
    769 \item Nonregular regexp features: zero-width assertions, backreferences
    770 \item Multicore for ruleset parallelism
    771 \end{enumerate}
     823\input{re-Unicode}
     824
     825\input{conclusion}
    772826
    773827
Note: See TracChangeset for help on using the changeset viewer.