# Changeset 1031

Ignore:
Timestamp:
Mar 25, 2011, 7:22:10 PM (8 years ago)
Message:

Meth clean-up

Location:
docs/PACT2011
Files:
2 edited

### Legend:

Unmodified
 r1003 \section{Parabix} \label{section:reserach} \label{section:parabix} %Describe key technology behind Parabix %Introduce SIMD; \begin{center} \begin{tabular}{cr}\\ source data $\vartriangleright$ & \verbabc\\ source data & \verbabc\\ $B_0$ & \verb..1.1.1.1.1....1.\\ $B_1$ & \verb...1.11.1..1..111\\ \begin{center} \begin{tabular}{lr}\\ source data $\vartriangleright$ & \verbabc\\ source data & \verbabc\\ % $N =$ name chars & \verb.11.111.11...11..\\ $M_0 = 1$ & \verb1................\\ %In Parabix2, we replace the sequential single-cursor parsing using bit scan instructions with a parallel parsing method using bitstream addition. Unlike the single cursor approach of Parabix1 and conceptually of traditional sequential approach, in Parabix2 multiple cursors positions are processed in parallel. In Parabix2, we replace the sequential single-cursor parsing using bit scan instructions with a parallel parsing method using bitstream addition. Unlike the single-cursor approach of Parabix1 (and conceptually of all sequential XML parsers), Parabix2 processes multiple cursors in parallel. For example, using the source data from Figure \ref{fig:Parabix1StarttagExample}, Figure \ref{fig:Parabix2StarttagExample} shows how Parabix2 identifies and moves each of the start tag markers forwards to the corresponding end tag. Like Parabix1, we assume that $N$ (the name chars) has been computed using the basis bitstreams and that In Parabix2, we replace the sequential single-cursor parsing using bit scan instructions with a parallel parsing method using bitstream addition. Unlike the single-cursor approach of Parabix1 (and conceptually of all sequential XML parsers), Parabix2 processes multiple cursors in parallel. For example, using the source data from Figure \ref{fig:Parabix1StarttagExample}, Figure \ref{fig:Parabix2StarttagExample} shows how Parabix2 identifies and moves each of the start tag markers forwards to the corresponding end tag. %Like Parabix1, we assume that $N$ (the name chars) has been computed using the basis bitstreams and that \begin{figure}[h] \begin{center} \begin{tabular}{lr}\\ source data $\vartriangleright$ & \verbabc\\ source data & \verbabc\\ $N =$ name chars & \verb.11.111.11...11..\\ $M_0 = [<]$ & \verb1......1....1....\\ \end{figure} In general, the set of bit positions in a marker bitstream may be considered to be the current parsing positions of multiple parses taking place in parallel throughout the source data stream. A further aspect of the parallel method is that conditional branch statements used to identify syntax error at each each parsing position are eliminated. Although we do not show it in the prior examples, error bitstreams can be used to identify any well-formedness errors found during the parsing process. Error positions are gathered and processed in as a final post processing step. Hence, Parabix2 offers additional parallelism over Parabix1 in the form of multiple cursor parsing as well as significanlty reduces branch misprediction penalty. In general, the set of bit positions in a marker bitstream may be considered to be the current parsing positions of multiple parses taking place in parallel throughout the source data stream. A further aspect of the parallel method is that conditional branch statements used to identify syntax error at each each parsing position are eliminated. Although we do not show it in the prior examples, error bitstreams can be used to identify any well-formedness errors found during the parsing process. Error positions are gathered and processed in as a final post processing step. Hence, Parabix2 offers additional parallelism over Parabix1 in the form of multiple cursor parsing as well as further reducing branch misprediction penalties.