Changeset 4504

Ignore:
Timestamp:
Feb 11, 2015, 7:34:40 PM (4 years ago)
Message:

Small fix for unicode matching example along with formatting changes

Location:
docs/Working/icGrep
Files:
6 edited

Unmodified
Removed
• docs/Working/icGrep/background.tex

 r4494 position of d'' characters and {\tt [a-z]} for the stream of lower case ASCII alphabetics are first computed in a fully data-parallel manner. Then the matching process proper begins taking advance of bitwise logic Then the matching process proper begins taking advantage of bitwise logic and shifting operations as well as an operation for finding all matches to a character class repetition known as MatchStar.  At each step of the \begin{figure} \vspace{-0.5em} \begin{center} \begin{tabular}{cr}\\ \end{tabular} \end{center} \vspace{-1em} \caption{Matching {\tt d[a-z]*ed} Using Bitwise Data Parallelism}\label{fig:bitwisematch} \vspace{-0.5em} \end{figure} {\tt [a-z]*} ($M_2$).   This produces pending matches at many positions.  However, there is no need to consider these matches one at a time using lazy or greedy matching strategies. Rather, the full marker stream $M_3$ of remaining possibilites after matching {\tt [e]} is easily Rather, the full marker stream $M_3$ of remaining possibilities after matching {\tt [e]} is easily computed using bitwise logic and shift. The final step produces marker stream $M_4$ indicating the single position
• docs/Working/icGrep/fig-compiler.tex

 r4500 \begin{figure}[tbh] \vspace{-2em} \begin{center} \end{center} \vspace{-1em} \caption{icGrep compilation architecture}\label{fig:compiler} \vspace{-1em} \end{figure}
• docs/Working/icGrep/fig-executor.tex

 r4499 \begin{pgfonlayer}{threads} \path (S2P.north west)+(-.1,.3) node (a) {}; \path (S2P.north west)+(-.1,.5) node (a) {}; \path (S2P.south east)+(+1.7,-0.1) node (b) {}; \path[fill=green!20,rounded corners, draw=green, solid] (a) rectangle (b); \node [draw=none,above=-0.1cm of S2P.north east] (t1) {Transposition Thread}; \node [draw=none,above=-0.04cm of S2P.north east] (t1) {Transposition Thread}; \path (RequiredStreamsGenerator.north west)+(-.1,.3) node (a) {}; \path (RequiredStreamsGenerator.north west)+(-.1,.38) node (a) {}; \path (RequiredStreamsGenerator.south east)+(+2,-0.1) node (b) {}; \path[fill=blue!20,rounded corners, draw=blue, solid] (a) rectangle (b); \node [draw=none,above=-0.1cm of RequiredStreamsGenerator.north east] (t1) {Stream Generator Thread}; \node [draw=none,above=-0.04cm of RequiredStreamsGenerator.north east] (t1) {Stream Generator Thread}; \path (JITFunction.north west)+(-.1,.3) node (a) {}; \path (NamedPropertyLibrary.south east)+(+.1,-0.1) node (b) {}; \path (JITFunction.north west)+(-.1,.38) node (a) {}; \path (NamedPropertyLibrary.east |- MatchScanner.south)+(+.1,-0.1) node (b) {}; \path[fill=red!20,rounded corners, draw=red, solid] (a) rectangle (b); \node [draw=none,above=-0.1cm of JITFunction.north east] (t1) {Matcher Thread}; \node [draw=none,above=-0.04cm of JITFunction.north east] (t1) {Matcher Thread}; \end{pgfonlayer}{threads}
• docs/Working/icGrep/introduction.tex

 r4490 Using parallel methods to accelerate matching of a single pattern on a single input stream is more difficult.  Indeed, of the 13 dwarves identified in the Berkeley overview of parallel computing research, finite state machines (FSMs) are considered the hardest to parallelize (embarassingly sequential) \cite{asanovic2006landscape}. finite state machines (FSMs) are considered the hardest to parallelize (embarrassingly sequential) \cite{asanovic2006landscape}. However, some success has been reported recently along two independent lines of research.   Mytkowicz et al \cite{mytkowicz2014data} use SIMD shuffle operations
• docs/Working/icGrep/unicode-re.tex

 r4499 character to the next. In order to address the requirements of Unicode advance, we use the $\mathit{ScanThru}$ \cite{cameron2011parallel} operation to move a set of markers To address the requirements of Unicode advance, we use the ScanThru~\cite{cameron2011parallel} operation to move a set of markers each through the nonfinal bytes of UTF-8 sequences to the final byte position.   Figure \ref{fig:multibytesequence} shows this byte position. Figure~\ref{fig:multibytesequence} shows this technique in operation in the case of advancing through byte sequences (each 3 bytes in length) corresponding to Chinese characters. To better demonstrate the process, we use \emph{ni3}, \emph{hao} and \emph{men} to represent these characters. $CC_{\mbox{ni3}}$ is the bitstream that marks character \emph{ni3} and $CC_{\mbox{hao}}$ is the bitstream that marks character stream \emph{hao}. To match a two UTF-8 character sequence \emph{ni3hao}, we first create an \emph{Initial} steam that marks the first byte of all the valid characters. We also produce a \emph{NonFinal} stream that marks every byte of all the multibyte characters except for the last byte. Using \emph{Initial} to ScanThru \emph{NonFinal}, we get the bitstream $M_2$, which marks the positions of the last byte of every character. An overlap between $M_2$ and $CC_{\mbox{ni3}}$ gives the start position for matching the next character. As illustrated by \emph{Adv}, we find two matches for \emph{ni3} and from these two positions we can start the matching process for the next character \emph{hao}. The final result stream shows 1 match for the multibyte sequence ni3hao. sequences (each 3 bytes in length) corresponding to Chinese characters. To better demonstrate the process, we use \texttt{ni3}, \texttt{hao} and \texttt{men} to represent these characters. $\text{CC}_{\texttt{ni3}}$ is the bitstream that marks character \texttt{ni3} and $\text{CC}_{\texttt{hao}}$ is the bitstream that marks character \texttt{hao}. To match a two UTF-8 character sequence \texttt{ni3hao}, we first create an Initial steam that marks the first byte of all the valid characters. We also produce a NonFinal stream that marks every byte of all multibyte characters \emph{except for} the last byte. Using Initial to ScanThru NonFinal, we construct bitstream $M_1$, which marks the positions of the last byte of every character. An overlap between $M_1$ and $\text{CC}_{\texttt{ni3}}$ gives the start position for matching the next character. As illustrated by $M_2$, we find two matches for \texttt{ni3}, and from these two positions we can start the matching process for the next character \texttt{hao}. The final result stream $M_4$ shows one match for the multibyte sequence \texttt{ni3hao}. \begin{figure}[tbh] \vspace{-0.5em} \begin{center} %\begin{tabular}{cr}\\ \begin{tabular}{r@{\hspace{1em}}r}\\ input data  & \verbni3hao(Hello),ni3men(You),\\ $CC_{\mbox{ni3}}$ & \verb..1.............1.........\\ $CC_{\mbox{hao}}$ & \verb.....1....................\\ \emph{Initial} & \verb1..1..111111111..1..111111\\ \emph{NonFinal} & \verb11.11.........11.11.......\\ $M_1 = \mathit{ScanThru}(\mathit{Initial}, \mathit{NonFinal})$ & \verb..1..111111111..1..1111111\\ $\mathit{Adv} = \mathit{Advance}(M_1 \land CC_{\mbox{ni3}})$ & \verb...1.............1........\\ $M_2 = \mathit{ScanThru}(\mathit{Initial} \land \mathit{Adv}, \mathit{NonFinal})$ & \verb.....1.............1......\\ $\mathit{match} = M_2 \land CC_{\mbox{hao}}$ & \verb.....1.................... \begin{tabular}{c@{\hspace{1em}}r}\\ input data                                                         & \verbni3hao(Hello),ni3men(You),\\ $\text{CC}_{\text{ni3}}$                                           & \verb..1.............1.........\\ $\text{CC}_{\text{hao}}$                                           & \verb.....1....................\\ Initial                                                            & \verb1..1..111111111..1..111111\\ NonFinal                                                           & \verb11.11.........11.11.......\\ $M_1 = \text{ScanThru}(\text{Initial}, \text{NonFinal})$           & \verb..1..111111111..1..1111111\\ $M_2 = \text{Advance}(M_1 \land \text{CC}_{\text{ni3}})$           & \verb...1.............1........\\ $M_3 = \text{ScanThru}(\text{Initial} \land M_2, \text{NonFinal})$ & \verb.....1.............1......\\ $M_4 = M_3 \land CC_{\text{hao}}$                                  & \verb.....1.................... \end{tabular} \end{center} \vspace{-1em} \caption{Processing of a Multibyte Sequence ni3hao} \label{fig:multibytesequence} \vspace{-0.5em} \end{figure} \paragraph{Unicode MatchStar.} The $\mathit{MatchStar}(M, C)$ operation directly implements the operation of finding all positions reachable from a {\em final} positions.   Thus the one bits of a Unicode character class stream are not necessarily contiguous.  This in turn means that the carry propagation within the MatchStar means that carry propagation within the MatchStar operation may terminate prematurely.
Note: See TracChangeset for help on using the changeset viewer.