Changeset 883


Ignore:
Timestamp:
Feb 3, 2011, 6:53:53 PM (8 years ago)
Author:
ksherdy
Message:

Reduce Section 4 to 1.5 pages. Minor edits.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/EuroPar2011/europar-cameron.tex

    r879 r883  
    7373% to $W$ transitions with each $W$-bit binary addition operation.
    7474On processors supporting $W$-bit addition operations,
    75 the method can perform up to $W$ finite state transitions per clock cycle.
     75the method can perform up to $W$ finite state transitions per instruction.
    7676The method is based on the concept of parallel bitstream technology,
    7777in which parallel streams of bits are formed such that each stream
     
    121121
    122122Our research has been exploring a promising alternative approach, however, based on
    123 the concept of {\em parallel bit streams} \cite{PPoPP08,CameronHerdyLin2008,Cameron2009}.   
     123the concept of {\em parallel bit streams} \cite{Cameron2009,PPoPP08,CameronHerdyLin2008}.   
    124124In this approach, byte streams
    125125are first sliced into eight basis bit streams, one for each
     
    150150identify current scanning positions for multiple instances
    151151of a particular syntactic context within a byte stream.
    152 These multiple marker positions may be each be independently
     152These multiple marker positions may each be independently
    153153advanced in parallel using addition and masking. 
    154154The net result is a new scanning primitive that
     
    179179Section \ref{sec:compile} then considers
    180180the translation of high-level operations on unbounded bitstreams into
    181 equivalent low-level code using SIMD intrinsics in the the C programming
     181equivalent low-level code using SIMD intrinsics in the C programming
    182182language.
    183183Performance results are presented in section 7, comparing
     
    211211\subsection{Fundamentals}
    212212
    213 A 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 of characters.
    214 For parsing, and other text processing tasks, we need to consider multiple properties of characters at different stages during the parsing process. A bitstream can be associated with each of these properties, and hence there will be multiple (parallel) bitstreams associated with a source data stream of characters \cite{PPoPP08,Cameron2009}.
     213A 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.
     214For parsing, and other text processing tasks, we need to consider multiple properties of characters at different stages during the parsing process. A bitstream can be associated with each of these properties, and hence there will be multiple (parallel) bitstreams associated with a source data stream of characters \cite{Cameron2009,PPoPP08}.
    215215
    216216The starting point for bitstream methods are \emph{basis} bitstreams
     
    243243classes needed for XML parsing \cite{CameronHerdyLin2008}.
    244244Improved instruction sets using parallel extract operations or
    245 inductive doubling techniques may further reduce this overhead significantly \cite{HilewitzLee2006,CameronLin2009}.
     245inductive doubling techniques may further reduce this overhead significantly \cite{CameronLin2009,HilewitzLee2006}.
    246246
    247247Beyond the bitwise logic needed for character class determination,
     
    259259scanning or parsing of a source data stream.
    260260The appearance of a 1 at a position in a marker bitstream could, for example, denote
    261 the starting position an XML tag in the data stream.   In general, the set of
     261the starting position of an XML tag in the data stream.   In general, the set of
    262262bit positions in a marker bitstream may be considered to be the current
    263263parsing positions of multiple parses taking place in parallel throughout
     
    460460The figure omits determination
    461461of error bitstreams, processing of single-quoted attribute values and handling
    462 of empty and empty element tags, for simplicity.  In this figure, the first
     462of empty element tags, for simplicity.  In this figure, the first
    463463four rows show the source data and three character class bitstreams:
    464464$N$ for characters permitted in XML names,
     
    642642$M_f$ & \verb`____________1____________1_________________________1_`\\
    643643$m = n(M_f) - m_i$ & \verb`_111111111111__11111111111______11111111111111111111_`\\
    644 $M_1 = n(\verb:[<]:) \wedge \neg m$ & \verb`____________________________1_________________________`
     644$M_1 = n(\verb:[<]:) \wedge \neg m$ & \verb`____________________________1________________________`
    645645\end{tabular}
    646646\end{center}
     
    675675
    676676Taking advantage of Python's built-in support for
    677 arbitrary-size integers to represent unbounded bitstreams,
     677unbounded integers to represent arbitrary-size bitstreams,
    678678we have implemented a complete parsing prototype for XML
    679679using only bitstream addition, subtraction and bitwise logic.
     
    681681implementation of the scanning primitive $s$ as shown
    682682previously.   The operation $n$ is simply implemented using
    683 a shift left operation, while subtraction and bitwise logic
     683an upshift operation, while subtraction and bitwise logic
    684684are directly supported.
    685685
     
    693693
    694694In this section, we consider the full application of the parsing techniques
    695 of the previous section to the problem of XML well-formedness checking
    696 in accord with the requirements of the XML specification \cite{TR:XML}.
     695of the previous section to the problem of XML well-formedness checking \cite{TR:XML}.
    697696This application is useful as a well-defined and commercially significant
    698 example to assess the overall applicability of the techniques. 
    699 To what extent can well-formedness requirements of XML be
    700 completely discharged using parallel bitstream techniques.
     697example to assess the overall applicability of parallel bit stream techniques. 
     698To what extent can the well-formedness requirements of XML be
     699completely discharged using parallel bitstream techniques?
    701700Are those techniques worthwhile in every instance, or
    702 are there better alternatives for certain requirements?
     701do better alternatives exist for certain requirements?
    703702For those requirements that cannot be fully implemented
    704703using parallel bitstream technology alone, what
    705 preprocessing supports can be offered by parallel bitstream
     704preprocessing support can be offered by parallel bit stream
    706705technology to the discharge of these requirements in other ways?
    707706We address each of these questions in this section,
     
    715714Most of the requirements of XML well-formedness checking
    716715can be implemented using two particular types of computed
    717 bitstream: {\em error bitstreams}, which were introduced in the previous section, along with and {\em error-check bitstreams}.
    718 Recall that an error bitstream stream is a stream marking the location of definite errors according
    719 to a particular requirement.  For example, the
     716bitstream: {\em error bitstreams}, introduced in the previous section, and {\em error-check bitstreams}.
     717Recall that an error bitstream stream is a stream marking the location of definite errors in accordance with
     718a particular requirement.  For example, the
    720719$E_0$, $E_1$, and $E_2$ bitstreams as computed during parsing of
    721720decimal character references in Figure \ref{fig:decref}
    722 are error bitstreams.   An error check bitstream is one
     721are error bitstreams.  One bits mark definite errors and zero bits mark the
     722absence of error according to the requirement.   
     723Thus the complete absence of errors according to the
     724requirements listed may be determined by forming the
     725bitwise logical ``or'' of these bitstreams and confirming
     726that the resulting value is zero. An error check bitstream is one
    723727that marks potential errors to be further checked in
    724728some fashion during post-bitstream processing.   
     
    728732\verb:<![: sequences, but also marks positions to
    729733subsequently check for the complete opening
    730 delimiter  \verb:<![CDATA[: at each position.
    731 
    732 The error bitstreams that discharge various XML well-formedness
    733 requirements are shown in Table \ref{tab:errstreams}.
    734 One bits mark definite errors and zero bits mark the
    735 absence of error according to the requirement.   
    736 Thus the complete absence of errors according to the
    737 requirements listed may be determined by forming the
    738 bitwise logical ``or'' of these bitstreams and confirming
    739 that the resulting value is zero.   
    740 
    741 \begin{table}
    742 \begin{center}
    743 \begin{tabular}{|c|p{9cm}|} \hline
    744 Error Name & Error Description  \\ \hline
    745 UTF8\_err & Any invalid UTF-8 multibyte sequence. \\ \hline
    746 control\_ch & Any control character in the 0x00 through 0x1F range, except HT, LF or CR  \\ \hline
    747 FFFE\_FFFF & Unicode codepoints 0xFFFE and 0xFFFF are illegal in XML. \\ \hline
    748 CDATA\_end & \verb:]]>: cannot occur in content. \\ \hline
    749 ref\_syntax & Any syntax error in references, except for name errors. \\ \hline
    750 comment & ``\verb:--:'' in a comment without following ``\verb:>:'' \\ \hline
    751 PI\_err & No space after a PI target. \\ \hline
    752 tag\_syntax & Any error in start, empty or end tags, except for name errors. \\ \hline
    753 \end{tabular}
    754 \end{center}
    755 \caption{XML Error Bitstreams}
    756 \label{tab:errstreams}
    757 \end{table}
    758 
    759 Table \ref{tab:checkstreams} lists the XML error-check bitstreams
    760 that are computed together with the subsequent
    761 post-bitstream processing required.  In typical documents,
    762 most of these error-check streams will be quite sparse
     734delimiter  \verb:<![CDATA[: at each position.
     735
     736In typical documents, most of these error-check streams will be quite sparse
    763737or even zero.   Many of the error conditions could
    764738actually be fully implemented using bitstream techniques,
    765 at the cost of a number of additional logic and shift
     739but at the cost of a number of additional logical and shift
    766740operations.   In general, however, the conditions are
    767741easier and more efficient to check one-at-a-time using
     
    770744multiple instances occur within any given block, thus
    771745eliminating the benefit of parallel evaluation of the logic.
    772 
    773 
    774 \begin{table}
    775 \begin{center}
    776 \begin{tabular}{|c|p{7.5cm}|} \hline
    777 Error-Check & Checking Required  \\ \hline
    778 CDATA & \verb:<![CDATA[: at each position \\ \hline
    779 PI\_target & Target does not match \verb:[Xx][Mm][Ll]: \\ \hline
    780 Name-start-check & Character is legal as a name start character \\ \hline
    781 Name-check & Character is legal as a name character \\ \hline
    782 Entity\_check & Only \verb:lt:, \verb:gt:, \verb:amp:, \verb:apos:, and \verb:quot:
    783 are legal in DTD-less documents. \\ \hline
    784 Charref\_check & Referenced character is legal. \\ \hline
    785 Unique\_attname & Attribute names are unique within a tag.\\ \hline
    786 \end{tabular}
    787 \end{center}
    788 \caption{XML Error-Check Bitstreams}
    789 \label{tab:checkstreams}
    790 \end{table}
    791746
    792747The requirement for name checking merits comment.   XML
     
    811766
    812767Attribute names within a single XML start tag or empty
    813 element tag must be unique.   When a full symbol table
    814 is needed for other reasons, this requirement could be
    815 implemented using symbol lookup.   Without a general
    816 symbol mechanism, it is also possible to contemplate
    817 using a simple sequential search mechanism, given that
    818 the list of attributes tends to be very short.   Another
    819 efficient approach is the use of Bloom filters to implement
    820 this requirement \cite{DaiNiZhu2010}.
     768element tag must be unique.  This requirement could be
     769implemented using one of several different approaches. Standard
     770approaches include: sequential search, symbol lookup, and Bloom filters
     771\cite{DaiNiZhu2010}.
    821772
    822773In general, the use of error-check bitstreams is a straightforward,
    823774convenient and reasonably efficient mechanism for
    824 checking the well-formedness requirements in this table.
     775checking the well-formedness requirements.
    825776
    826777\subsection{Tag Matching}
     
    835786marking the occurrences of end tags.   In post-bitstream
    836787processing, we iterate through this computed bitstream
    837 to compare tags.   When a start tag is seen its name is
    838 pushed onto the stack to be subsequently popped when
    839 the corresponding end tag is identified.   At this point,
    840 the name match can be verified.  Empty tags are only relevant
    841 during this process in that they cannot be distinguished
    842 from start tags immediately.  Thus the names of empty
    843 tags are pushed on the stack when encountered and then
    844 removed immediately when the corresponding tag end is
    845 identified.
     788and match tags using an iterative stack-based approach.
    846789
    847790\subsection{Document Structure}
     
    856799Thus the requirements to check this top-level structure
    857800for well-formedness are relatively minor, with an overhead
    858 that is quite low for reasonably-sized or large files.
     801that is quite low for sufficiently sized files.
    859802
    860803\subsection{Summary}
     
    928871shows the document characteristics of the XML instances selected for this performance study,
    929872including both document-oriented and data-oriented XML files.
    930 The jawiki.xml and dewiki.xml XML files are document-oriented XML instances of Wikimedia books, written in German and Japanese, respectively. The remaining files are data-oriented.  The roads.gml file is an instance of Geography Markup Language (GML), a modeling language for geographic systems as well as an open interchange format for geographic transactions on the Internet \cite{GML04}.  The po.xml file is an example of purchase order data, while the soap.xml file contains a large SOAP message.
     873The jawiki.xml and dewiki.xml XML files are document-oriented XML instances of Wikimedia books, written in Japanese and German, respectively. The remaining files are data-oriented.  The roads.gml file is an instance of Geography Markup Language (GML),
     874a modeling language for geographic information systems as well as an open interchange format for geographic transactions on the Internet \cite{GML04}.  The po.xml file is an example of purchase order data, while the soap.xml file contains a large SOAP message.
    931875Markup density is defined as the ratio of the total markup contained within an XML file to the total XML document size.
    932876This metric is reported for each document.
     
    934878\begin{table*}[tbh]
    935879\begin{center}
    936 \begin{tabular}{|c|r|r|r|r|r|}
     880\begin{tabular}{|c||r|r|r|r|r|}
    937881\hline
    938882File Name               & dewiki.xml            & jawiki.xml            & roads.gml     & po.xml        & soap.xml \\ \hline   
     
    991935\begin{tabular}{|c|c||c|c|c|c|c|}
    992936\hline
    993 Parser Class & Parser & dewiki  & jawiki    & gml  & po & soap  \\ \hline
     937Parser Class & Parser & dewiki.xml  & jawiki.xml    & roads.gml  & po.xml & soap.xml  \\ \hline
    994938\multirow{3}{*}{Byte-at-a-time} & Xerces (DOM)    &    39.8    &   46.7    &  81.6    &   122.5   &    143.7  \\ \cline{2-7}
    995939& Xerces (SAX)   &     24.0   &    30.4     &  40.3    &   54.3    &   64.3     \\ \cline{2-7}
Note: See TracChangeset for help on using the changeset viewer.