Changeset 4083 for docs


Ignore:
Timestamp:
Aug 25, 2014, 7:20:36 AM (4 years ago)
Author:
cameron
Message:

Updates

File:
1 edited

Legend:

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

    r4082 r4083  
    3636\frametitle{Acceleration of Regular Expression Matching}
    3737
     38\begin{block}<+->{Sequential Matching Problems}
    3839\begin{itemize}[<+->]
    3940\item Example: quickly find instances of \verb:(^|[ ])\p{Lu}\p{Ll}+[.!?]($|[ ]): in text.
    40 \item Sequential algorithms use finite automata or backtracking.
    41 \item Parallelizing these approaches is difficult.
    42 \begin{itemize}
    43 \item Finite state machines are the 13th (and hardest) ``dwarf'' in the Berkeley Landscape of Parallel Computing Research.
     41\item Three families of sequential algorithms: NFAs, DFAs or backtracking.
     42\end{itemize}
     43\end{block}
     44\begin{block}<+->{Parallelization}
     45\begin{itemize}
     46\item Berkeley ParLab:
     47\begin{itemize}
     48\item FSMs are 13th dwarf: hardest to parallelize.
    4449\item Embarassingly sequential?
    45 \item Some success in parallel application of FSMs to multiple input streams.
    46 \item Recent work shows some promise using techniques such as coalesced FSMs and principled speculation.
    47 \end{itemize}
    48 \end{itemize}
     50\end{itemize}
     51\item Parallel application of FSMs to multiple input streams (SIMD/GPU).
     52\item Promising recent work: coalesced FSMs, principled speculation.
     53\end{itemize}
     54\end{block}
    4955\end{frame}
    5056
     
    96102\frametitle{Impressive Results in Full Unicode Matching}
    97103
    98 \begin{itemize}[<+->]
     104\begin{itemize}%[<+->]
    99105\item \verb:(^|[ ])\p{Lu}\p{Ll}+[.!?]($|[ ]):
    100106\begin{itemize}
     
    171177\begin{frame}[fragile]
    172178\frametitle{Character Class Ranges}
    173 \begin{itemize}[<+->]
     179\begin{itemize}%[<+->]
    174180\item Ranges of characters are often very simple to compute.
    175181\item CCC({\tt cc\_0\_9 = [0-9]})
     
    342348\begin{frame}[fragile]
    343349\frametitle{Long-Stream Addition}
     350\begin{itemize}[<+->]
     351\item Processors limit addition to 64 bits.
     352\item SIMD blocks may be 128, 256 or (soon) 512 bits.
     353\item Addition traditionally requires sequential propagation of
     354  carries between 64-bit fields.
     355\item However, a parallel method is possible.
     356\begin{itemize}
     357\item Extract one carry and one ``bubble'' bit each from 64-bit
     358  fields.
     359\item Apply MatchStar to produce a mask of ``increment'' bits.
     360\item Spread the increment bits to the 64-bit fields and add.
     361\end{itemize}
     362\item Potentially supports 4096 bit addition using 64-bit adders.
     363\end{itemize}
     364\end{frame}
     365
     366\begin{frame}[fragile]
     367\frametitle{Long-Stream Addition}
    344368Compute the long-stream sum {\tt Z} = {\tt X} + {\tt Y}.
    345369\begin{tabular}{c||r|r|r|r|r|r|r|r||}\cline{2-9}
    346370{\tt X} & {\tt 19} & {\tt 31} & {\tt BA} & {\tt 4C} & {\tt 3D} & {\tt 45} & {\tt 21} & {\tt F1} \\ \cline{2-9}
    347371{\tt Y} & {\tt 22} & {\tt 12} & {\tt 45} & {\tt B3} & {\tt E2} & {\tt 16} & {\tt 17} & {\tt 36} \\ \cline{2-9}
    348 \onslide<2->{\tt R} (add digits)& {\tt 3B} & {\tt 43} & {\tt FF} & {\tt FF} & {\tt 1F} & {\tt 5B} & {\tt 38} & {\tt 27} \\ \cline{2-9}
    349 \onslide<2->{\tt x} = high\_bit({\tt X})& {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} \\ \cline{2-9}
    350 \onslide<2->{\tt y} = high\_bit({\tt Y}) & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
    351 \onslide<2->{\tt r} = high\_bit({\tt Z}) & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
    352 \onslide<3->{\tt c} (carries)& {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 1} \\ \cline{2-9}
    353 \onslide<4->{\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}
    354 \onslide<5->{\tt b} (bubble ({\tt Z} = {\tt FF}) & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
    355 \onslide<6->{\tt i} = Matchstar({\tt b},{\tt c*2})& {\tt 0} & {\tt 1} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} \\ \cline{2-9}
    356 \onslide<7->{\tt Z} = {\tt R} + {\tt i} & {\tt 3B} & {\tt 44} & {\tt 0} & {\tt 0} & {\tt 1F} & {\tt 5B} & {\tt 39} & {\tt 27} \\ \cline{2-9}
     372\alert<3>{\tt R} (add digits)& {\tt 3B} & {\tt 43} & \alert<3>{\tt FF} & \alert<3>{\tt FF} & {\tt 1F} & {\tt 5B} & {\tt 38} & {\tt 27} \\ \cline{2-9}
     373{\tt x} = high\_bit({\tt X})& {\tt 0} & {\tt 0} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} \\ \cline{2-9}
     374{\tt y} = high\_bit({\tt Y}) & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
     375{\tt r} = high\_bit({\tt Z}) & {\tt 0} & {\tt 0} & {\tt 1} & {\tt 1} & {\tt 0} & {\tt 0} & {\tt 0} & {\tt 0} \\ \cline{2-9}
     376\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}
     377{\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}
     379\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}
     380\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}
    357381\end{tabular}
    358382\end{frame}
Note: See TracChangeset for help on using the changeset viewer.