# Changeset 1368 for docs/HPCA2012/02-background.tex

Ignore:
Timestamp:
Aug 24, 2011, 3:55:35 PM (8 years ago)
Message:

large changes to section 2; minor edits to section 3

File:
1 edited

### Legend:

Unmodified
 r1302 \label{section:background} % This section provides % Extensible Markup Language (XML) is a core technology standard % of the World Wide Web Consortium (W3C) that provides a common % framework for encoding and communicating structured information. % In applications ranging from Office Open XML in % Microsoft Office to NDFD XML of the NOAA National Weather % Service, from KML in Google Earth to Castor XML in the Martian Rovers, % from ebXML for e-commerce data interchange to RSS for news feeds % from web sites everywhere, XML plays a ubiquitous role in providing % a common framework for data interoperability world-wide and beyond. % As XML 1.0 editor Tim Bray is quoted in the W3C celebration of XML at 10 years, % "there is essentially no computer in the world, desk-top, hand-held, % or back-room, that doesn't process XML sometimes." % % With this focus on performance however, relatively little attention % has been paid on reducing energy consumption in XML processing.  For example, in addressing % performance through multicore parallelism, one generally must % pay an energy price for performance gains because of the % increased processing required for synchronization. % This focus on reduction of energy consumption is a key topic in this % paper. We study the energy and performance % characteristics of several XML parsers across three generations % of x86-64 processor technology.  The parsers we consider are % the widely used byte-at-a-time parsers Expat and Xerces, as well the % Parabix1 and Parabix2 parsers based on parallel bit stream technology. % A compelling result is that the performance benefits of parallel bit stream technology % translate directly and proportionally to substantial energy savings. \subsection{XML} In 1998, the W3C officially adopted XML as a standard. 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}. % In 1998, the W3C officially adopted XML as a standard for data interchange. % Today, XML can be found everywhere from mobile websites and cloud computing to server-side database engines. % éšä»¶ % can't represent in verbose and not really sure if the google auto-translater is correct XML files can be classified as document-oriented'' or data-oriented'' \cite{DuCharme04}. Documented-oriented XML is designed for human readability, such as shown in Figure \ref{fig:sample_xml}; data-oriented XML files are intended to be parsed by machines and omit 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 application ready data. Extensible Markup Language (XML) is a core technology standard of the World Wide Web Consortium (W3C); it provides a common framework for encoding and communicating structured and semi-structured information. XML can represent virtually any type of information (i.e., content) in a descriptive fashion. XML markup encodes a description of an XML document's storage layout and logical structure. Because XML is intended to be human-readable, XML markup tags are often verbose by design \cite{TR:XML}. For example, Figure \ref{fig:sample_xml} provides a standard product list encapsulated within an XML document. All content is highlighted in bold. Anything that is not content is considered markup. \begin{figure}[h] { \scriptsize \begin{verbatim} Widget Bitoniau ABC $19.95 \end{verbatim} } \caption{Example XML Document}\label{fig:sample_xml} {\scriptsize \begin{center} \begin{tabbing} \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \\ {\ttfamily{\verb<Products\verb>}}\+ \\ {\ttfamily{\verb<Product ID=\verb"}}{\bfseries\ttfamily{0001}}{\ttfamily{\verb"\verb>}}\+ \\ {\ttfamily{\verb<ProductName Language=\verb"}}{\bfseries\ttfamily{English}}{\ttfamily{\verb"\verb>}}{\bfseries\ttfamily{Widget}}{\ttfamily{\verb</ProductName\verb> }}\\ {\ttfamily{\verb<ProductName Language=\verb"}}{\bfseries\ttfamily{French}}{\ttfamily{\verb"\verb>}}{\bfseries\ttfamily{Bitoniau}}{\ttfamily{\verb</ProductName\verb> }}\\ {\ttfamily{\verb<Company\verb>}}{\bfseries\ttfamily{ABC}}{\ttfamily{\verb</Company\verb> }}\\ {\ttfamily{\verb<Price\verb>}}{\bfseries\ttfamily{\$19.95}}{\ttfamily{\verb</Price\verb> }}\- \\ {\ttfamily{\verb</Product\verb> }}\- \\ {\ttfamily{\verb</Products\verb> }}\\ \end{tabbing} \end{center}} \caption{Sample XML Document}\label{fig:sample_xml} \end{figure} %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. %Cameron et al.'s work in \cite{CameronHerdyLin2008} demonstrates that both XML parser selection and XML document markup density have considerable impact on the computational costs of processing XML documents. Computational costs are reported in processor cycles per XML byte; markup density is defined as the ratio of XML markup bytes to the total number of XML document bytes. \subsection{XML Parsers} % However, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}. Traditional XML parsers process an XML document sequentially, a single byte-at-a-time, from the first to the last character in the source text. Each character is examined to distinguish between the XML-specific markup, such as an opening angle bracket \verb<', and the content held within the document. The character that the parser is currently processing is commonly referred to its {\it cursor position}. As the parser moves its cursor through the source document, it alternates between markup scanning / validation and content processing operations. In other words, traditional XML parsers operate as 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. Unfortunately, textual data tends to consist of variable-length items sequenced in generally unpredictable patterns \cite{Cameron2010}; thus any character could be a state transition until deemed otherwise. \subsection{Traditional XML Parsers} % However, textual data tends to consist of variable-length items in generally unpredictable patterns \cite{Cameron2010}. 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 of the source file. Each character of the source text is examined in turn 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 commonly referred to using the concept of a current 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. In other words, traditional XML parsers operate as 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. Unfortunately, textual data tends to consist of variable-length items sequenced in generally unpredictable patterns \cite{Cameron2010}; thus any character could be a state transition until deemed otherwise. A major disadvantage of the sequential byte-at-a-time approach to XML parsing is that processing an XML document requires at least one conditional branch per byte of source text. For example, Xerces-C, which is the most popular open-source C++ based XML parser and the foundation of the Apache XML project \cite{xerces}, uses a series of nested switch statements and state-dependent flag tests to control the parsing logic of the program. Our analysis, which we detail in {\bf SECTION XXX}, found that Xerces-C requires between 6 - 13 branches per byte of XML to support this form of control structure (depending on the ratio of markup vs. content). Cache utilization is also significantly reduced due to the manner in which markup and content must be scanned and buffered for future use. For instance, Xerces-C incurs $\sim$100 L1 cache misses per 1000 bytes of XML. % Branch mispredictions are known % to signficantly degrade XML parsing performance in proportion to the markup density of the source document % \cite{CameronHerdyLin2008} (i.e., the ratio of markup vs. content). Expat and Xerces-C are popular byte-a-time sequential parsers. Both are C/C++ based and open-source. Expat was originally released in 1998; it is currently used in Mozilla Firefox and provides the core functionality of many additional XML processing tools \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: %\begin{verbatim} %   XXXXXXXXXX   XERCES CODE   XXXXXXXXXX %\end{verbatim} A major disadvantage of the sequential byte-at-a-time approach to XML parsing is that each XML character incurs at least one conditional branch. The cumulative effect of branch mispredictions penalties are known to degrade XML parsing performance in proportion to the markup density of the source document \cite{CameronHerdyLin2008} (i.e., the proportion of XML-markup to XML-data). \subsection {Parallel XML Parsing} In general, parallel XML acceleration methods come in one of two forms: multithreaded approaches and SIMD-based techniques. Multithreaded XML parsers take advantage of multiple cores via number of strategies. Common strategies include preparsing the XML file to locate key partitioning points \cite{ZhangPanChiu09} and speculative p-DFAs \cite{ZhangPanChiu09}. SIMD XML parsers leverage the SIMD registers to overcome the performance limitations of the sequential byte-at-a-time processing model and its inherently data dependent branch misprediction rates.  Further, data parallel SIMD instructions allow the processor to perform the same operation on multiple pieces of data simultaneously.  The Parabix1 and Parabix2 parsers studied in this paper fall under the SIMD classification. The Parabix parser versions studied are described in further detail in Section \ref{section:parabix}. % Switch block logical % Branches % Cache utilization % \subsection {Parallel XML Parsing} % % % In general, parallel acceleration methods come in two forms: multithreaded approaches and % SIMD-based techniques. Multithreaded XML parsers take advantage of multiple cores via number of strategies. % Common strategies include preparsing the XML file to locate key partitioning points \cite{ZhangPanChiu09} % and speculative p-DFAs \cite{ZhangPanChiu09}. % To accelerate XML parsing performance, most of the recent % work has focused on parallelization through the use of multicore % parallelism for chip multiprocessors \cite{ZhangPanChiu09, ParaDOM2009, LiWangLiuLi2009}, % SIMD XML parsers leverage the SIMD registers to overcome the % performance limitations of the sequential byte-at-a-time processing model and its inherently data dependent % branch misprediction rates.  Further, data parallel SIMD instructions allow the processor to perform the same % operation on multiple pieces of data simultaneously.  The Parabix1 and Parabix2 parsers studied in this paper % fall under the SIMD classification. The Parabix parser versions studied are described in further detail in % Section \ref{section:parabix}. % while SIMD (Single Instruction Multiple Data) parallelism % has been of interest to Intel in designing new SIMD instructions\cite{XMLSSE42} % , as well as to the developers of parallel bit stream technology % \cite{CameronHerdyLin2008, Cameron2009, Cameron2010}. % Each of these approaches has shown considerable performance % benefits over traditional sequential parsing techniques that follow the % byte-at-a-time model. %\subsection {SIMD Operations}