1 | \documentclass[a4paper,10pt]{article} |
---|
2 | \usepackage[utf8]{inputenc} |
---|
3 | |
---|
4 | \def \Bitstream{Bit Stream} |
---|
5 | \def \bitstream{bit stream} |
---|
6 | |
---|
7 | %opening |
---|
8 | \title{Fast Regular Expression Matching using Parallel \Bitstream{}s} |
---|
9 | \author{ |
---|
10 | {Robert D. Cameron} \\ |
---|
11 | \and |
---|
12 | {Kenneth S. Herdy} \\ |
---|
13 | \and |
---|
14 | {Ben Hull} \\ |
---|
15 | \and |
---|
16 | {Thomas C. Shermer} \\ |
---|
17 | \\School of Computing Science |
---|
18 | \\Simon Fraser University |
---|
19 | } |
---|
20 | \begin{document} |
---|
21 | |
---|
22 | \date{} |
---|
23 | \maketitle |
---|
24 | |
---|
25 | \begin{abstract} |
---|
26 | |
---|
27 | A parallel regular expression matching method is introduced and studied in |
---|
28 | application to the problem of online pattern matching. |
---|
29 | |
---|
30 | The method is based on the concept of parallel |
---|
31 | \bitstream{} technology, in which parallel streams of bits are formed such |
---|
32 | that each stream comprises bits in one-to-one correspondence with the |
---|
33 | character code units of a source data stream. |
---|
34 | |
---|
35 | On processors supporting W-bit addition operations, the method processes W source characters |
---|
36 | in parallel and performs up to W finite state transitions per clock cycle. |
---|
37 | |
---|
38 | Performance results show a dramatic speed-up over traditional and state-of-the-art alternatives. |
---|
39 | |
---|
40 | \end{abstract} |
---|
41 | |
---|
42 | \section{Introduction} |
---|
43 | \label{Introduction} |
---|
44 | %\input{introduction.tex} |
---|
45 | |
---|
46 | Regular expresssion matching is an extensively studied problem with application to |
---|
47 | numerous application domains. A multitude |
---|
48 | of algorithms and software tools have been developed to the address the particular |
---|
49 | demands of the various application domains. |
---|
50 | |
---|
51 | The pattern matching problem can be |
---|
52 | stated as follows. Given a text T$_{1..n}$ of n characters and a pattern P, |
---|
53 | find all the text positions of T that start an occurrence of P. Alternatively, |
---|
54 | one may want all the final positions of occurrences. Some applications require |
---|
55 | slightly different output such as the line that matches the pattern. |
---|
56 | |
---|
57 | A pattern P can be a simple string, but it can also be, a regular expression. |
---|
58 | A regular expression, is an expression that specifies a set of strings. |
---|
59 | A regular expression is composed of (i) simple strings and (ii) the |
---|
60 | union, concatenation and Kleene closure of other regular expressions. |
---|
61 | To avoid parentheses it is assumed that the Kleene star has the highest priority, |
---|
62 | next concatenation and then alternation, however, most formalisms provides grouping |
---|
63 | operators to allow the definition of scope and operator precedence. |
---|
64 | Readers unfamiliar with the concept of regular expression matching are referred |
---|
65 | classical texts such as \cite{aho2007}. |
---|
66 | |
---|
67 | Regular expression matching is commonly performed using a wide variety of |
---|
68 | publically available software tools for on-line pattern matching. For instance, |
---|
69 | UNIX grep, Gnu grep, agrep, cgrep, nrgrep, and Perl regular |
---|
70 | expressions \cite{abou-assaleh2004}. Amongst these tools Gnu grep (egrep), |
---|
71 | agrep, and nrgrep are widely known and considered as |
---|
72 | the fastest regular expression matching tools in practice \cite{navarro2000}. |
---|
73 | and are of particular interest to this study. |
---|
74 | |
---|
75 | % simple patterns, extended patterns, regular expressions |
---|
76 | |
---|
77 | % motivation / previous work |
---|
78 | Although tradi finite state machine methods used in the scanning and parsing of |
---|
79 | text streams is considered to be the hardest of the â13 dwarvesâ to parallelize |
---|
80 | [1], parallel bitstream technology shows considerable promise for these types of |
---|
81 | applications [3, 4]. In this approach, character streams are processed W positions |
---|
82 | at a time using the W-bit SIMD registers commonly found on commodity processors |
---|
83 | (e.g., 128-bit XMM registers on Intel/AMD chips). This is achieved by |
---|
84 | first slicing the byte streams into eight separate basis bitstreams, one for each bit |
---|
85 | position within the byte. These basis bitstreams are then combined with bitwise |
---|
86 | logic and shifting operations to compute further parallel bit streams of interest. |
---|
87 | |
---|
88 | We further increase the parallelism in our methods by introducing a new parallel |
---|
89 | scanning primitive which we have coined Match Star. Match Star returns all matches |
---|
90 | in a single operation and eliminates backtracking |
---|
91 | when a partially successful search path fails. |
---|
92 | |
---|
93 | |
---|
94 | The remainder of this paper is organized as follows. |
---|
95 | |
---|
96 | Section~\ref{Background} presents background material on classic |
---|
97 | regular expression pattern matching techniques and provides insight into the |
---|
98 | efficiency of traditional regular expression software tools. |
---|
99 | |
---|
100 | Section~\ref{Bitwise Parallel Data Streams} describes out data parallel |
---|
101 | regular expression matching techniques. |
---|
102 | |
---|
103 | Section~\ref{Compiler Technology} |
---|
104 | |
---|
105 | Section~\ref{Methodology} describes the evaluation framework and Section~\ref{Experimental Results} |
---|
106 | presents a detailed performance analysis of our data parallel \bitstream{} techniques against |
---|
107 | Gnu grep, agrep, and nr-grep. |
---|
108 | |
---|
109 | Section~\ref{conclusion} concludes the paper. |
---|
110 | |
---|
111 | \section{Background} |
---|
112 | \label{Background} |
---|
113 | %\input{background.tex} |
---|
114 | |
---|
115 | % Background |
---|
116 | |
---|
117 | % History |
---|
118 | |
---|
119 | Historically, the origins of regular expression matching date back to automata theory |
---|
120 | and formal language theory developed by Kleene in the 1950s \cite{kleene1951}. |
---|
121 | |
---|
122 | In 1959, Dana and Scott demonstrated that |
---|
123 | NFAs can be simulated using Deterministic Finite Automata (DFA) in which each DFA |
---|
124 | state corresponds to a set of NFA states. |
---|
125 | |
---|
126 | Thompson, in 1968, is credited with the first construction to convert regular expressions |
---|
127 | to nondeterministic finite automata (NFA) for regular expression matching. |
---|
128 | |
---|
129 | Thompsonâs publication \cite{thompson1968} marked the beginning of a long line of |
---|
130 | regular expression implementations that construct automata for pattern matching. |
---|
131 | |
---|
132 | The traditional technique [16] to search a regular expression of length m in |
---|
133 | a text of length n is to first convert the expression into a non-deterministic |
---|
134 | automaton (NFA) with O(m) nodes. It is possible to search the text using the |
---|
135 | NFA directly in O(mn) worst case time. The cost comes from the fact that |
---|
136 | more than one state of the NFA may be active at each step, and therefore all |
---|
137 | may need to be updated. A more effcient choice is to convert the NFA into a |
---|
138 | DFA. A DFA has only a single active state and allows to search the text at |
---|
139 | O(n) worst-case optimal. The problem with this approach is that the DFA |
---|
140 | may have O(2^m) states. |
---|
141 | |
---|
142 | In general, the general process is first to build a |
---|
143 | NFA from the regular expression and simulate the NFA on text input, |
---|
144 | or alternatively to convert the NFA into a |
---|
145 | DFA, optionally minimize the number of states in the DFA, |
---|
146 | and finally simulate the DFA on text input. |
---|
147 | |
---|
148 | |
---|
149 | |
---|
150 | \section{Parallel Bitwise Data Streams} |
---|
151 | \label{Parallel Bitwise Data Streams} |
---|
152 | |
---|
153 | |
---|
154 | \section{Compiler Technology} |
---|
155 | \label{Compiler Technology} |
---|
156 | |
---|
157 | \section{Methodology} |
---|
158 | \label{Methodology} |
---|
159 | %\input{methodology.tex} |
---|
160 | |
---|
161 | We compare the performance of our parallel \bitstream{} techniques against |
---|
162 | Gnu grep, agrep, and nr-grep. |
---|
163 | |
---|
164 | Given a regular expression R and a test T the regular expression matching |
---|
165 | problem finds all ending position of substrings in Q that matches a string in |
---|
166 | the language denoted by R. |
---|
167 | |
---|
168 | The behaviour of Gnu grep, agrep, and nr-grep are differ in that |
---|
169 | |
---|
170 | Gnu grep |
---|
171 | |
---|
172 | agrep |
---|
173 | |
---|
174 | nr-grep |
---|
175 | |
---|
176 | |
---|
177 | |
---|
178 | \section{Experimental Results} |
---|
179 | \label{results} |
---|
180 | %\input{results.tex} |
---|
181 | |
---|
182 | \section{Conclusion and Future Work} |
---|
183 | \label{conclusion} |
---|
184 | %\input{conclusion.tex} |
---|
185 | |
---|
186 | { |
---|
187 | \bibliographystyle{acm} |
---|
188 | \bibliography{reference} |
---|
189 | } |
---|
190 | |
---|
191 | \end{document} |
---|