Changeset 1003 for docs


Ignore:
Timestamp:
Mar 25, 2011, 4:59:09 PM (9 years ago)
Author:
ksherdy
Message:

Edits.

Location:
docs/PACT2011
Files:
2 edited

Legend:

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

    r991 r1003  
    11\section{Background}
    22\label{section:background}
    3 This section provides a brief overview of XML and traditional and parallel XML processing technology, and describes the key design and performance aspects of successive generations of the Parabix parallel XML processing technology. % clunky sounding...
     3This section provides a brief overview of XML and traditional and parallel XML processing technology. Section \ref{section:reserach} describes the key design and performance aspects of both generations of the Parabix parallel XML processing technology.
    44
     5\subsection{XML}
    56In 1998, the W3C officially adopted XML as a standard. XML is a platform-independent data interchange format. The defining characteristics of XML are that it can represent virtually any type of information through the use of self-describing markup tags and can easily store semi-structured data in a descriptive fashion. XML markup encodes a description of an XML document's storage layout and logical structure. Because XML was intended to be human-readable, XML markup tags are often verbose by design \cite{TR:XML}.
    67For example, a typical XML file could be:
     
    2526\end{figure}
    2627
    27 % <ProductName Language="CH">郚件</ProductName> % can't represent in verbose and not really sure if the google auto-translater is correct
     28% <ProductName Language="Chinese">郚件</ProductName> % can't represent in verbose and not really sure if the google auto-translater is correct
    2829
    2930
    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 to extract the information within. The role of an XML parser is to transform the text-based XML data into an application-ready format.
     31XML files can be classified as ``document-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 itself 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.
    3132%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.
    3233
     
    3738% However, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}.
    3839
    39 Traditional 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
     40Traditional 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. The current character that the parser is processing is refered to as its cursor position. As the parser moves the cursor through the source document, the parser 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.
    4041
    4142In 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.
    4243
    43 Expat 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).
     44Expat 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}. For example, the main loop of Xerces-C well-formedness scanner contains:
    4445
    45 \subsection{Parallel XML Parsing}
     46\begin{verbatim}
     47   XXXXXXXXXX   XERCES CODE   XXXXXXXXXX
     48\end{verbatim}
    4649
    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, 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}.
     50The 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).
    4851
    49 \subsubsection{Parabix1}
     52\subsection {Parallel XML Parsing}
    5053
    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. 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}.
     54In general, parallel XML acceleration methods comes in one of two forms: multithreaded approaches and SIMD-ized 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 serial join step typically follows. SIMD XML parsers leverage the SIMD registers to overcome the performance limitations of the byte-at-a-time sequential processing paradigm and inherent data dependent branch misprediction rates \cite{Cameron2010}. SIMD instructions allows the processor to perform the same operation on multiple pieces of data simultaneously. To our knowledge, the only SIMD-based XML parsers are Parabix1 and Parabix2, both of which were designed and developed by Cameron et al. \cite{CameronHerdyLin2008}. We discuss both versions of Parabix in Section \ref{section:reserach}.
    5255
    53 \subsubsection{Parabix2}
     56\subsection {SIMD Operations}
    5457
    55 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.
     58
     59
     60% Two such SIMD XML parsers, Parabix1 and Parabix2, utilizes parallel bit stream processing technology.
     61
     62
     63% Extract section 2.2 and merge into 3.   Add a new subsection
     64% in section 2 saying a bit about SIMD.   Say a bit about pure SIMD vertical
     65% operations and then mention the pack operations that allow
     66% us to implement transposition efficiently in parallel. 
     67% Also note that the SIMD registers support bitwise logic across
     68% their full width and that this is extensively used in our work.
     69
     70
     71% \subsection{Parallel XML Parsing}
     72%
     73% 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}.
     74%
     75% \subsubsection{Parabix1}
     76%
     77% 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}.
     78%
     79% \subsubsection{Parabix2}
     80%
     81% 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.
    5682
    5783%
  • docs/PACT2011/03-research.tex

    r954 r1003  
    11\section{Parabix}
    22\label{section:reserach}
    3 Describe key technology behind Parabix
    4 Introduce SIMD;
    5 Talk about SSE
    6 Highlight which SSE instructions are important
    7 TAlk about each pass in the parser; How SSE is used in every phase...
    8 Benefits of SSE in each phase.
    9 
    10 The results of \cite{CameronHerdyLin2008} showed that Parabix, the predecessor of Parabix2, was dramatically faster than both Expat 2.0.1 and Xerces-C++ 2.8.0.
    11 It is our expectation is that Parabix2 will outperform both Expat 2.0.1 and Xerces-C++ 3.1.1 in terms of energy consumption per source XML byte.
    12 This expectation is based on the relatively-branchless code composition of Parabix2 and the more-efficient utilization of last-level cache resources.
    13 The authors of \cite {bellosa2001, bircher2007, bertran2010} indicate that such factors have a considerable effect on overall energy consumption.
    14 Hence, one of the foci in our study is the manner in which straight line SIMD code influences energy usage.
     3%Describe key technology behind Parabix
     4%Introduce SIMD;
     5%Talk about SSE
     6%Highlight which SSE instructions are important
     7%TAlk about each pass in the parser; How SSE is used in every phase...
     8%Benefits of SSE in each phase.
    159
    1610
     11% Extract section 2.2 and merge into 3.   Add a new subsection
     12% in section 2 saying a bit about SIMD.   Say a bit about pure SIMD vertical
     13% operations and then mention the pack operations that allow
     14% us to implement transposition efficiently in parallel. 
     15% Also note that the SIMD registers support bitwise logic across
     16% their full width and that this is extensively used in our work.
     17%
     18% Also, it could be good to have a small excerpt of a byte-at-a-time
     19% scanning loop for XML, e.g., extracted from Xerces in section 2.1. 
     20% Just a few lines showing the while loop - Linda can tell you the file.
     21%
     22
     23% This section focuses on the
     24
     25
     26% 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}.
     27
     28% The results of \cite{CameronHerdyLin2008} showed that Parabix, the predecessor of Parabix2, was dramatically faster than both Expat 2.0.1 and Xerces-C++ 2.8.0.
     29% It is our expectation is that Parabix2 will outperform both Expat 2.0.1 and Xerces-C++ 3.1.1 in terms of energy consumption per source XML byte.
     30% This expectation is based on the relatively-branchless code composition of Parabix2 and the more-efficient utilization of last-level cache resources.
     31% The authors of \cite {bellosa2001, bircher2007, bertran2010} indicate that such factors have a considerable effect on overall energy consumption.
     32% Hence, one of the foci in our study is the manner in which straight line SIMD code influences energy usage.
     33
     34
     35\subsection{Parabix1}
     36
     37% 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.
     38
     39At 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 position throughout the parsing process. Where Parabix1 differs from the traditional parser is that it scans for key markup characters using a series of basis bitstreams.
     40A bitstream is simply a sequence of $0$s and $1$s, where there is one such bit in the bitstream for each character in a source data stream. A basis bitstream is a bitstream that consists of only transposed textual XML data.
     41In other words, a source character consisting of $M$ bits can be represented with $M$ bitstreams and
     42by utilizing $M$ SIMD registers of width $W$, it is possible to scan through $W$ characters in parallel.
     43The register width $W$ varies between 64-bit for MMX, 128-bit for SSE, and 256-bit for AVX.
     44Figure \ref{fig:inputstreams} presents an example of how we represent 8-bit ASCII characters using eight bitstreams. $B_0 \ldots B_7$ are the individual bitstreams. The $0$ bits in the bitstreams are represented by periods, so that the $1$ bits stand out.
     45
     46\begin{figure}[h]
     47\begin{center}
     48\begin{tabular}{cr}\\
     49source data $\vartriangleright$ & \verb`<t1>abc</t1><t2/>`\\
     50$B_0$ & \verb`..1.1.1.1.1....1.`\\
     51$B_1$ & \verb`...1.11.1..1..111`\\
     52$B_2$ & \verb`11.1...111.111.11`\\
     53$B_3$ & \verb`1..1...11..11..11`\\
     54$B_4$ & \verb`1111...1.111111.1`\\
     55$B_5$ & \verb`11111111111111111`\\
     56$B_6$ & \verb`.1..111..1...1...`\\
     57$B_7$ & \verb`.................`\\
     58\end{tabular}
     59\end{center}
     60\caption{Parallel Bitstream Example}
     61\label{fig:inputstreams}
     62\end{figure}
     63
     64In order represent the byte-oriented character data as parallel bitstreams, the source data is first loaded in sequential order and converted into its transposed representation through a series of packs, shifts, and bitwise operations.
     65Using the SIMD capabilities of current commodity processors, this transposition of source data to bitstreams incurs an amortized overhead of about 1 CPU cycle per byte for transposition \cite{CameronHerdyLin2008}. When parsing, we need to consider multiple properties of characters at different stages during the process. Using the basis bitstreams, it is possible to combine them using bitwise logic in order to compute character-class bitstreams;t hat is, streams that identify the positions at which characters belonging to a specific character class occur. For example, a ASCII character is an open angle bracket `<' if and only if $B_2 \land \ldots \land B_5 =$ 1 and the other basis bitstreams are 0 at the same position within the basis bitstreams. Once these character-class bitstreams are created, bit-scan operations, common to commodity processors, can be used for sequential markup scanning and data validation operations. A common operation in all XML parsers is identifying the start tags (`<') and their accompanying end tags (either ``/>'' or ``>'' depending whether the element tag is an empty element tag or not, respectively).
     66
     67\begin{figure}[h]
     68\begin{center}
     69\begin{tabular}{lr}\\
     70source data $\vartriangleright$ & \verb`<t1>abc<t1/><t2/>`\\
     71% $N = $ name chars & \verb`.11.111.11...11..`\\
     72$M_0 = 1$ & \verb`1................`\\
     73$M_1 = advance(M_0)$ & \verb`.1...............`\\
     74$M_2 = bitscan('>')$ & \verb`...1.............`\\
     75$M_3 = advance(M_2)$ & \verb`....1............`\\
     76$M_4 = bitscan('<')$ & \verb`.......1.........`\\
     77$M_5 = bitscan('/')$ & \verb`..........1......`\\
     78$M_6 = advance(M_5)$ & \verb`...........1.....`\\
     79$M_7 = bitscan('<')$ & \verb`.............1...`\\
     80$M_8 = bitscan('/')$ & \verb`...............1.`\\
     81$M_9 = advance(M_8)$ & \verb`................1`\\
     82% $M_2 \lor M_6 \lor M_9$    & \verb`...1.......1....1`\\
     83\end{tabular}
     84\end{center}
     85\caption{Parabix1 Start and End Tag Identification}
     86\label{fig:Parabix1StarttagExample}
     87\end{figure}
     88
     89
     90Unlike traditional parsers, these sequential operations are accelerated significantly since bit scan operations can perform up to $W$ 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}.
     91
     92
     93
     94
     95% In section 3, we should try to explain a bit more detail of the
     96% operation.   Under Parabix 1, a little bit on transposition
     97% and calculation of the [<] bitstream would be good, perhaps
     98% using the examples from the 2010 Technical Report or EuroPar submission.
     99
     100
     101\subsection{Parabix2}
     102
     103% Under Parabix 2 a little discussion of bitwise addition for
     104% scanning, perhaps again excerpted from the TR/EuroPar submission
     105% would be good.
     106
     107%In Parabix2, we replace the sequential single-cursor 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.
     108
     109In Parabix2, we replace the sequential single-cursor parsing using bit scan instructions with a parallel parsing method using bitstream addition. Unlike the single-cursor approach of Parabix1 (and conceptually of all sequential XML parsers), Parabix2 processes multiple cursors in parallel. For example, using the source data from Figure \ref{fig:Parabix1StarttagExample}, Figure \ref{fig:Parabix2StarttagExample} shows how Parabix2 identifies and moves each of the start tag markers forwards to the corresponding end tag. Like Parabix1, we assume that $N$ (the name chars) has been computed using the basis bitstreams and that
     110
     111\begin{figure}[h]
     112\begin{center}
     113\begin{tabular}{lr}\\
     114source data $\vartriangleright$ & \verb`<t1>abc<t1/><t2/>`\\
     115$N = $ name chars & \verb`.11.111.11...11..`\\
     116$M_0 = [<]$ & \verb`1......1....1....`\\
     117$M_1 = \texttt{advance}(M_0)$ & \verb`.1......1....1...`\\
     118$M_2 = \texttt{scanto}('/','>')$ & \verb`...1......1....1.`\\
     119$M_3 = \texttt{scanto}(>)$ & \verb`...1.......1....1`
     120\end{tabular}
     121\end{center}
     122\caption{Parabix2 Start and End Tag Identification}
     123\label{fig:Parabix2StarttagExample}
     124\end{figure}
     125
     126In 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. Although we do not show it in the prior examples, error bitstreams can be used to identify any well-formedness errors found 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.
     127
     128
Note: See TracChangeset for help on using the changeset viewer.