source: docs/Working/re/sse2.tex @ 3498

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

Chart changes.

File size: 4.1 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[14]. 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 1.  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`["']|"|'|&#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\begin{figure}
46\begin{center}
47\begin{tikzpicture}
48\begin{axis}[
49xtick=data,
50ylabel=Cycles per Byte,
51xticklabels={@,Date,Email,URIorEmail,xquote},
52tick label style={font=\tiny},
53enlarge x limits=0.15,
54enlarge y limits={0.15, upper},
55ymin=0,
56legend style={at={(0.5,-0.15)},
57anchor=north,legend columns=-1},
58ymax=8,
59ybar,
60bar width=7pt,
61visualization depends on=y \as \rawy,
62]
63\addplot[fill=black]
64file {data/cycles1.dat};
65\addplot[fill=gray]
66file {data/cycles2.dat};
67\addplot[fill=white]
68file {data/cycles3.dat};
69 
70\legend{Bitstreams,NRGrep,Grep,Annot}
71\end{axis}
72\end{tikzpicture}
73\end{center}
74\caption{Cycles per Byte}
75\end{figure}
76 
77\begin{figure}
78\begin{center}
79\begin{tikzpicture}
80\begin{axis}[
81xtick=data,
82ylabel=Instructions per Byte,
83xticklabels={@,Date,Email,URIorEmail,xquote},
84tick label style={font=\tiny},
85enlarge x limits=0.15,
86enlarge y limits={0.15, upper},
87ymin=0,
88legend style={at={(0.5,-0.15)},
89anchor=north,legend columns=-1},
90ymax=16,
91ybar,
92bar width=7pt,
93]
94\addplot[fill=black]
95file {data/instructions1.dat};
96\addplot[fill=gray]
97file {data/instructions2.dat};
98\addplot[fill=white]
99file {data/instructions3.dat};
100 
101\legend{Bitstreams,NRGrep,Grep,Annot}
102\end{axis}
103\end{tikzpicture}
104\end{center}
105\caption{Instructions per Byte}
106\end{figure}
107
108\begin{figure}
109\begin{center}
110\begin{tikzpicture}
111\begin{axis}[
112xtick=data,
113ylabel=Instructions per Cycle,
114xticklabels={@,Date,Email,URIorEmail,xquote},
115tick label style={font=\tiny},
116enlarge x limits=0.15,
117enlarge y limits={0.15, upper},
118ymin=0,
119legend style={at={(0.5,-0.15)},
120anchor=north,legend columns=-1},
121ybar,
122bar width=7pt,
123]
124\addplot[fill=black]
125file {data/ipc1.dat};
126\addplot[fill=gray]
127file {data/ipc2.dat};
128\addplot[fill=white]
129file {data/ipc3.dat};
130
131\legend{Bitstreams,NRGrep,Grep,Annot}
132\end{axis}
133\end{tikzpicture}
134\end{center}
135\caption{Instructions per Cycle}
136\end{figure}
137
138\begin{figure}
139\begin{center}
140\begin{tikzpicture}
141\begin{axis}[
142xtick=data,
143ylabel=Branch Misses per Byte,
144xticklabels={@,Date,Email,URIorEmail,xquote},
145tick label style={font=\tiny},
146enlarge x limits=0.15,
147enlarge y limits={0.15, upper},
148ymin=0,
149legend style={at={(0.5,-0.15)},
150anchor=north,legend columns=-1},
151ymax=0.03,
152ybar,
153bar width=7pt,
154]
155\addplot[fill=black]
156file {data/branch-misses1.dat};
157\addplot[fill=gray]
158file {data/branch-misses2.dat};
159\addplot[fill=white]
160file {data/branch-misses3.dat};
161
162\legend{Bitstreams,NRGrep,Grep,Annot}
163\end{axis}
164\end{tikzpicture}
165\end{center}
166\caption{Branch Misses per Byte}
167\end{figure}
168
Note: See TracBrowser for help on using the repository browser.