Changeset 4084 for docs/Working


Ignore:
Timestamp:
Aug 25, 2014, 3:34:16 PM (5 years ago)
Author:
cameron
Message:

Final version

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/Slides/pactslides.tex

    r4083 r4084  
    3737
    3838\begin{block}<+->{Sequential Matching Problems}
    39 \begin{itemize}[<+->]
     39\begin{itemize}%[<+->]
    4040\item Example: quickly find instances of \verb:(^|[ ])\p{Lu}\p{Ll}+[.!?]($|[ ]): in text.
    4141\item Three families of sequential algorithms: NFAs, DFAs or backtracking.
     
    4949\item Embarassingly sequential?
    5050\end{itemize}
    51 \item Parallel application of FSMs to multiple input streams (SIMD/GPU).
    52 \item Promising recent work: coalesced FSMs, principled speculation.
     51\item Parallel application of FSMs to multiple input streams.
     52\item Recent advances: coalesced FSMs, principled speculation.
    5353\end{itemize}
    5454\end{block}
     
    5959\frametitle{Our Approach}
    6060
    61 \begin{itemize}[<+->]
     61\begin{itemize}%[<+->]
    6262\item A fundamentally parallel approach in contrast to approaches
    6363that parallelize existing DFA or NFA algorithms.
     
    7373of character class repetitions using bitstream addition.
    7474
    75 \item Compilation technologies for regular expressions (new), character classes (existing),
    76 unbounded bitstreams (existing).
     75\item Adds compilation technologies for regular expressions to Parabix
     76  technology.
    7777
    7878\item Recent work: all compilers integrated together with LLVM for
     
    8484\frametitle{Bitwise Data Parallelism}
    8585
    86 \begin{itemize}[<+->]
     86\begin{itemize}%[<+->]
    8787\item Parabix methods use a transform representation of text.
    8888\item Bitstreams are formed using one bit per input byte.
     
    103103
    104104\begin{itemize}%[<+->]
    105 \item \verb:(^|[ ])\p{Lu}\p{Ll}+[.!?]($|[ ]):
    106 \begin{itemize}
    107 \item Match against 110 MB Arabic wikimedia document.
     105\item Example: \verb:(^|[ ])\p{Lu}\p{Ll}+[.!?]($|[ ]):
     106\begin{itemize}
    108107\item Find capitalized words at ends of sentences.
    109108\item Use Unicode upper/lower case categories.
     109\item Match against 110 MB Arabic wikimedia document.
    110110\end{itemize}
    111111\item \verb:egrep: 45,951,194,784 CPU cycles.
     
    143143\frametitle{Parabix Programming}
    144144
    145 \begin{itemize}[<+->]
     145\begin{block}<+->{Programmer View}
     146
     147\begin{itemize}%[<+->]
    146148\item Parabix programs written as unbounded bit stream operations.
    147149\item Unbounded bit streams considered as arbitrarily large integers.
    148 \item Fundamental operations: bitwise logic, bit-stream shifting and long-stream addition.
    149 \item Parabix tool chain has three components:
     150\item Fundamental operations: bitwise logic, bit-stream advance (shift) and
     151  long-stream addition.
     152\end{itemize}
     153\end{block}
     154\begin{block}<+->{Parabix Tool Chain}
    150155\begin{itemize}
    151156\item Character Class Compiler (CCC) produces stream equations from character classes.
     
    153158\item Portable SIMD library for multiple architectures.
    154159\end{itemize}
    155 \end{itemize}
     160\end{block}
    156161\end{frame}
    157162
    158163\begin{frame}[fragile]
    159164\frametitle{Character Class Formation}
    160 \begin{itemize}[<+->]
     165\begin{itemize}%[<+->]
    161166\item Combining 8 bits of a code unit gives a character class stream.
    162167\item CCC({\tt cc\_a = [a]})
     
    216221\begin{frame}[fragile]
    217222\frametitle{Marker Streams}
    218 \begin{itemize}[<+->]
     223\begin{itemize}%[<+->]
    219224\item Marker stream $M_i$ indicates the positions that are reachable after item $i$ in the regular expression.
    220225\item Each marker stream $M_i$ has one bit for every input byte in the input file.
     
    348353\begin{frame}[fragile]
    349354\frametitle{Long-Stream Addition}
    350 \begin{itemize}[<+->]
     355\begin{itemize}%[<+->]
    351356\item Processors limit addition to 64 bits.
    352357\item SIMD blocks may be 128, 256 or (soon) 512 bits.
     
    376381\alert<4>{\tt c} (carries)& {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} & \alert<4>{\tt 1} & {\tt 0} & {\tt 0} & \alert<4>{\tt 1} \\ \cline{2-9}
    377382{\tt c*2} (shift left 1)& {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} \\ \cline{2-9}
    378 {\tt b} (bubble ({\tt Z} = {\tt FF}) & {\tt 0} & {\tt 0} & \alert<5>{\tt 1} & \alert<5>{\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
     383\alert<5>{\tt b} (bubble ({\tt Z} = {\tt FF}) & {\tt 0} & {\tt 0} & \alert<5>{\tt 1} & \alert<5>{\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
    379384\alert<6>{\tt i} = Matchstar({\tt b},{\tt c*2})& {\tt 0} & \alert<6>{\tt 1} &\alert<6> {\tt 1} & \alert<6>{\tt 1} & {\tt 0} & {\tt 0} & \alert<6>{\tt 1} & {\tt 0} \\ \cline{2-9}
    380385\alert<7>{\tt Z} = {\tt R} + {\tt i} & {\tt 3B} &  \alert<7>{\tt 44} & \alert<7>{\tt 0} & \alert<7>{\tt 0} & {\tt 1F} & {\tt 5B} & \alert<7>{\tt 39} & {\tt 27} \\ \cline{2-9}
     
    386391
    387392
    388 \begin{frame}[fragile]
    389 \frametitle{Test Expressions}
     393
     394
     395
     396\begin{frame}[fragile]
     397\frametitle{Experimental Evaluation}
     398\begin{block}<+->{Compare Parabix grep vs. Alternatives}
     399\begin{itemize}
     400\item nrgrep (NFA-based)
     401\item re2grep (DFA-based)
     402\item GNU egrep, pcregrep
     403\end{itemize}
     404\end{block}
     405\begin{block}<+->{Test Expressions}
    390406
    391407
    392408{\tiny
    393 \begin{tabular}{|l|l|}
     409\begin{tabular}{c|c}
    394410\hline
    395411Name            & Expression    \\ \hline   
     
    399415URI     & \verb`(([a-zA-Z][a-zA-Z0-9]*)://|mailto:)([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)`         \\ \hline     
    400416Hex             & \verb`[ ](0x)?([a-fA-F0-9][a-fA-F0-9])+[.:,?! ]`              \\ \hline
    401 StarHeight              & \verb`[A-Z]((([a-zA-Z]*a[a-zA-Z]*[ ])*[a-zA-Z]*e[a-zA-Z]*[ ])*[a-zA-Z]*s[a-zA-Z]*[ ])*[.?!]`          \\ \hline
     417StarHt          & \verb`[A-Z]((([a-zA-Z]*a[a-zA-Z]*[ ])*[a-zA-Z]*e[a-zA-Z]*[ ])*[a-zA-Z]*s[a-zA-Z]*[ ])*[.?!]`          \\ \hline
    402418\end{tabular}
    403419}
     420\end{block}
     421
    404422\end{frame}
    405423
Note: See TracChangeset for help on using the changeset viewer.