# source:docs/Working/re/sse2.tex@3508

Last change on this file since 3508 was 3508, checked in by bhull, 6 years ago

Minor change.

File size: 6.3 KB
Line
1\section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2}
2
3
4\subsection{Implementation Notes}
5\subsection{Evaluation Methodology}
6
7
8
9\paragraph{GREP Implementations:}
10We evaluate our Bitwise Data Parallel implementation against GNU grep version 2.10 and nrgrep version 1.12. GNU grep is a popular open-source grep implementation that uses DFAs. NR-grep is one of the strongest competitors in regular expression matching performance. It uses an NFA-based approach.
11
12\paragraph{Expressions:}
13Each GREP implementation is tested with the five regular expressions in Table \ref{RegularExpressions}.  Xquote matches any of the representations of a quote in xml.  It is run on roads-2.gml, a 11,861,751 byte gml data file. The other four expressions are taken from Benchmark of Regex Libraries[?] and are all run on a concatenated version of the linux howto[?] which is 39,422,105 bytes in length.  @ simply matches the "@" character.  It demonstrates the overhead involved in matching the simplest regular expression.  Date, Email, and URIOrEmail provide examples of common uses for regular expression matching.
14
15
16
17
18
19\begin{table*}[htbp]
20\begin{center}
21{
22\footnotesize
23\begin{tabular}{|l|l|}
24\hline
25Name            & Expression    \\ \hline
26@               & \verb@              \\ \hline
27Date            & \verb([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)          \\ \hline
28Email           & \verb([^ @]+)@([^ @]+)              \\ \hline
29URIOrEmail      & \verb([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)           \\ \hline
30Xquote          & \verb["']|&quot;|&apos;|&#0*3[49];|&#x0*2[27];              \\ \hline
31\end{tabular}
32}
33\end{center}
34\caption{Regular Expressions}
35\label{RegularExpressions}
36\end{table*}
37
38
39
40
41
42
43
44\subsection{Comparison}
45
46Figure \ref{fig:SSECyclesPerByte} shows cycles per byte.  For the three most complicated expressions, the bitstreams implementation had the lowest cycle count.
47
48For the @ expression, Grep had very slightly better performance than the bitstreams implementation.  The bitstreams implementation has a fair amount of overhead for transposition that hurts relative performance for very simple expressions.
49
50For the Date expression, NRGrep is able to skip large portions of the input file since every time it encounters a character that can't appear in a date, it can skip past six characters.  For the more compicated expressions, it loses this advantage.
51
52The bitstreams implementation has fairly consistent performance.  As the regular expression complexity increases, the cycle count increases slowly.  The largest difference in cycles per byte for the bitstreams implementation is a ratio of 2 to 1.  The same cannot be said of Grep or NRGrep.  NRGrep uses more than 10 times the cycles per byte for Xquote than for Date.  The number of cycles per byte that Grep uses for URIOrEmail is almost 900 times as many as it uses for @.
53
54\begin{figure}
55\begin{center}
56\begin{tikzpicture}
57\begin{axis}[
58xtick=data,
59ylabel=Cycles per Byte,
60xticklabels={@,Date,Email,URIorEmail,xquote},
61tick label style={font=\tiny},
62enlarge x limits=0.15,
63enlarge y limits={0.15, upper},
64ymin=0,
65legend style={at={(0.5,-0.15)},
66anchor=north,legend columns=-1},
67ymax=12,
68ybar,
69bar width=7pt,
70visualization depends on=y \as \rawy,
71]
73file {data/cycles1.dat};
75file {data/cycles2.dat};
77file {data/cycles3.dat};
78
79\legend{Bitstreams,NRGrep,Grep,Annot}
80\end{axis}
81\end{tikzpicture}
82\end{center}
83\caption{Cycles per Byte}\label{fig:SSECyclesPerByte}
84\end{figure}
85
86Figure \ref{fig:SSEInstructionsPerByte} shows instructions per byte.  The relative values mirror cycles per byte.  The bitstreams implementation continues to show consistent performance.  This is especially noticeable in Figure \ref{fig:SSEInstructionsPerCycle}, which shows instructions per cycle.  The bitstreams implementation has almost no variation in the instructions per cycle.  Both Grep and NRGrep have considerably more variation based on the input regular expression.
87
88\begin{figure}
89\begin{center}
90\begin{tikzpicture}
91\begin{axis}[
92xtick=data,
93ylabel=Instructions per Byte,
94xticklabels={@,Date,Email,URIorEmail,xquote},
95tick label style={font=\tiny},
96enlarge x limits=0.15,
97enlarge y limits={0.15, upper},
98ymin=0,
99legend style={at={(0.5,-0.15)},
100anchor=north,legend columns=-1},
101ymax=25,
102ybar,
103bar width=7pt,
104]
106file {data/instructions1.dat};
108file {data/instructions2.dat};
110file {data/instructions3.dat};
111
112\legend{Bitstreams,NRGrep,Grep,Annot}
113\end{axis}
114\end{tikzpicture}
115\end{center}
116\caption{Instructions per Byte}\label{fig:SSEInstructionsPerByte}
117\end{figure}
118
119
120\begin{figure}
121\begin{center}
122\begin{tikzpicture}
123\begin{axis}[
124xtick=data,
125ylabel=Instructions per Cycle,
126xticklabels={@,Date,Email,URIorEmail,xquote},
127tick label style={font=\tiny},
128enlarge x limits=0.15,
129enlarge y limits={0.15, upper},
130ymin=0,
131legend style={at={(0.5,-0.15)},
132anchor=north,legend columns=-1},
133ybar,
134bar width=7pt,
135]
137file {data/ipc1.dat};
139file {data/ipc2.dat};
141file {data/ipc3.dat};
142
143\legend{Bitstreams,NRGrep,Grep,Annot}
144\end{axis}
145\end{tikzpicture}
146\end{center}
147\caption{Instructions per Cycle}\label{fig:SSEInstructionsPerCycle}
148\end{figure}
149
150Figure \ref{fig:SSEBranchMisses} shows the branch misses per kilobyte.  The bitstreams implementation remains consistent here.  NRGrep and Grep have branch miss rates that vary significantly with different regular expressions.
151
152Overall, our performance is considerably better than both NRGrep and Grep for the more complicated expressions that were tested.  Also, our performance scales smoothly with regular expression complexity so it can be expected to remain better for complicated expressions in general.
153
154\begin{figure}
155\begin{center}
156\begin{tikzpicture}
157\begin{axis}[
158xtick=data,
159ylabel=Branch Misses per Kilobyte,
160xticklabels={@,Date,Email,URIorEmail,xquote},
161tick label style={font=\tiny},
162enlarge x limits=0.15,
163enlarge y limits={0.15, upper},
164ymin=0,
165legend style={at={(0.5,-0.15)},
166anchor=north,legend columns=-1},
167ybar,
168ymax=40,
169bar width=7pt,
170]
172file {data/branch-misses1.dat};