Changeset 900


Ignore:
Timestamp:
Feb 6, 2011, 1:48:32 PM (8 years ago)
Author:
cameron
Message:

Fred's latest changes.

Location:
docs/EuroPar2011
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • docs/EuroPar2011/europar-cameron.tex

    r898 r900  
    9797hardest of the ``13 dwarves'' to parallelize \cite{Asanovic:EECS-2006-183},
    9898parallel bitstream technology shows considerable promise for these
    99 types of applications\cite{PPoPP08,CameronHerdyLin2008,Green2009}.
     99%types of applications\cite{PPoPP08,CameronHerdyLin2008,Green2009}.
     100types of applications \cite{PPoPP08,CameronHerdyLin2008,Green2009}.
    100101In this approach, character streams are processed $N$ positions at
    101102a time using the $N$-bit SIMD registers commonly found on commodity
     
    111112instructions also available on commodity processors, the
    112113Parabix 1 XML parser was shown to considerably accelerate XML
    113 parsing in comparison with conventional byte-at-a-time parser
     114% parsing in comparison with conventional byte-at-a-time parser
     115parsing in comparison with conventional byte-at-a-time parsers
    114116in applications such as statistics gathering \cite{CameronHerdyLin2008} and
    115117as GML to SVG conversion \cite{Herdy2008}. 
     
    192194The starting point for bitstream methods are \emph{basis} bitstreams
    193195and their use in determining \emph{character-class} bitstreams.
    194 The $k$th basis bitstream $B_k$ consists of the $k$th bit (0-based, starting at the LSB)
     196The $k$th basis bitstream $B_k$ consists of the $k$th bit (0-based, starting at the the least significant bit)
    195197of each character in the source data stream;
    196198thus each $B_k$ is dependent on the encoding of the source characters (ASCII, UTF-8, UTF-16, etc.).
     
    252254the middle of a span.
    253255The parallel parsing task is to move each
    254 of the four markers forward through the corresponding spans of
     256of the four markers forward (to the left) through the corresponding spans of
    255257digits to the immediately following positions.
    256258
     
    259261\begin{tabular}{cr}\\
    260262source data $\vartriangleleft$ & \verb`----173942---654----1----49731----321--`\\
    261 $M_0 =$ & \verb`.........1.....1....1......1...........`\\
     263$M_0$ & \verb`.........1.....1....1......1...........`\\
    262264$D = $\verb:[0-9]: & \verb`....111111...111....1....11111....111..`\\
    263265$M_0 + D$ & \verb`...1........1......1....1...11....111..`\\
     
    474476After these operations, there are no more attributes
    475477in the first tag, so its corresponding marker becomes zeroed out.
    476 However, $M_{1, 8}$ is not all $0$s, as the second tags still has an unparsed attribute-value pair.
     478However, $M_{1, 8}$ is not all $0$s, as the second tag still has an unparsed attribute-value pair.
    477479Thus, the parsing continues.
    478480
     
    654656%\subsection{Summary}
    655657
    656 Overall, parallel bitstream techniques are quite well-suited to
     658Overall, parallel bitstream techniques are well-suited to
    657659verification problems such as XML well-formedness checking. 
    658660Many of the character validation and syntax checking requirements
     
    708710
    709711In this section, we compare the performance of our \verb:xmlwf:
    710 implementation using the Parabix2 technology described above with several
     712implementation using the Parabix 2 technology described above with several
    711713other implementations.
    712714These include the original \verb:xmlwf:
Note: See TracChangeset for help on using the changeset viewer.