Changeset 1300 for docs


Ignore:
Timestamp:
Aug 8, 2011, 3:04:27 PM (8 years ago)
Author:
ksherdy
Message:

Minor edits.

Location:
docs/PACT2011
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • docs/PACT2011/00-abstract.tex

    r1295 r1300  
    1313In Parabix, we first convert character streams into sets of parallel
    1414bit streams. We then exploit the SIMD operations prevalent on commodity-level hardware for performance.
    15 The first generation Parabix1 parser exploits the processor built-in bit-scan instructions
     15The first generation Parabix1 parser exploits the processor built-in $bitscan$ instructions
    1616over these streams to make multibyte moves but follows an otherwise sequential
    1717approach.  The second generation Parabix2 technology adds further
  • docs/PACT2011/03-research.tex

    r1299 r1300  
    6262To transform byte-oriented character data to parallel bit stream representation, source data is first loaded into SIMD registered in sequential order. It is then converted to the transposed basis bit stream representation through a series of parallel SIMD pack, shift, and logical bitwise operations. Using the SIMD capabilities of current commodity processors, the transposition of source data to basis bit stream format incurs an amortized cost of approximately 1 cycle per byte \cite{CameronHerdyLin2008}.
    6363
    64 Throughout the XML parsing process we must identify key XML characters. For example, the opening angle bracket character `<'. For this purpose, we combine the basis bit streams using bitwise logic and compute character-class bit streams. For example, the $j$-th character is an open angle bracket `<' if and only if the $j$-th bit of $B_2, B_3, B_4, B_5 =$ 1 and the $j$-th bit of $B_0, B_1, B_6, B_7 =$ 0. Character-class streams mark the positions of source characters as a single $1$-bit. Each bit position in the computed bit stream is in one-to-one correspondence with its source byte position.  Once generated, single cycle built-in {\em bitscan} operations are used to locate the positions of key XML characters throughout the parsing process. Utilizing $M$ SIMD registers of width $W$, it is possible to scan through $W$ characters in parallel. The register width $W$ varies between 64-bit for MMX, 128-bit for SSE, and 256-bit for AVX.
     64Throughout the XML parsing process we must identify key XML characters. For example, the opening angle bracket character `<'. For this purpose, we combine the basis bit streams using bitwise logic and compute character-class bit streams. For example, the $j$-th character is an open angle bracket `<' if and only if the $j$-th bit of $B_2, B_3, B_4, B_5 =$ 1 and the $j$-th bit of $B_0, B_1, B_6, B_7 =$ 0. Character-class streams mark the positions of source characters as a single $1$-bit. Each bit position in the computed bit stream is in one-to-one correspondence with its source byte position.  Once generated, single cycle built-in {\em bitscan} operations are used to locate the positions of key XML characters throughout the parsing process. Utilizing $M$ SIMD registers of width $W$, it is possible to scan through $W$ characters in parallel. The register width $W$ is processor dependent and ranges from 64-bit for MMX, to 128-bit for SSE, and 256-bit for AVX.
    6565
    66 A common operation in XML parsing is XML start tag validation. Starts tags begin with `<' and end with either ``/>'' or ``>'' (depending whether the element tag is an empty element tag or not, respectively). Figure \ref{fig:Parabix1StarttagExample} conceptually demonstrates start tag validation as performed in Parabix1 using character-class streams together with the processor built-in bit scan operation. The first bit stream $M_0$ is created and the parser begins scanning the source data for an open angle bracket `<', starting at position 1. Since the source data begins with `<', $M_0$ is assigned a cursor position of 1. The $advance$ operation then shifts $M_0$'s cursor position by 1, resulting in the creation of a new bit stream, $M_1$, with the cursor position at 2. The following $bitscan$ operation takes the cursor position from $M_1$ and sequentially scans every position until it locates either an `>'. It finds a `>' at position 4 and returns that as the new cursor position for $M_2$. Calculating $M_3$ advances the cursor again, and the $bitscan$ used to create $M_4$ locates the new opening angle bracket. This process continues in sequence until until all start tags are validated. Unlike traditional parsers, these sequential operations are accelerated significantly since the {\em bitscan} operation can skip up to $w$ positions, where $w$ is the processor word width in bits. This approach has recently been applied to Unicode transcoding and XML parsing to good effect, with research prototypes showing substantial speed-ups over even the best of byte-at-a-time alternatives \cite{CameronHerdyLin2008, Herdy2008, Cameron2009}.
     66A common operation in XML parsing is XML start tag validation. Starts tags begin with `<' and end with either ``/>'' or ``>'' (depending on whether the element tag is an empty element tag or not, respectively). Figure \ref{fig:Parabix1StarttagExample} conceptually demonstrates start tag validation as performed in Parabix1 using character-class streams together with the processor built-in $bitscan$ operation. We proceeed as follows. The first bit stream $M_0$ is created and the parser begins scanning the source data for an open angle bracket `<', starting at position 1. Since the source data begins with `<', $M_0$ is assigned a cursor position of 1. The $advance$ operation then shifts $M_0$'s cursor position by 1, resulting in the creation of a new bit stream, $M_1$, with the cursor position at 2. The following $bitscan$ operation takes the cursor position from $M_1$ and sequentially scans every position until it locates either an `>'. It finds a `>' at position 4 and returns that as the new cursor position for $M_2$. Calculating $M_3$ advances the cursor again, and the $bitscan$ used to create $M_4$ locates the new opening angle bracket. This process continues in sequence until until all start tags are validated. Unlike traditional parsers, these sequential operations are accelerated significantly since the {\em bitscan} operation can skip up to $w$ positions, where $w$ is the processor word width in bits. This approach has recently been applied to Unicode transcoding and XML parsing to good effect, with research prototypes showing substantial speed-ups over even the best of byte-at-a-time alternatives \cite{CameronHerdyLin2008, Herdy2008, Cameron2009}.
    6767
    6868\begin{figure}[h]
     
    8989\subsection{Parabix2}
    9090
    91 In Parabix2, the sequential single-cursor parsing approach using {\em bitscan} instructions is replaced by a parallel parsing approach, that uses multiple cursors when possible, and bit stream addition operations to advance cursor positions.
     91In Parabix2, the sequential single-cursor parsing approach using {\em bitscan} instructions is replaced by a parallel parsing approach, that uses multiple cursors when possible, and bit stream addition operations to advance multiple cursor positions in parallel.
    9292Unlike the single-cursor approach of Parabix1 (and conceptually of all sequential XML parsers),
    9393Parabix2 processes multiple cursors in parallel. For example, using the source data from
Note: See TracChangeset for help on using the changeset viewer.