# Changeset 3502 for docs/Working/re

Ignore:
Timestamp:
Sep 15, 2013, 4:38:43 PM (6 years ago)
Message:

Updates to section 1; analysis section

Location:
docs/Working/re
Files:
 r3501 addition techniques for 256-bit addition with AVX2 and 4096-bit additions with GPGPU SIMT. Section \ref{sec:analysis} Section \ref{sec:SSE2} Section \ref{sec:AVX2} Section \ref{sec:GPU} Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work. Section \ref{sec:SSE2} describes our overall SSE2 implementation and carries out a performance study in comparison with existing grep implementations. Given the dramatic variation in grep performance across different implementation techniques, expressions and data sets, Section \ref{sec:analysis} considers a comparison between the bit-stream and NFA approaches from a theoretical perspective. Section \ref{sec:AVX2} then examines and demonstrates the scalability of our bitwise data-parallel approach in moving from 128-bit to 256-bit SIMD on Intel Haswell architecture. To further investigate scalability, Section \ref{sec:GPU} addresses the implementation of our matcher using groups of 64 threads working together SIMT-style on a GPGPU system. Section \ref{sec:Concl} concludes the paper with a discussion of results and areas for future work. \section{Regular Expression Notation and Grep}\label{sec:grep} of characters in class $C$ from each position in $M$. \paragraph*{Compilation Algorithm.} \input{compilation} \section{Block-at-a-Time Processing}\label{sec:blockwise} expression matching as shown herein, it seems reasonable to expect such instructions to become available. \raggedbottom \section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis} \begin{enumerate} \item Operations \item Memory behaviour per input byte: note tables of DFA/NFA. Bille and Throup \em{Faster regular expression matching}\cite{bille2009faster} \end{enumerate} \input{sse2} \input{analysis} \input{avx2}