Changeset 3464
 Timestamp:
 Sep 12, 2013, 7:18:49 AM (6 years ago)
 Location:
 docs/Working/re
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

docs/Working/re/ppoppre.tex
r3463 r3464 82 82 \section{Introduction} 83 83 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} 84 The use of regular expressions to search texts for occurrences 85 of string patterns has a long history and 86 remains a pervasive technique throughout computing applications today. 87 {\em a brief history} 88 89 There has been considerable interest in using parallelization techniques 90 to improve the performance of regular expression matching. 91 {\em a brief review} 92 93 Whereas the existing approaches to parallelization have been 94 based on adapting traditional sequential algorithms to emergent 95 parallel architectures, we introduce both a new algorithmic 96 approach and its implementation on SIMD and GPU architectures. 97 This approach relies on a bitwise data parallel view of text 98 streams as well as a surprising use of addition to implement 99 matching operations. The closest previous work is that 100 underlying bitparallel XML parsing using 128bit SSE2 SIMD 101 technology together with a parallel scanning primitive also 102 based on addition \cite{cameron2011parallel}. 103 However, in contrast to the deterministic, longestmatch 104 scanning associated with the ScanThru primitive of that 105 work, we introduce here a new primitive MatchStar 106 that can be used in full generality for nondeterministic 107 regular expression matching. We also introduce a longstream 108 addition technique involving a further application of MatchStar 109 that enables us to scale the technique to $n$bit addition 110 in $log_{64} n$ steps. 111 112 There is also a strong keyword match between the bitparallel 113 data streams used in our approach and the bitparallelism of 114 regular expression using the bitap and WuManber NFA 115 (nondeterministic finite automata) algorithms \cite{}. 116 However those algorithms use bitparallelism in a fundamentally 117 different way: to represent all possible current NFA states 118 as a bit vector and to perform byteatatime transitions 119 using the bitwise operations. Nevertheless, the agrep and 120 nrgrep programs implemented using these techniques remain 121 among the strongest competitors in overall performance 122 to our implementations. 99 123 100 124 
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 } 1 7 @incollection{bille2009faster, 2 8 title={Faster regular expression matching},
Note: See TracChangeset
for help on using the changeset viewer.