Changeset 3637 for docs


Ignore:
Timestamp:
Feb 22, 2014, 5:09:56 PM (5 years ago)
Author:
cameron
Message:

Replace xquote with HexBytes?; various cleanups

Location:
docs/Working/re
Files:
3 edited

Legend:

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

    r3625 r3637  
    5858xtick=data,
    5959ylabel=AVX2 Instruction Reduction,
    60 xticklabels={@,Date,Email,URIorEmail,xquote},
     60xticklabels={@,Date,Email,URIorEmail,HexBytes},
    6161tick label style={font=\tiny},
    6262enlarge x limits=0.15,
     
    109109xtick=data,
    110110ylabel=AVX2 Speedup,
    111 xticklabels={@,Date,Email,URIorEmail,xquote},
     111xticklabels={@,Date,Email,URIorEmail,HexBytes},
    112112tick label style={font=\tiny},
    113113enlarge x limits=0.15,
     
    134134
    135135As shown in Figure \ref{fig:AVXSpeedup} the reduction in
    136 instruction count was reflected in a considerable speed-up
     136instruction count was reflected in a significant speed-up
    137137in the bitstreams implementation.  However, the speed-up was
    138138considerably less than expected.  As shown in \ref{fig:AVXIPC}
     
    148148xtick=data,
    149149ylabel=Change in Instructions per Cycle,
    150 xticklabels={@,Date,Email,URIorEmail,xquote},
     150xticklabels={@,Date,Email,URIorEmail,HexBytes},
    151151tick label style={font=\tiny},
    152152enlarge x limits=0.15,
  • docs/Working/re/re-main.tex

    r3636 r3637  
    586586the 64 work groups.  Each work group carries out the regular
    587587expression matching operations 4096 bytes at a time using SIMT
    588 processing.  Figure \ref{fig:GPUadd} shows our implementation
    589 of long-stream addition on the GPU.  Each thread maintains
    590 its own carry and bubble values in shared memroy and performs
     588processing.   We were able to adapt our long-stream addition
     589model to the GPU as shown in Figure \ref{fig:GPUadd}.  The GPU
     590does not directly support the mask and spread operations,
     591but we are able to simulate them using shared memory.
     592Each thread maintains
     593its own carry and bubble values in shared memory and performs
    591594synchronized updates with the other threads using a six-step
    592 parallel-prefix style process.
     595parallel-prefix style process.  Others have implemented
     596long-stream addition on the GPU using similar techniques.
    593597
    594598
     
    599603and also accessed by GPU for further processing. Therefore,
    600604the expensive data transferring time that needed by traditional
    601 discrete GPUs is hinden and we compare only the kernel execution
    602 time with our SSE2 and AVX mplementations as shown in Figure
     605discrete GPUs is hidden and we compare only the kernel execution
     606time with our SSE2 and AVX implementations as shown in Figure
    603607\ref{fig:SSE-AVX-GPU}. The GPU version gives 30\% to 55\% performance
    604608improvement over SSE version and 10\% to 40\% performance
     
    616620further processing rather than jump to the next block with a
    617621simple IF test. Therefore, the performance of different
    618 regular expresions is depended on the number of function calls
    619 to the long-stream addition and the total number of matches
     622regular expresions is dependent on the number of
     623long-stream addition operations and the total number of matches
    620624of a given input.
    621625
     
    665669xtick=data,
    666670ylabel=Running Time (ms per megabyte),
    667 xticklabels={@,Date,Email,URIorEmail,xquote},
     671xticklabels={@,Date,Email,URIorEmail,HexBytes},
    668672tick label style={font=\tiny},
    669673enlarge x limits=0.15,
  • docs/Working/re/sse2.tex

    r3617 r3637  
    4141Email           & \verb`([^ @]+)@([^ @]+)`              \\ \hline
    4242URIOrEmail      & \verb`([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)`           \\ \hline     
    43 Xquote          & \verb`["']|"|'|&#0*3[49];|&#x0*2[27];`              \\ \hline
     43HexBytes                & \verb`(^|[ ])0x([a-fA-F0-9][a-fA-F0-9])+[.:,?!]?($|[ ])`              \\ \hline
    4444\end{tabular}
    4545}
     
    5151
    5252\paragraph{Test expressions.}
    53 Each grep implementation is tested with the five regular expressions in Table \ref{RegularExpressions}.  Xquote matches any of the representations of a
    54 single or double quote character occuring in XML content.  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 [http://lh3lh3.users.sourceforge.net/reb.shtml] 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.
     53Each grep implementation is tested with the five regular expressions
     54in Table \ref{RegularExpressions}.  @ 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.
     55HexBytes matches delimited. They are taken from Benchmark of Regex
     56Libraries [http://lh3lh3.users.sourceforge.net/reb.shtml].
     57HexBytes matches delimited byte strings in hexadecimal notation,
     58enforcing the constraint that the number of hex digits is even.   This
     59expression shows performance of a repetition operator implemented with
     60a while loop.
     61All tests are run on a concatenated version of the linux howto which is 39,422,105 bytes in length. 
    5562
    5663
     
    6269xtick=data,
    6370ylabel=Cycles per Byte,
    64 xticklabels={@,Date,Email,URIorEmail,xquote},
     71xticklabels={@,Date,Email,URIorEmail,HexBytes},
    6572tick label style={font=\tiny},
    6673enlarge x limits=0.15,
     
    106113xtick=data,
    107114ylabel=Instructions per Byte,
    108 xticklabels={@,Date,Email,URIorEmail,xquote},
     115xticklabels={@,Date,Email,URIorEmail,HexBytes},
    109116tick label style={font=\tiny},
    110117enlarge x limits=0.15,
     
    131138\end{figure}
    132139
    133 Figure \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.
     140Figure \ref{fig:SSEInstructionsPerByte} shows instructions per byte.
     141The relative values mirror cycles per byte.  The bitstreams
     142implementation continues to show consistent performance.  This is
     143especially noticeable in Figure \ref{fig:SSEInstructionsPerCycle},
     144which shows instructions per cycle.  The bitstreams implementation has
     145almost no variation in the instructions per cycle.  Both grep and
     146nrGrep have considerably more variation based on the input regular
     147expression.   
    134148 
    135149
     
    140154xtick=data,
    141155ylabel=Instructions per Cycle,
    142 xticklabels={@,Date,Email,URIorEmail,xquote},
     156xticklabels={@,Date,Email,URIorEmail,HexBytes},
    143157tick label style={font=\tiny},
    144158enlarge x limits=0.15,
     
    170184xtick=data,
    171185ylabel=Branch Misses per Instruction,
    172 xticklabels={@,Date,Email,URIorEmail,xquote},
     186xticklabels={@,Date,Email,URIorEmail,HexBytes},
    173187tick label style={font=\tiny},
    174188enlarge x limits=0.15,
Note: See TracChangeset for help on using the changeset viewer.