Ignore:
Timestamp:
Feb 24, 2014, 2:24:02 AM (5 years ago)
Author:
cameron
Message:

Substitute gre2p for grep; cite GPU long-stream add; remove excess figures

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/sse2.tex

    r3637 r3642  
    11\section{SSE2 Implementation and Evaluation}\label{sec:SSE2}
     2
     3\begin{table*}[htbp]
     4\begin{center}
     5{
     6\footnotesize
     7\begin{tabular}{|l|l|}
     8\hline
     9Name            & Expression    \\ \hline   
     10@               & \verb`@`              \\ \hline     
     11Date            & \verb`([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)`          \\ \hline     
     12Email           & \verb`([^ @]+)@([^ @]+)`              \\ \hline
     13URIOrEmail      & \verb`([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)`           \\ \hline     
     14HexBytes                & \verb`(^|[ ])0x([a-fA-F0-9][a-fA-F0-9])+[.:,?!]?($|[ ])`              \\ \hline
     15\end{tabular}
     16}
     17\end{center}
     18\caption{Regular Expressions}
     19\label{RegularExpressions}
     20\end{table*}
     21
    222
    323\paragraph{Implementation Notes.}
     
    1535
    1636\paragraph{Comparative Implementations.}
    17 We evaluate our bitwise data parallel implementation versus several alternatives.   We report data for two of these: GNU grep version 2.10
    18 and nrgrep version 1.12. GNU grep is a popular open-source grep implementation that uses DFAs,
    19 as well as heuristics for important special cases.
     37We evaluate our bitwise data parallel implementation versus several
     38alternatives.   
     39We report data for two of these:
     40gre2p
     41%GNU grep version 2.10
     42and nrgrep version 1.12.
     43The gre2p program is a grep version implemented using the recently developed
     44RE2 regular expression library, using a systematic DFA-based approach
     45(as well as some NFA fallback techniques) \cite{cox2010RE2}.
    2046The NFA class is represented by nrgrep, one of the
    2147strongest competitors in regular expression matching performance.
    22 We also considered agrep 3.41 as and alternative NFA-based implementation
     48We also considered GNU grep 2.10, agrep 3.41 as and alternative NFA-based implementation
    2349and pcregrep 8.12 as a backtracking implementation, but do not
    24 report data for them.  The agrep implementation does not support
     50report data for them. 
     51GNU grep is a popular open-source implementation that is claimed to be
     52primarily DFA-based with
     53heuristics for important special cases.   
     54The agrep implementation does not support
    2555some of the common regular expression syntax feature and is limited to
    2656patterns of at most 32 characters.   As a backtracking implementation,
     
    2959
    3060We performed our SSE2 performance study using an Intel Core i7 quad-core (Sandy Bridge) processor (3.40GHz, 4 physical cores, 8 threads (2 per core), 32+32 kB (per core) L1 cache, 256 kB (per core) L2 cache, 8 MB L3 cache) running the 64-bit version of Ubuntu 12.04 (Linux).
    31 
    32 \begin{table*}[htbp]
    33 \begin{center}
    34 {
    35 \footnotesize
    36 \begin{tabular}{|l|l|}
    37 \hline
    38 Name            & Expression    \\ \hline   
    39 @               & \verb`@`              \\ \hline     
    40 Date            & \verb`([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)`          \\ \hline     
    41 Email           & \verb`([^ @]+)@([^ @]+)`              \\ \hline
    42 URIOrEmail      & \verb`([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)`           \\ \hline     
    43 HexBytes                & \verb`(^|[ ])0x([a-fA-F0-9][a-fA-F0-9])+[.:,?!]?($|[ ])`              \\ \hline
    44 \end{tabular}
    45 }
    46 \end{center}
    47 \caption{Regular Expressions}
    48 \label{RegularExpressions}
    49 \end{table*}
    5061
    5162
     
    8899file {data/cycles3.dat};
    89100 
    90 \legend{Bitstreams,NRGrep,Grep,Annot}
     101\legend{Bitstreams,NRGrep,Gre2p,Annot}
    91102\end{axis}
    92103\end{tikzpicture}
     
    131142file {data/instructions3.dat};
    132143 
    133 \legend{Bitstreams,NRGrep,Grep,Annot}
     144\legend{Bitstreams,NRGrep,Gre2p,Annot}
    134145\end{axis}
    135146\end{tikzpicture}
     
    171182file {data/ipc3.dat};
    172183
    173 \legend{Bitstreams,NRGrep,Grep,Annot}
     184\legend{Bitstreams,NRGrep,Gre2p,Annot}
    174185\end{axis}
    175186\end{tikzpicture}
     
    201212file {data/branch-misses3.dat};
    202213
    203 \legend{Bitstreams,NRGrep,Grep,Annot}
     214\legend{Bitstreams,NRGrep,Gre2p,Annot}
    204215\end{axis}
    205216\end{tikzpicture}
Note: See TracChangeset for help on using the changeset viewer.