Ignore:
Timestamp:
Dec 13, 2011, 4:50:42 PM (8 years ago)
Author:
lindanl
Message:

minor changes

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/HPCA2012/final_ieee/03-research.tex

    r1751 r1774  
    1818traditional text processing models is in how Parabix represents the
    1919source data.  Given a traditional byte-oriented text stream, Parabix
    20 first transposes the text data to a transform domain consisting of 8
    21 parallel bit streams, known as {\em basis bit streams}.  In essence,
    22 each basis bit stream $b_{k}$ represents the stream of $k$-th bit of
     20first transposes the text data into a transform representation consisting of 8
     21parallel bit streams, known as {\em basis bit streams} wherein
     22basis bit stream $b_{k}$ represents the stream of $k$-th bit of
    2323each byte in the source text.  That is, the $k$-th bit of $i$-th byte
    24 in the source text is in the $i$-th (bit) position of the $k$-th basis
     24in the source text is in one-to-one correspondence with the $i$-th bit of the $k$-th basis
    2525bit stream, $b_{k}$.  For example, in Figure~\ref{fig:BitStreamsExample}, we show how the ASCII string ``{\ttfamily
    2626  b7\verb`<`A}'' is represented as 8 basis bit streams, $\tt b_{0
    27   \ldots 7}$. The bits used to construct $\tt b_7$ have been
     27  \ldots 7}$. The bits used to construct $\tt b_7$ are
    2828highlighted in this example.
    2929
     
    5353use the 128-bit SIMD registers commonly found on commodity processors
    5454(e.g. SSE on Intel) to process 128 byte positions at a time using
    55 bitwise logic, shifting and other operations.
     55bitwise logical, shift and arithmetic operations.
    5656
    5757Just as forward and inverse Fourier transforms are used to transform
    5858between the time and frequency domains in signal processing, bit
    5959stream transposition and inverse transposition provides ``byte space''
    60 and ``bit space'' views of text.  The goal of the Parabix framework is
     60and ``bit space'' domains for text.  The goal of the Parabix framework is
    6161to support efficient text processing using these two equivalent
    62 representations in the same way that efficient signal processing
     62representations in the analogous way that efficient signal processing
    6363benefits from the use of the frequency domain in some cases and the
    6464time domain in others.
     
    101101metadata parsing.
    102102% For example, in a CSV file, any `,' or `\textbackslash n' can indicate the start of a new column or row respectively.
    103 For example, in XML, any opening angle bracket character, `\verb`<`', may indicate that we are starting a new markup tag.
     103For example, in XML, any opening angle bracket character, `\verb`<`', may indicate the start of a markup tag.
    104104Traditional byte-at-a-time parsers find these characters by comparing the value of each byte with a set
    105105of known significant characters and branching appropriately when one is found, typically using an if or switch statement.
     
    109109% However, a `<' is legal within an XML comment so not every `<' necessarily means that we are opening a new tag.
    110110
    111 Character-class bit streams allow us to perform up to 128
    112 ``comparisons'' in parallel with a single operation by using a series
    113 of boolean-logic operations \footnote{$\land$, $\lor$ and $\lnot$
    114   denote the boolean AND, OR and NOT operations.}  to merge multiple
    115 basis bit streams into a single character-class stream that marks the
    116 positions of key characters with a $1$. For example, a character is
     111Character-class bit streams enable up to 128
     112``comparisons'' in parallel through a
     113series of boolean-logic operations \footnote{$\land$, $\lor$ and $\lnot$
     114  denote the boolean AND, OR and NOT operations.}  that merge multiple basis
     115bit streams into a single character-class stream that marks the
     116positions of key characters. For example, a character is
    117117an `\verb`<`' if and only if $\lnot(b_ 0 \lor b_1) \land (b_2 \land
    118 b_3 \land b_4 \land b_5) \land \lnot (b_6 \lor b_7) = 1$.  Classes of
    119 characters can be found with similar formulas.  For example, a
     118b_3 \land b_4 \land b_5) \land \lnot (b_6 \lor b_7) = 1$.  Addition character
     119classes can be determined with similar formulas.  For example, a
    120120character is a number {\tt [0-9]} if and only if $\lnot(b_0 \lor b_1)
    121121\land (b_2 \land b_3) \land \lnot(b_4 \land (b_5 \lor b_6))$.  An
     
    135135To perform lexical analysis on the input data, Parabix computes lexical and error bit streams from the character-class bit streams using
    136136a mixture of both boolean logic and arithmetic operations. Lexical bit streams typically mark multiple current parsing positions.
    137 Unlike the single-cursor approach of traditional text parsers, these allow Parabix to process multiple cursors in parallel.
     137Unlike the single-cursor approach of traditional text parsers, the marking of multiple lexical items allows Parabix to process multiple items in parallel.
    138138Error bit streams are often the byproduct or derivative of computing lexical bit streams and can be used to identify any well-formedness
    139 issues found during the parsing process. The presence of a $\tt 1$ in an error stream indicates that the lexical stream cannot be
    140 trusted to be completely accurate and it may be necessary to perform some sequential parsing on that section to determine the cause and severity
    141 of the error. %How errors are handled depends on the logical implications of the error and go beyond the scope of this paper.
    142 
    143 To form lexical bit streams, we have to introduce a few new operations: {\tt Advance} and {\tt ScanThru}.
     139issues found during the parsing process. A $\tt 1$ bit in an error stream indicates the precense of a potential error that may require further
     140processing to determine cause and severity.
     141
     142To form lexical bit streams we introduce two new operations: {\tt Advance} and {\tt ScanThru}.
    144143The {\tt Advance} operator accepts one input parameter, $c$, which is typically viewed as a bit stream containing multiple cursor bits,
    145144and advances each cursor one position forward.  On little-endian architectures, shifting forward means shifting to the right.
    146 {\tt ScanThru} accepts two input parameters, $c$ and $m$; any bit that is in both $c$ and $m$ is moved to first subsequent
    147 $\tt 0$-bit in $m$ by calculating $(c + m) \land \lnot m$. 
     145{\tt ScanThru} accepts two input parameters, $c$ and $m$, where $c$ denotes an initial
     146set of cursor positions, and $m$ denotes a set of ``marked'' lexical item positions.
     147The ScanThru operation determines the cursor positions immediately
     148following any run of marker positions by calculating $(c + m) \land \lnot m$. 
    148149For example, in Figure \ref{fig:ParabixParsingExample} suppose we have the regular expression \verb`<[a-zA-Z]+>` and wish to find all
    149150instances of it in the source text.
     
    152153token. By computing $E_{0}$, the parser notes that ``\verb`<>`'' does not match the expected pattern. To find the end positions of each token,
    153154the parser calculates $L_{1}$ by moving the cursors in $L_0$ through the letter bits in $C_0$. $L_1$ is then validated to ensure that each
    154 token ends with a `\verb`>`' and discovers that ``\verb`<error]`'' too fails to match the expected pattern.
     155token ends with a `\verb`>`' and discovers that ``\verb`<error]`'' also fails to match the expected pattern.
    155156With additional post bit-stream processing, the erroneous cursors in $L_{0}$ and $L_{1}$ can be removed; the details
    156157of which go beyond the scope of this paper.
     
    188189% details, refer to the technical report \cite{Cameron2010}.
    189190
    190 Using this parallel bit stream approach, conditional branch statements
     191Using this parallel bit stream approach, the vast majority of conditional branches
    191192used to identify key positions and/or syntax errors at each
    192193parsing position are mostly eliminated, which, as Section
     
    211212application.  Input is specified using a character class syntax
    212213adapted from the standard regular expression notations.  Output is a
    213 minimized set of three-address bitwise operations to compute each of
     214minimized set of three-address bitwise operations that compute each of
    214215the character classes from the basis bit streams.
    215 
    216 
    217 For example, Figure \ref{fig:CCC} shows the input and output produced
     216Figure \ref{fig:CCC} shows the input and output produced
    218217by the character class compiler for the example of \verb`[0-9]`
    219218discussed in the previous section.  The output operations may be
     
    305304carry variable declarations that allow the results of
    306305{\tt Advance} and {\tt ScanThru} operations to be carried over from
    307 block to block.  A separate carry variable is required for every
     306block-to-block.  A separate carry variable is required for every
    308307{\tt Advance} or {\tt ScanThru} operation.  A function containing
    309308such operations is translated into a public C++ class (struct),
     
    316315specific architecture and Carry Queue representation.
    317316The unbounded bit stream {\tt Advance} and {\tt ScanThru}
    318 operations are translated into block-by-block equivalents
     317operations are translated into block-wise equivalents
    319318with explicit carry-in and carry-out processing. 
    320319At the end of each block, the {\tt CarryQ\_Adjust}
     
    325324(if and while constructs) which involves additional
    326325carry-test insertion in control branches.
    327 Explaining the full details of the translation
     326A complete explanation of the Pablo translation
    328327is beyond the scope of this paper.
    329328
     
    332331The Parabix architecture also includes runtime libraries that support
    333332a machine-independent view of basic SIMD operations, as well as a set
    334 of core function libraries.  For machine-independence, we program all
    335 operations using an abstract SIMD machine.  The abstract machine
     333of core function libraries. For portability, we program all SIMD operations against
     334an abstract SIMD machine representation, parameterized on SIMD
     335field and register width. The abstract machine
    336336supports all power-of-2 field widths up to the full SIMD register
    337337width on a target machine.  Let $w = 2k$ be the field width in
     
    350350currently take advantage of the 128-bit Altivec operations on the
    351351Power PC, 64-bit MMX and 128-bit SSE operations on previous generation
    352 Intel platforms, the latest 256-bit AVX extensions on the Sandybridge
     352Intel platforms, the latest 256-bit AVX extensions on the \SB{}
    353353processor, and finally the 128-bit \NEON{} operations on ARM.
    354354
Note: See TracChangeset for help on using the changeset viewer.