1 | %----------------------------------------------------------------------------- |
---|
2 | % |
---|
3 | % Template for sigplanconf LaTeX Class |
---|
4 | % |
---|
5 | % Name: sigplanconf-template.tex |
---|
6 | % |
---|
7 | % Purpose: A template for sigplanconf.cls, which is a LaTeX 2e class |
---|
8 | % file for SIGPLAN conference proceedings. |
---|
9 | % |
---|
10 | % Guide: Refer to "Author's Guide to the ACM SIGPLAN Class," |
---|
11 | % sigplanconf-guide.pdf |
---|
12 | % |
---|
13 | % Author: Paul C. Anagnostopoulos |
---|
14 | % Windfall Software |
---|
15 | % 978 371-2316 |
---|
16 | % paul@windfall.com |
---|
17 | % |
---|
18 | % Created: 15 February 2005 |
---|
19 | % |
---|
20 | %----------------------------------------------------------------------------- |
---|
21 | |
---|
22 | |
---|
23 | \documentclass{sigplanconf} |
---|
24 | |
---|
25 | % The following \documentclass options may be useful: |
---|
26 | |
---|
27 | % preprint Remove this option only once the paper is in final form. |
---|
28 | % 10pt To set in 10-point type instead of 9-point. |
---|
29 | % 11pt To set in 11-point type instead of 9-point. |
---|
30 | % authoryear To obtain author/year citation style instead of numeric. |
---|
31 | |
---|
32 | \usepackage{amsmath} |
---|
33 | |
---|
34 | |
---|
35 | \begin{document} |
---|
36 | |
---|
37 | \special{papersize=8.5in,11in} |
---|
38 | \setlength{\pdfpageheight}{\paperheight} |
---|
39 | \setlength{\pdfpagewidth}{\paperwidth} |
---|
40 | |
---|
41 | \conferenceinfo{PPoPP 2014}{February 15-19, 2013, Orland, Florida, United States} |
---|
42 | \copyrightyear{2013} |
---|
43 | \copyrightdata{978-1-nnnn-nnnn-n/yy/mm} |
---|
44 | \doi{nnnnnnn.nnnnnnn} |
---|
45 | |
---|
46 | % Uncomment one of the following two, if you are not going for the |
---|
47 | % traditional copyright transfer agreement. |
---|
48 | |
---|
49 | %\exclusivelicense % ACM gets exclusive license to publish, |
---|
50 | % you retain copyright |
---|
51 | |
---|
52 | %\permissiontopublish % ACM gets nonexclusive license to publish |
---|
53 | % (paid open-access papers, |
---|
54 | % short abstracts) |
---|
55 | |
---|
56 | \titlebanner{banner above paper title} % These are ignored unless |
---|
57 | \preprintfooter{short description of paper} % 'preprint' option specified. |
---|
58 | |
---|
59 | \title{Bitwise Data Parallelism in Regular Expression Matching} |
---|
60 | \subtitle{Subtitle Text, if any} |
---|
61 | |
---|
62 | \authorinfo{Robert D. Cameron \and Kenneth S. Herdy \and Dan Lin \and Meng Lin \and Ben Hull \and Thomas S. Shermer \and Arrvindh Shriraman} |
---|
63 | {Simon Fraser University} |
---|
64 | {\{cameron,ksherdy,lindanl,linmengl,bhull,shermer,ashriram\}@cs.sfu.ca} |
---|
65 | |
---|
66 | \maketitle |
---|
67 | |
---|
68 | \begin{abstract} |
---|
69 | \input{abstract} |
---|
70 | \end{abstract} |
---|
71 | \category{Theory of computation}{Formal languages and automata theory}{Regular languages} |
---|
72 | \category{Computer systems organization}{Parallel architectures}{Single instruction, multiple data} |
---|
73 | |
---|
74 | % general terms are not compulsory anymore, |
---|
75 | % you may leave them out |
---|
76 | %\terms |
---|
77 | %term1, term2 |
---|
78 | |
---|
79 | \keywords |
---|
80 | regular expression matching, grep, parallel bit stream technology |
---|
81 | |
---|
82 | \section{Introduction} |
---|
83 | |
---|
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 | The origins of regular expression matching date back to automata theory |
---|
89 | developed by Kleene in the 1950s \cite{kleene1951}. |
---|
90 | Thompson \cite{thompson1968} is credited with the first construction to convert regular expressions |
---|
91 | to nondeterministic finite automata (NFA). |
---|
92 | Following Thompson's approach, a regular expression of length m is first converted |
---|
93 | to an NFA with O(m) nodes. It is then possible to search a text of length n using the |
---|
94 | NFA in worst case O(mn) time. Often, a more efficient choice |
---|
95 | is to convert the NFA into a DFA. A DFA has only a single active state at any time |
---|
96 | in the matching process and |
---|
97 | hence it is possible to search a text at of length n in worst-case O(n) optimal. |
---|
98 | However, it is well known that the conversion of an NFA to an equivalent DFA may result |
---|
99 | in state explosion. That is, the number of resultant DFA states may increase exponentially. |
---|
100 | In \cite{Baeza-yates_anew} a new approach to text searching was proposed based on bit-parallelism \cite{baeza1992new}. |
---|
101 | This technique takes advantage of the intrinsic parallelism of bitwise operations |
---|
102 | within a computer word. Given a w-bit word, the Shift-Or algorithm \cite{Baeza-yates_anew} algorithm uses the |
---|
103 | bit-parallel approach to |
---|
104 | simulate an NFA in O($nm/w$) worst-case time. |
---|
105 | |
---|
106 | A disadvantage of the bit-parallel Shift-Or pattern matching approach |
---|
107 | in comparison to simple string matching algorithms is an inability to skip input characters. |
---|
108 | For example, the Boyer-Moore family of algorithms \cite{boyer1977fast} skip input characters |
---|
109 | to achieve sublinear times in the average case. Backward Dawg Matching |
---|
110 | (BDM) string matching algorithms \cite{crochemore1994text} based on suffix automata are able to skip characters. |
---|
111 | The Backward Nondeterministic Dawg Matching (BNDM) pattern matching algorithm \cite{wu1992fast} |
---|
112 | combines the bit-parallel advantages of Shift-Or and with the character skipping advantages of the BDM algorithm. |
---|
113 | The nrgrep pattern matching tool is built over the BNDM algorithm, |
---|
114 | and hence the name nrgrep \cite{navarro2000}. |
---|
115 | |
---|
116 | There has been considerable interest in using parallelization techniques |
---|
117 | to improve the performance of regular expression matching. |
---|
118 | {\em a brief review} |
---|
119 | |
---|
120 | Scarpazza and Braudaway demonstrate that irregular, |
---|
121 | control-flow dominated text processing algorithms can be efficiently |
---|
122 | executed on multicore hardware \cite{scarpazza2008fast}. |
---|
123 | In related work, Pasetto et al. present a flexible tool that |
---|
124 | performs small-ruleset regular expression matching at a rate of |
---|
125 | 2.88 Gbps per chip on Intel Xeon E5472 hardware \cite{pasetto2010}. |
---|
126 | Naghmouchi et al. demonstrate that the Aho-Corasick |
---|
127 | string matching algorithm is well suited for implementation on commodity multicore, the |
---|
128 | Cell Broadband Engine and GPGPU hardware \cite{scarpazza2011top, naghmouchi2010}. In each case, both thread- |
---|
129 | level (additional cores) and data-level (SIMD units) hardware features are leveraged for performance. |
---|
130 | On the Cell Broadband Engine, Scarpazzaâs implementation delivers a throughput of 40 |
---|
131 | Gbps for a small dictionary size of approximately 100 patterns, and a throughput of 3.3-3.4 |
---|
132 | Gbps for a larger dictionary of tens of thousands of patterns. |
---|
133 | Scarpazza and Russell present a SIMD tokenizer that delivers 1.00â1.78 Gbps on a single |
---|
134 | Cell Broadband Engine chip \cite{scarpazza2008} and extend this approach for emulation on the Intel Larrabee |
---|
135 | instruction set \cite{scarpazza2009larrabee}. Iorio and van Lunteren describe a string matching implementation for |
---|
136 | automata that achieves 4 Gbps on the Cell Broadband Engine \cite{iorio2008}. |
---|
137 | In more recent work, |
---|
138 | |
---|
139 | TODO |
---|
140 | |
---|
141 | SIMD\cite{salapura2012accelerating} |
---|
142 | |
---|
143 | and |
---|
144 | % GPUs\cite{lin2013accelerating} |
---|
145 | TODO |
---|
146 | |
---|
147 | Whereas the existing approaches to parallelization have been |
---|
148 | based on adapting traditional sequential algorithms to emergent |
---|
149 | parallel architectures, we introduce both a new algorithmic |
---|
150 | approach and its implementation on SIMD and GPU architectures. |
---|
151 | This approach relies on a bitwise data parallel view of text |
---|
152 | streams as well as a surprising use of addition to match |
---|
153 | runs of characters in a single step. The closest previous |
---|
154 | work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD |
---|
155 | technology together with a parallel scanning primitive also |
---|
156 | based on addition \cite{cameron2011parallel}. |
---|
157 | However, in contrast to the deterministic, longest-match |
---|
158 | scanning associated with the ScanThru primitive of that |
---|
159 | work, we introduce here a new primitive MatchStar |
---|
160 | that can be used in full generality for nondeterministic |
---|
161 | regular expression matching. We also introduce a long-stream |
---|
162 | addition technique involving a further application of MatchStar |
---|
163 | that enables us to scale the technique to $n$-bit addition |
---|
164 | in $log_{64} n$ steps. We ultimately apply this technique, |
---|
165 | for example, to perform |
---|
166 | synchronized 4096-bit addition on GPU warps of 64 threads. |
---|
167 | |
---|
168 | There is also a strong keyword match between the bit-parallel |
---|
169 | data streams used in our approach and the bit-parallelism |
---|
170 | used for NFA state transitions in the classical algorithms of |
---|
171 | Wu and Manber \cite{wu1992agrep}, Baez-Yates and Gonnet \cite{baeza1992new} |
---|
172 | and Navarro and Raffinot \cite{navarro1998bit}. |
---|
173 | However those algorithms use bit-parallelism in a fundamentally |
---|
174 | different way: representing all possible current NFA states |
---|
175 | as a bit vector and performing parallel transitions to a new |
---|
176 | set of states using table lookups and bitwise logic. Whereas |
---|
177 | our approach can match multiple characters per step, bit-parallel |
---|
178 | NFA algorithms proceed through the input one byte at a time. |
---|
179 | Nevertheless, the agrep \cite{wu1992agrep} and |
---|
180 | nrgrep \cite{navarro2000} programs implemented using these techniques remain |
---|
181 | among the strongest competitors in regular expression matching |
---|
182 | performance, so we include them in our comparative evaluation. |
---|
183 | |
---|
184 | |
---|
185 | The remainder of this paper is organized as follows. |
---|
186 | Section \ref{sec:unbounded} presents our basic algorithm using |
---|
187 | a model of unbounded bitwise data parallelism. |
---|
188 | Section \ref{sec:regexp} |
---|
189 | Section \ref{sec:analysis} |
---|
190 | Section \ref{sec:SSE2} |
---|
191 | Section \ref{sec:AVX2} |
---|
192 | Section \ref{sec:GPU} |
---|
193 | Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work. |
---|
194 | |
---|
195 | |
---|
196 | \section{An Unbounded Model for Bitwise Regular Expression Matching}\label{sec:unbounded} |
---|
197 | |
---|
198 | Whereas all traditional regular expression matching engines are |
---|
199 | fundamentally based on an element-at-a-time processing model, |
---|
200 | the approach we introduce in this paper is based on quite a |
---|
201 | different conceptual model: processing all elements of an input data |
---|
202 | stream simultaneously. Depending on the available parallel |
---|
203 | processing resources, an actual implementation may divide an |
---|
204 | input stream into segments and process the segments |
---|
205 | sequentially. Within each segment, all elements of the input |
---|
206 | stream are processed in parallel. The approach is inherently |
---|
207 | scalable and can be adapted to a variety of parallel architectures. |
---|
208 | The fundamental primitives required are bitwise logic and |
---|
209 | long-stream addition. |
---|
210 | |
---|
211 | A key concept in this approach is the derivation of bit streams |
---|
212 | that are parallel to the input data stream, i.e., in one-to-one |
---|
213 | correspondence with the data element positions of the input |
---|
214 | streams. Typically, the input stream is a byte stream comprising |
---|
215 | the 8-bit character code units of a particular encoding such |
---|
216 | as extended ASCII, ISO-8859-1 or UTF-8. However, the method may also |
---|
217 | easily be used with wider code units such as the 16-bit code units of |
---|
218 | UTF-16. In the case of a byte stream, the first step is to transpose |
---|
219 | the byte stream into eight parallel bit streams, such that bit stream |
---|
220 | $i$ comprises the $i^\text{th}$ bit of each byte. These streams form |
---|
221 | a set of basis bit streams from which many other parallel bit |
---|
222 | streams can be calculated, such as character class bit |
---|
223 | streams such that each bit $j$ of the stream specifies |
---|
224 | whether character $j$ of the input stream is in the class |
---|
225 | or not. {\bf perhaps a figure here.} |
---|
226 | |
---|
227 | Using the SIMD capabilities of commodity processors, |
---|
228 | the basis bit streams and character class bit streams may be |
---|
229 | efficiently computed using the Parabix framework that |
---|
230 | has been developed and used extensively for high-performance |
---|
231 | XML parsing \cite{}. For example, working with the 128-bit |
---|
232 | SIMD registers on commodity Intel and AMD processors, |
---|
233 | the Parabix framework can be employed to process input |
---|
234 | streams in blocks of 128 bytes at a time. However, the |
---|
235 | general model is not dependent on any particular data block size |
---|
236 | and can be scaled for arbitrary sized blocks depending on |
---|
237 | available resources. |
---|
238 | |
---|
239 | \section{Bitwise Regular Expression Matching with MatchStar}\label{sec:regexp} |
---|
240 | |
---|
241 | |
---|
242 | \subsection{Bitwise Data Parallelism vs. Bit-Parallel State Transition} |
---|
243 | The bitap algorithms use bitwise operations in an orthogonal way. |
---|
244 | |
---|
245 | \section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis} |
---|
246 | |
---|
247 | \begin{enumerate} |
---|
248 | \item Operations |
---|
249 | \item Memory behaviour per input byte: note tables of DFA/NFA. |
---|
250 | |
---|
251 | Bille and Throup \em{Faster regular expression matching}\cite{bille2009faster} |
---|
252 | |
---|
253 | \end{enumerate} |
---|
254 | |
---|
255 | |
---|
256 | |
---|
257 | \section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2} |
---|
258 | \subsection{Implementation Notes} |
---|
259 | \subsection{Evaluation Methodology} |
---|
260 | \subsection{Comparison} |
---|
261 | |
---|
262 | |
---|
263 | |
---|
264 | \section{SIMD Scalability}\label{sec:AVX2} |
---|
265 | \subsection{AVX Stream Addition} |
---|
266 | We use MatchStar for carry propagation. |
---|
267 | |
---|
268 | \section{GPU Implementation}\label{sec:GPU} |
---|
269 | |
---|
270 | \section{Miscellaneous} |
---|
271 | \subsection{Skipping} |
---|
272 | \subsection{Unicode} |
---|
273 | |
---|
274 | \section{Conclusion}\label{sec:Concl} |
---|
275 | \subsection{Contributions} |
---|
276 | \begin{enumerate} |
---|
277 | \item New Algorithm Class for Regular Expression Matching |
---|
278 | \item MatchStar for Character Class Repetition |
---|
279 | \item Long Stream Addition |
---|
280 | \item Implementations showing performance and scalability |
---|
281 | \end{enumerate} |
---|
282 | \subsection{Future Work} |
---|
283 | \begin{enumerate} |
---|
284 | \item Substring capture |
---|
285 | \item Unicode character classes |
---|
286 | \item Nonregular regexp features: zero-width assertions, backreferences |
---|
287 | \item Multicore for ruleset parallelism |
---|
288 | \end{enumerate} |
---|
289 | |
---|
290 | |
---|
291 | |
---|
292 | %\appendix |
---|
293 | %\section{Appendix Title} |
---|
294 | |
---|
295 | %This is the text of the appendix, if you need one. |
---|
296 | |
---|
297 | \acks |
---|
298 | |
---|
299 | This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada and |
---|
300 | MITACS, Inc. |
---|
301 | |
---|
302 | % We recommend abbrvnat bibliography style. |
---|
303 | |
---|
304 | \bibliographystyle{abbrvnat} |
---|
305 | |
---|
306 | % The bibliography should be embedded for final submission. |
---|
307 | |
---|
308 | \bibliography{reference} |
---|
309 | |
---|
310 | %\begin{thebibliography}{} |
---|
311 | %\softraggedright |
---|
312 | |
---|
313 | %\bibitem[Smith et~al.(2009)Smith, Jones]{smith02} |
---|
314 | %P. Q. Smith, and X. Y. Jones. ...reference text... |
---|
315 | % |
---|
316 | %\end{thebibliography} |
---|
317 | |
---|
318 | |
---|
319 | \end{document} |
---|
320 | |
---|
321 | |
---|