Changeset 991 for docs


Ignore:
Timestamp:
Mar 24, 2011, 7:11:05 PM (8 years ago)
Author:
ksherdy
Message:

Minor edits.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/PACT2011/02-background.tex

    r990 r991  
    4545\subsection{Parallel XML Parsing}
    4646
    47 In general, parallel XML acceleration methods comes in one of two forms --- multithreaded approaches and SIMDized techniques. Multithreaded XML parsers take advantage of multiple cores by first quickly preparsing the XML file to locate key partitioning points. The XML workload is then divided and processed independently across the available cores \cite{ZhangPanChiu09}. A join step typically follows. SIMD XML parsers leverage the SIMD registers to overcome the performance limitations of the byte-at-a-time sequential paradigm and inherent data dependent branch misprediction rates \cite{Cameron2010}. The SIMDized XML parsers, Parabix1 and Parabix2, utilizes parallel bit stream processing technology. With this method, byte-oriented character data is first transposed to eight parallel bit streams, one for each bit position within the character code units (bytes). These bit streams are then loaded into SIMD registers of width $W$ (e.g., 64-bit, 128-bit, 256-bit, etc). This allows $W$ consecutive code units to be represented and processed at once. Bitwise logic and shift operations, bit scans, population counts and other bit-based operations are then used to carry out the work in parallel \cite{CameronLin2009}.
     47In general, parallel XML acceleration methods comes in one of two forms --- multithreaded approaches and SIMDized techniques. Multithreaded XML parsers take advantage of multiple cores by first quickly preparsing the XML file to locate key partitioning points. The XML workload is then divided and processed independently across the available cores \cite{ZhangPanChiu09}. A join step typically follows. SIMD XML parsers leverage the SIMD registers to overcome the performance limitations of the byte-at-a-time sequential paradigm and inherent data dependent branch misprediction rates \cite{Cameron2010}. The SIMDized XML parsers, Parabix1 and Parabix2, both utilize parallel bit stream processing technology. With this method, byte-oriented character data is first transposed to eight parallel bit streams, one for each bit position within the character code units (bytes). These bit streams are then loaded into SIMD registers of width $W$ (e.g., 64-bit, 128-bit, 256-bit, etc). This allows $W$ consecutive code units to be represented and processed at once. Bitwise logic and shift operations, bit scans, population counts and other bit-based operations are then used to carry out the work in parallel \cite{CameronLin2009}.
    4848
    4949\subsubsection{Parabix1}
    5050
    51 Our first generation parallel bitstream XML parser, Parabix1, uses a less conventional approach of SIMD technology to represent text in parallel bitstreams. Bits of each stream are in one-to-one-correspondence with the bytes of a character stream. A transposition step first transforms sequential byte stream data into eight basis bitstreams for the bits of each byte. Bitwise logical combinations of these basis bitstreams can then be used to classify bytes in various ways, while the bit scan operations common to commodity processors can be used for fast sequential scanning. At a high level, Parabix1 processes source XML in a functionally equivalent manner as a traditional processor. That is, Parabix1 moves sequentially through the source document, maintaining a single cursor scanning position throughout the parse. However, this scanning operation itself is accelerated significantly which leads to dramatic performance improvements, since bit scan operations can perform up to general register width (32-bit, 64-bit) finite state transitions per clock cycle. 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, CameronLin2009, Cameron2010}.
     51Our first generation parallel bitstream XML parser, Parabix1, uses a less conventional approach of SIMD technology to represent text in parallel bitstreams. Bits of each stream are in one-to-one-correspondence with the bytes of a character stream. As mentioned a transposition step first transforms sequential byte stream data into eight basis bitstreams for the bits of each byte. Bitwise logical combinations of these basis bitstreams are then be used to classify bytes in various ways, while the bit scan operations common to commodity processors are used for fast sequential scanning. At a high level, Parabix1 processes source XML in a functionally equivalent manner as a traditional processor. That is, Parabix1 moves sequentially through the source document, maintaining a single cursor scanning position throughout the parse. However, this scanning operation itself is accelerated significantly which leads to dramatic performance improvements, since bit scan operations can perform up to general register width (32-bit, 64-bit) finite state transitions per clock cycle. 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, CameronLin2009, Cameron2010}.
    5252
    5353\subsubsection{Parabix2}
Note: See TracChangeset for help on using the changeset viewer.