Changeset 3502


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

Updates to section 1; analysis section

Location:
docs/Working/re
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/ppopp-re.tex

    r3501 r3502  
    203203addition techniques for 256-bit addition with AVX2 and
    2042044096-bit additions with GPGPU SIMT.
    205 Section \ref{sec:analysis}
    206 Section \ref{sec:SSE2}
    207 Section \ref{sec:AVX2}
    208 Section \ref{sec:GPU}
    209 Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work.
     205Section \ref{sec:SSE2} describes our overall SSE2 implementation
     206and carries out a performance study in comparison with
     207existing grep implementations.
     208Given the dramatic variation in grep performance across
     209different implementation techniques, expressions and data sets,
     210Section \ref{sec:analysis} considers a comparison between
     211the bit-stream and NFA approaches from a theoretical perspective.
     212Section \ref{sec:AVX2} then examines and demonstrates
     213the scalability of our
     214bitwise data-parallel approach in moving from
     215128-bit to 256-bit SIMD on Intel Haswell architecture.
     216To further investigate scalability, Section \ref{sec:GPU}
     217addresses the implementation of our matcher using
     218groups of 64 threads working together SIMT-style on a GPGPU system.
     219Section \ref{sec:Concl} concludes the paper with a discussion of results and
     220areas for future work.
    210221
    211222\section{Regular Expression Notation and Grep}\label{sec:grep}
     
    427438of characters in class $C$ from each position in $M$. 
    428439
    429 \paragraph*{Compilation Algorithm.}
    430 
     440\input{compilation}
    431441
    432442\section{Block-at-a-Time Processing}\label{sec:blockwise}
     
    562572expression matching as shown herein, it seems reasonable to expect
    563573such instructions to become available.
    564 \raggedbottom
    565 \section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis}
    566 
    567 \begin{enumerate}
    568 \item Operations
    569 \item Memory behaviour per input byte: note tables of DFA/NFA.
    570 
    571 Bille and Throup \em{Faster regular expression matching}\cite{bille2009faster}
    572 
    573 \end{enumerate}
    574574
    575575
    576576\input{sse2}
     577
     578\input{analysis}
    577579
    578580\input{avx2}
Note: See TracChangeset for help on using the changeset viewer.