Changeset 990 for docs


Ignore:
Timestamp:
Mar 24, 2011, 6:53:37 PM (9 years ago)
Author:
ksherdy
Message:

Minor edits.

File:
1 edited

Legend:

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

    r989 r990  
    2828
    2929
    30 XML files can be classified as ``documents-oriented'' or ``data-oriented'' \cite{DuCharme04}. Documented-oriented XML is designed to be human readable, such as Figure \ref{fig:sample_xml}; data-oriented XML files are intended to be parsed by machines and omit any ``human-friendly'' formatting techniques, such as the use of whitespace and descriptive ``natural language'' naming schemes.  Although the XML specification does not distinguish between ``XML for documents'' and ``XML for data'' \cite{TR:XML}, the latter often requires the use of an XML parser in order to utilize the information within them. The role of an XML parser is to transform the text-based XML data into an application-ready format.
     30XML files can be classified as ``documents-oriented'' or ``data-oriented'' \cite{DuCharme04}. Documented-oriented XML is designed to be human readable, such as Figure \ref{fig:sample_xml}; data-oriented XML files are intended to be parsed by machines and omit any ``human-friendly'' formatting techniques, such as the use of whitespace and descriptive ``natural language'' naming schemes.  Although the XML specification does not distinguish between ``XML for documents'' and ``XML for data'' \cite{TR:XML}, the latter often requires the use of an XML parser to extract the information within. The role of an XML parser is to transform the text-based XML data into an application-ready format.
    3131%For example, an XML parser for a web browser may take a XML file, apply a style sheet to it, and display it to the end user in an attractive yet informative way; an XML database parser may take a XML file and construct indexes and/or compress the tree into a proprietary format to provide the end user with efficient relational, hierarchical, and/or object-based query access to it.
    3232
     
    3737% However, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}.
    3838
    39 Traditional XML parsers are sequential byte-at-a-time parsers. Using this approach, an XML parser processes a source document by serially scanning through it in a top-down manner. Each character of text is read to distinguish between the XML-specific markup, such as an opening angle bracket `<', and the data held within the document. As the parser moves through the source document, it alternates between markup scanning and data validation operations.
    40 At each processing step, a parser scans the source document and locates the expected markup fields or reports an error and terminates. % not happy with the phrasing of this line
    41 In other words, traditional XML parsers are complex finite-state machines that use per-character comparisons to transition between data- and metadata-type states. Each state transition indicates the context in which to interpret the subsequent characters. Unfortunetly, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}; thus any character could be a state transition until deemed otherwise.
    42 Two such parsers are Expat and Xerces-C.
    43 Both are C/C++ based open-source XML parsers.
    44 Expat was originally released in 1998; it is currently used in Mozilla Firefox and Open Office \cite{expat}.
    45 Xerces-C was released in 1999 and is the foundation of the Apache XML project \cite{xerces}.
     39Traditional XML parsers process XML sequentially a single byte-at-a-time. Following this approach, an XML parser processes a source document serially, from the first to the last byte in the source file in a top-down manner. Each character of text is examined to distinguish between the XML-specific markup, such as an opening angle bracket `<', and the content held within the document. As the parser moves through the source document, it alternates between markup scanning, and data validation and processing operations. At each processing step, the parser scans the source document and either locates the expected markup, or reports an error condition and terminates. % not happy with the phrasing of this line
    4640
    47 The major disadvantage with sequential XML parsers is that every character requires at least one conditional branch. Branch mispredictions have been shown to degrade performance in proportion to the markup density of the source document \cite{CameronHerdyLin2008} (i.e., the proportion of XML-markup vs. XML-data).
     41In other words, traditional XML parsers are complex finite-state machines that use byte comparisons to transition between data and metadata states. Each state transition indicates the context in which to interpret the subsequent characters. Unfortunetly, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}; thus any character could be a state transition until deemed otherwise.
     42
     43Expat and Xerces-C are popular byte-a-time sequential parsers. Both are C/C++ based open-source XML parsers. Expat was originally released in 1998; it is currently used in Mozilla Firefox and Open Office \cite{expat}. Xerces-C was released in 1999 and is the foundation of the Apache XML project \cite{xerces}. The major disadvantage of the byte-at-a-time sequential approach to XML parsering is that each character incurs at least one conditional branch. The cummulative effect of branch mispredictions penalties are known to degrade parsing performance in proportion to the markup density of the source document \cite{CameronHerdyLin2008} (i.e., the proportion of XML-markup vs. XML-data).
    4844
    4945\subsection{Parallel XML Parsing}
    5046
    51 Parallel XML processing generally comes in one of two forms: multithreading and SIMD. Multithreaded XML parsers take advantage of parallism by first quickly preparsing the XML file to locate the key markup entities and determine the best workload distribution in which process the XML file using $n$-cores \cite{ZhangPanChiu09}. SIMD XML parsers leverage the SIMD registers to overcome the performance limitations of the sequential paradigm and inherently data dependent branch misprediction rates \cite{Cameron2010}. Two such SIMD 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, 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}.
    5248
    5349\subsubsection{Parabix1}
    5450
    55 Our first generation parallel bitstream XML parser---Parabix1---uses employs 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. 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}.
    5652
    5753\subsubsection{Parabix2}
    5854
    59 In our second generation XML parser---Parabix2---we address the replacement of sequential 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. To deal with these parallel cursors, three additional categories of bitstreams are introduced. Marker bitstreams are used to represent positions of interest in the parsing of a source data stream \cite{Cameron2010}. The appearance of a 1 at a position in a marker bitstream could, for example, denote the starting position an XML tag in the data stream. 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. Instead, error bitstreams are used to identify the position of parsing or well-formedness errors 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.
     55In our second generation XML parser, Parabix2, we address the replacement of sequential 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. To deal with these parallel cursors, three additional categories of bitstreams are introduced. Marker bitstreams are used to represent positions of interest in the parsing of a source data stream \cite{Cameron2010}. The appearance of a 1 at a position in a marker bitstream could, for example, denote the starting position an XML tag in the data stream. 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. Instead, error bitstreams are used to identify the position of parsing or well-formedness errors 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.
    6056
    6157%
Note: See TracChangeset for help on using the changeset viewer.