Changeset 3464 for docs


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

Intro outline

Location:
docs/Working/re
Files:
2 edited

Legend:

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

    r3463 r3464  
    8282\section{Introduction}
    8383
    84 
    85 
    86 
    87 
    88 
    89 
    90 
    91 
    92 Parallelism in regular expressions.
    93 \begin{enumerate}
    94 \item stream parallelism
    95 \item NFA state parallelism
    96 \item ruleset parallelism
    97 \item data parallelism
    98 \end{enumerate}
     84The use of regular expressions to search texts for occurrences
     85of string patterns has a long history and
     86remains a pervasive technique throughout computing applications today.
     87{\em a brief history}
     88
     89There has been considerable interest in using parallelization techniques
     90to improve the performance of regular expression matching.
     91{\em a brief review}
     92
     93Whereas the existing approaches to parallelization have been
     94based on adapting traditional sequential algorithms to emergent
     95parallel architectures, we introduce both a new algorithmic
     96approach and its implementation on SIMD and GPU architectures.
     97This approach relies on a bitwise data parallel view of text
     98streams as well as a surprising use of addition to implement
     99matching operations.   The closest previous work is that
     100underlying bit-parallel XML parsing using 128-bit SSE2 SIMD
     101technology together with a parallel scanning primitive also
     102based on addition \cite{cameron2011parallel}.   
     103However, in contrast to the deterministic, longest-match
     104scanning associated with the ScanThru primitive of that
     105work, we introduce here a new primitive MatchStar
     106that can be used in full generality for nondeterministic
     107regular expression matching.   We also introduce a long-stream
     108addition technique involving a further application of MatchStar
     109that enables us to scale the technique to $n$-bit addition
     110in $log_{64} n$ steps.
     111
     112There is also a strong keyword match between the bit-parallel
     113data streams used in our approach and the bit-parallelism of
     114regular expression using the bitap and Wu-Manber NFA
     115(nondeterministic finite automata) algorithms \cite{}.
     116However those algorithms use bit-parallelism in a fundamentally
     117different way: to represent all possible current NFA states
     118as a bit vector and to perform byte-at-a-time transitions
     119using the bitwise operations.   Nevertheless, the agrep and
     120nrgrep programs implemented using these techniques remain
     121among the strongest competitors in overall performance
     122to our implementations.
    99123
    100124
  • docs/Working/re/reference.bib

    r3459 r3464  
     1@article{lin2012accelerating,
     2  title={Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs},
     3  author={Lin, C and Liu, C and Chien, L and Chang, S},
     4  year={2012},
     5  publisher={IEEE}
     6}
    17@incollection{bille2009faster,
    28  title={Faster regular expression matching},
Note: See TracChangeset for help on using the changeset viewer.