Changeset 3880 for docs


Ignore:
Timestamp:
Jun 17, 2014, 7:55:53 PM (5 years ago)
Author:
cameron
Message:

Various formatting items

Location:
docs/Working/re
Files:
7 edited

Legend:

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

    r3875 r3880  
    1717
    1818
    19 \paragraph*{AVX2 256-Bit Addition}
    2019 \begin{figure}[tbh]
    2120
     
    3433\end{figure}
    3534
    36 Bitstream addition at the 256-bit block size was implemented using the
     35\paragraph*{AVX2 256-Bit Addition} Bitstream addition at the 256-bit block size was implemented using the
    3736long-stream addition technique.   The AVX2 instruction set directly
    3837supports the \verb#hsimd<64>::mask(X)# operation using
  • docs/Working/re/compilation.tex

    r3876 r3880  
    1 \paragraph{Compilation}
    2 
    3 Using the marker stream and MatchStar concept, we now
     1\paragraph*{Compilation} Using the marker stream and MatchStar concept, we now
    42outline our compilation algorithm.  This is implemented
    53in a Java program.   First the regular expression is
  • docs/Working/re/conclusion.tex

    r3870 r3880  
    11\section{Discussion}\label{sec:Concl}
    2 \paragraph*{Contributions}
    3 A new class of regular expression matching algorithm has been
     2\paragraph*{Contributions} A new class of regular expression matching algorithm has been
    43introduced based on the concept of bit-parallel data streams
    54together with the MatchStar operation.  The algorithm is
     
    2928effort.
    3029
    31 \paragraph{Related Work}
    32 Much of the previous work in parallelizing of regular processing
     30\paragraph*{Related Work} Much of the previous work in parallelizing of regular processing
    3331has dealt with the problem of using parallel resources to handle
    3432multiple instances of a matching problem in parallel.   It is thus
     
    7573of 5X or more.
    7674
    77 \paragraph*{Ongoing and Future Work}
    78 
    79 Based on the techniques presented here a fully integrated
     75\paragraph*{Ongoing and Future Work} Based on the techniques presented here a fully integrated
    8076grep version with a dynamic code generator implemented with LLVM
    8177is being developed by another team working with the Parabix
  • docs/Working/re/pact051-cameron.tex

    r3878 r3880  
    4343%
    4444% 1st. author
    45 \alignauthor
    46 Rob Cameron\\
     45%\alignauthor
     46Rob Cameron, Tom Shermer, Arrvindh Shriraman, Ken Herdy, Dan Lin, Ben Hull, Meng Lin\\
    4747       \affaddr{School of Computing Science}\\
    4848       \affaddr{Simon Fraser University}\\
    4949       \affaddr{Surrey, British Columbia}\\
    50        \email{cameron@cs.sfu.ca}
    51 % 2nd. author
    52 \alignauthor
    53 Tom Shermer\\
    54        \affaddr{School of Computing Science}\\
    55        \affaddr{Simon Fraser University}\\
    56        \affaddr{Surrey, British Columbia}\\
    57        \email{shermer@cs.sfu.ca}
    58 % 3rd. author
    59 \alignauthor Arrvindh Shriraman\\
    60        \affaddr{School of Computing Science}\\
    61        \affaddr{Simon Fraser University}\\
    62        \affaddr{Surrey, British Columbia}\\
    63        \email{ashriram@cs.sfu.ca}
    64 \and  % use '\and' if you need 'another row' of author names
    65 % 4th. author
    66 \alignauthor Ken Herdy\\
    67        \affaddr{School of Computing Science}\\
    68        \affaddr{Simon Fraser University}\\
    69        \affaddr{Surrey, British Columbia}\\
    70        \email{ksherdy@sfu.ca}
    71 % 5th. author
    72 \alignauthor Dan Lin\\
    73        \affaddr{School of Computing Science}\\
    74        \affaddr{Simon Fraser University}\\
    75        \affaddr{Surrey, British Columbia}\\
    76        \email{lindanl@sfu.ca}
    77 % 6th. author
    78 \alignauthor Ben Hull\\
    79        \affaddr{School of Computing Science}\\
    80        \affaddr{Simon Fraser University}\\
    81        \affaddr{Surrey, British Columbia}\\
    82        \email{bhull@sfu.ca}
    83 % 7th. author
    84 \alignauthor Meng Lin\\
    85        \affaddr{School of Computing Science}\\
    86        \affaddr{Simon Fraser University}\\
    87        \affaddr{Surrey, British Columbia}\\
    88        \email{linmengl@sfu.ca}
     50       \email{\{cameron,shermer,ashrira,ksherdy,lindanl,bhull,linmengl\}@sfu.ca}
    8951}
    90 % There's nothing stopping you putting the seventh, eighth, etc.
    91 % author on the opening page (as the 'third row') but we ask,
    92 % for aesthetic reasons that you place these 'additional authors'
    93 % in the \additional authors block, viz.
    94 %\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
    95 %email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
    96 %(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
    97 %\date{30 July 1999}
    98 % Just remember to make sure that the TOTAL number of authors
    99 % is the number that will appear on the first page PLUS the
    100 % number that will appear in the \additionalauthors section.
    10152
    10253
     
    452403
    453404
    454 \paragraph*{MatchStar}
    455 MatchStar takes a marker bitstream and a character class bitstream as input.  It returns all positions that can be reached by advancing the marker bitstream zero or more times through the character class bitstream.
     405\paragraph*{MatchStar}  MatchStar takes a marker bitstream and a character class bitstream as input.  It returns all positions that can be reached by advancing the marker bitstream zero or more times through the character class bitstream.
    456406
    457407\begin{figure}[tbh]
     
    636586and then extracting the carry-out {\tt q} from the high bit position.
    637587\[\text{\tt i} = \text{\tt MatchStar(c*2+p, b)}\]
    638 \[\text{\tt q} = \text{\tt i >> f}\]
     588\[\text{\tt q} = \text{verb:i >> f:}\]
    639589
    640590As described subsequently, we use a two-level long-stream addition technique
  • docs/Working/re/re-Unicode.tex

    r3876 r3880  
    1 \paragraph*{Unicode}
    2 
    3 The introduction of Unicode as a common encoding system including
     1\paragraph*{Unicode}  The introduction of Unicode as a common encoding system including
    42the characters of all the world's written languages and notation
    53systems has introduced some complexity for regular expression matching
  • docs/Working/re/sse2.tex

    r3876 r3880  
    2222
    2323
    24 \paragraph{Implementation Notes}
    25 Our regular expression compiler directly uses the Parabix tool chain
     24\paragraph*{Implementation Notes} Our regular expression compiler directly uses the Parabix tool chain
    2625to compile regular expression into SSE2-based implementations.
    2726Our compiler essentially scripts three other compilers to perform
     
    3534as they are encountered.
    3635
    37 \paragraph{Comparative Implementations}
    38 We evaluate our bitwise data parallel implementation versus several
     36\paragraph*{Comparative Implementations} We evaluate our bitwise data parallel implementation versus several
    3937alternatives.   
    4038We report data for two of these:
     
    7068
    7169
    72 \paragraph{Test Expressions}
    73 Each grep implementation was evaluated
     70\paragraph*{Test Expressions} Each grep implementation was evaluated
    7471against the five regular expressions shown
    7572in Table \ref{RegularExpressions}. 
     
    7875in matching the simplest possible regular expression, a single character.
    7976Date, Email, and URIOrEmail provide examples of commonly used regular expression.
    80 This set of expressions were drawn from the \textit{Benchmark of Regex
     77This set of expressions were modified from the \textit{Benchmark of Regex
    8178Libraries} (http://lh3lh3.users.sourceforge.net/reb.shtml).
    8279HexBytes matches delimited byte strings in hexadecimal notation, and
     
    8481expression illustrates the performance
    8582of a repetition operator implemented using
    86 a while loop.
     83a while loop.  StarHeight is an expression designed to further
     84stress our while loop implementation with 4 levels of Kleene closure.
    8785All tests were run on a version
    8886of a \textit{Linux 3Dfx howto}
     
    9189
    9290
    93 \paragraph{Results}
     91\paragraph*{Results}
    9492\begin{figure}
    9593\begin{center}
Note: See TracChangeset for help on using the changeset viewer.