source: docs/EuroPar2011/europar-cameron.tex @ 898

Last change on this file since 898 was 898, checked in by cameron, 9 years ago

Fit Table 2 for width

File size: 41.2 KB
3%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
5% This is the LaTeX source for the instructions to authors using
6% the LaTeX document class 'llncs.cls' for contributions to
7% the Lecture Notes in Computer Sciences series.
8%       Springer Heidelberg 2006/05/04
10% It may be used as a template for your own input - copy it
11% to a new file with a new name and use it as the basis
12% for your article.
14% NB: the document class 'llncs' has its own and detailed documentation, see
27\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
28\urldef{\mailsb}\path|anna.kramer, leonie.kunz, christine.reiss, nicole.sator,|
29\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}|   
35\mainmatter  % start of an individual contribution
40% first the title is needed
41\title{Parallel Scanning with Bitstream Addition: An XML Case Study}
43% a short form should be given in case it is too long for the running head
44\titlerunning{Parallel Scanning with Bitstream Addition}
46% the name(s) of the author(s) follow(s) next
48% NB: Chinese authors should write their first names(s) in front of
49% their surnames. This ensures that the names appear correctly in
50% the running heads and the author index.
52\author{Robert D. Cameron
54\and Ehsan Amiri \and Kenneth S. Herdy \and Dan Lin \and Thomas C. Shermer \and Fred P. Popowich}
57\authorrunning{Cameron {\em et al}}
59% the affiliations are given next; don't give your e-mail address
60% unless you accept that it will be published
61\institute{Simon Fraser University, Surrey, BC, Canada\\
62\email{\{cameron, eamiri, ksherdy, lindanl, shermer, popowich\}}
69A parallel scanning method using the concept of bitstream addition is
70introduced and studied in application to the problem of XML
71parsing and well-formedness checking.   
72% The method parallelizes
73% finite-state transitions, using carry propagation to achieve up
74% to $W$ transitions with each $W$-bit binary addition operation.
75On processors supporting $W$-bit addition operations,
76the method can perform up to $W$ finite state transitions per instruction.
77The method is based on the concept of parallel bitstream technology,
78in which parallel streams of bits are formed such that each stream
79comprises bits in one-to-one correspondence with the character
80code units of a source data stream.    Parsing routines are initially
81prototyped in Python using its native support for unbounded
82integers to represent arbitrary-length  bitstreams.  A compiler
83then translates the Python code into low-level C-based implementations.
84These low-level implementations take advantage of
85the SIMD (single-instruction multiple-data) capabilities of commodity
86processors to yield a dramatic speed-up over
87traditional alternatives employing byte-at-a-time parsing.
88%\keywords{SIMD text processing, parallel bitstream technology, XML, parsing}
89\keywords{SIMD text processing, parallel bitstreams, XML, parsing}
95Although the finite state machine methods used
96in the scanning and parsing of text streams is considered to be the
97hardest of the ``13 dwarves'' to parallelize \cite{Asanovic:EECS-2006-183},
98parallel bitstream technology shows considerable promise for these
99types of applications\cite{PPoPP08,CameronHerdyLin2008,Green2009}.
100In this approach, character streams are processed $N$ positions at
101a time using the $N$-bit SIMD registers commonly found on commodity
102processors (e.g., 128-bit XMM registers on Intel/AMD chips). 
103This is achieved by first slicing the byte streams into eight separate
104basis bitstreams, one for each bit position within the byte. 
105These basis bitstreams are then combined with bitwise logic and
106shifting operations to compute further parallel bit streams of
107interest, such as the \verb:[<]: bit stream marking the position
108of all opening angle brackets in an XML document.
110Using these techniques as well as the {\em bit scan} 
111instructions also available on commodity processors, the
112Parabix 1 XML parser was shown to considerably accelerate XML
113parsing in comparison with conventional byte-at-a-time parser
114in applications such as statistics gathering \cite{CameronHerdyLin2008} and
115as GML to SVG conversion \cite{Herdy2008}
116Other efforts to accelerate XML parsing include the use of custom
117XML chips \cite{Leventhal2009}, FPGAs \cite{DaiNiZhu2010}, and
118multithread/multicore speedups based on fast preparsing \cite{ZhangPanChiu09}.
120In this paper, we further increase the parallelism in our methods
121by introducing a new parallel scanning primitive using bitstream
122addition.   In essence, this primitive replaces the sequential bit
123scan operations underlying Parabix 1 with a new approach that
124independently advances multiple marker bits in parallel using
125simple addition and logic operations.   This paper documents the
126technique and evaluates it in application to the problem of XML
127parsing and well-formedness checking.
129Section 2 reviews the basics of parallel bitstream technology
130and introduces our new parallel scanning primitive.  Section 3
131goes on to show how this primitive may be used in XML scanning
132and parsing, while Section 4 discusses the construction of a
133complete XML well-formedness checker based on these techniques.
134Section 5 then briefly describes the compiler technology used to
135generate the low level code for our approach.  A performance
136study in Section 6 shows that the new Parabix 2 parser is
137dramatically faster than traditional byte-at-a-time parsers
138as well as the original Parabix 1 parser, particularly for
139dense XML markup.  Section 7 concludes the paper.
142% The remainder of this paper is organized as follows.
143% Section 2 reviews the basics of parallel bitstream technology
144% and introduces our new parallel scanning primitive.
145% Section 3 illustrates how this primitive may be used
146% in the lexical processing of XML references including the
147% parallel identification of errors.   Section 4 goes on
148% to consider the more complex task of XML tag processing
149% that goes beyond mere tokenization.
150% Building on these methods, Section 5 describes how to
151% construct a
152% complete solution to the problem of XML parsing and
153% well-formedness checking, in order
154% to gauge the applicability and power of the techniques.
155% Section \ref{sec:compile} then considers
156% the translation of high-level operations on unbounded bitstreams into
157% equivalent low-level code using SIMD intrinsics in the C programming
158% language.
159% Performance results are presented in section 7, comparing
160% the results of our generated implementations in comparison with
161% a number of existing alternatives.
162% The paper concludes with
163% comments on the current status of the work and directions for
164% further research.
166\section{The Parallel Bitstream Method}\label{sec:parabit}
171source data $\vartriangleleft$ & \verb`----173942---654----1----49731----321--`\\
172$B_7$ & \verb`.......................................`\\
173$B_6$ & \verb`.......................................`\\
174$B_5$ & \verb`111111111111111111111111111111111111111`\\
175$B_4$ & \verb`....111111...111....1....11111....111..`\\
176$B_3$ & \verb`1111...1..111...1111.1111.1...1111...11`\\
177$B_2$ & \verb`1111.1..1.1111111111.11111.1..1111...11`\\
178$B_1$ & \verb`.....11..1...1.............11.....11...`\\
179$B_0$ & \verb`11111111..111.1.111111111.111111111.111`\\
180\verb:[0-9]: & \verb`....111111...111....1....11111....111..`\\
183\caption{Basis and Character-Class Bitstreams}
189A 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.
190For 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.
192The starting point for bitstream methods are \emph{basis} bitstreams
193and their use in determining \emph{character-class} bitstreams.
194The $k$th basis bitstream $B_k$ consists of the $k$th bit (0-based, starting at the LSB)
195of each character in the source data stream;
196thus each $B_k$ is dependent on the encoding of the source characters (ASCII, UTF-8, UTF-16, etc.).
197Given these basis bitstreams, it is then possible to combine them
198using bitwise logic in order to compute character-class
199bitstreams, that is, streams that identify the positions at which characters belonging
200to a particular class occur.  For example, the character class bitstream
201$D=$\verb:[0-9]: marks with $1$s the positions at which decimal digits
202occur.    These bitstreams are illustrated in Figure \ref{fig:inputstreams},
203for an example source data stream consisting of digits and hyphens.
204This figure also illustrates some of our conventions for figures:  the left triangle $\vartriangleleft$ after
205``source data'' indicates that all streams are read from right to left
206(i.e., they are in little-endian notation).  We also use hyphens
207in the input stream represent any character that is not relevant to a character
208class under consideration, so that relevant characters stand out.
209Furthermore, the $0$ bits in the bitstreams are represented by periods,
210so that the $1$ bits stand out.
213Transposition of source data to basis bitstreams and calculation
214of character-class streams in this way is an overhead on parallel bit
215stream applications, in general.   However, using the SIMD
216capabilities of current commodity processors, these operations are quite
217fast, with an amortized overhead of about 1 CPU cycle per byte for
218transposition and less than 1 CPU cycle per byte for all the character
219classes needed for XML parsing \cite{CameronHerdyLin2008}.
220%Improved instruction sets using parallel extract operations or
221%inductive doubling techniques may further reduce this overhead significantly \cite{CameronLin2009,HilewitzLee2006}.
223Beyond the bitwise logic needed for character class determination,
224we also need \emph{upshifting} to deal with sequential combination.
225The upshift $n(S)$ of a bitstream $S$ is obtained by shifting the bits in $S$ one position forward,
226then placing a $0$ bit in the starting position of the bitstream; $n$ is meant to be mnemonic of ``next''.
227In $n(S)$, the last bit of $S$ may be eliminated or retained for error-testing purposes.
229\subsection{A Parallel Scanning Primitive}
231In this section, we introduce the principal new feature of the paper,
232a parallel scanning method based on bitstream addition.   Key to this
233method is the concept of {\em marker} bitstreams. 
234Marker bitstreams are used to represent positions of interest in the
235scanning or parsing of a source data stream.
236The appearance of a 1 at a position in a marker bitstream could, for example, denote
237the starting position of an XML tag in the data stream.   In general, the set of
238bit positions in a marker bitstream may be considered to be the current
239parsing positions of multiple parses taking place in parallel throughout
240the source data stream.
242Figure \ref{fig:scan1} illustrates the basic concept
243underlying parallel parsing with bitstream addition.
244All streams are shown in little-endian
245representation, with streams reading from right-to-left.
246The first row shows a source data stream that includes several
247spans of digits, together with other nondigit characters shown
248as hyphens.  The second row specifies the parsing problem
249using a marker bitstream $M_0$ to mark four initial marker
250positions.  In three instances, these markers are at
251the beginning (i.e., little end) of a span, while one is in
252the middle of a span.
253The parallel parsing task is to move each
254of the four markers forward through the corresponding spans of
255digits to the immediately following positions.
260source data $\vartriangleleft$ & \verb`----173942---654----1----49731----321--`\\
261$M_0 =$ & \verb`.........1.....1....1......1...........`\\
262$D = $\verb:[0-9]: & \verb`....111111...111....1....11111....111..`\\
263$M_0 + D$ & \verb`...1........1......1....1...11....111..`\\
264$M_1 = (M_0 + D) \wedge \neg D$ & \verb`...1........1......1....1..............`
269\caption{Parallel Scan Using Bitstream Addition and Mask}
273The third row of Figure \ref{fig:scan1}
274shows the derived character-class bitstream $D$ identifying
275positions of all digits in the source stream. 
276The fourth row then illustrates the key concept: marker movement
277is achieved by binary addition of the marker and character
278class bitstreams.  As a marker 1 bit is combined using binary addition to
279a span of 1s, each 1 in the span becomes 0, generating
280a carry to add to the next position to the left.
281For each such span, the process terminates at the left end
282of the span, generating a 1 bit in the immediately
283following position.   These generated 1 bits represent
284the moved marker bits.   However, the result of the
285addition also produces some additional bits that are
286not involved in the scan operation.   
287However, these are easily removed as shown in the fifth row,
288by applying bitwise logic to mask
289off any bits from the digit bitstream; these can never
290be marker positions resulting from a scan.
291The addition and masking technique allows matching of
292the regular expression \verb:[0-9]*: for any reasonable
293(conflict-free) set of initial markers specified in $M_0$.
296% The addition and masking technique allows matching of
297% the regular expression \verb:[0-9]*: for any reasonable
298% (conflict-free) set of initial markers specified in $M_0$.
299% A conflict occurs when a span from one marker would run
300% into another marker position.   However, such conflicts
301% do not occur with the normal methods of marker bitstream
302% formation, in which unique syntactic features of
303% the input stream are used to specify the initial marker
304% positions.
306In the remainder of this paper, the notation $s(M, C)$
307denotes the operation to scan
308from an initial set of marker positions $M$ through
309the spans of characters belonging to a character class $C$ found at each position.
310\[s(M, C) = (M_0 + C)  \wedge \neg C\]
313\section{XML Scanning and Parsing}
316We now consider how the parallel scanning primitive can
317be applied to the following problems in scanning and
318parsing of XML structures:  (1) parallel scanning of XML decimal character references,
319and (2) parallel parsing of XML start tags.
320The grammar of these structures is shown in Figure \ref{fig:xmlgrmr}.
325DecRef & ::=   &        '\verb:&#:' Digit+ '\verb:;:'  \\
326Digit  & ::=   &         \verb:[0-9]:\\
327STag         &  ::=   &        '\verb:<:' Name (WS  Attribute)* WS? '\verb:>:'  \\
328Attribute & ::=   &        Name WS? '=' WS? AttValue \\
329AttValue  &           ::=   &        `\verb:":' \verb:[^<"]*: `\verb:":' $|$ ``\verb:':'' \verb:[^<']*: ``\verb:':'' \\
330%DQuoted & ::= & \verb:[^<"]*:  \\
331%SQuoted & ::= & \verb:[^<']*:
334\caption{XML Grammar: Decimal Character References and Start Tags}
341\multicolumn{2}{l}{source data $\vartriangleright$}     
342                                         & \verb`-&#978;-&9;--&#;--&#13!-`\\
343$M_0$ &                                  & \verb`.1......1....1....1.....`\\
344$M_1$ & $ = n(M_0)$                      & \verb`..1......1....1....1....`\\
345$E_0$ & $ = M_1 \wedge \neg $\verb:[#]:  & \verb`.........1..............`\\
346$M_2$ & $ = n(M_1 \wedge \neg  E_0)$     & \verb`...1...........1....1...`\\
347$E_1$ & $ = M_2 \wedge \neg  D$          & \verb`...............1........`\\
348$M_3$ & $ = s(M_2 \wedge \neg  E_1, D)$  & \verb`......1...............1.`\\
349$E_2$ & $ = M_3 \wedge \neg  $\verb:[;]: & \verb`......................1.`\\
350$M_4$ & $ = M_3 \wedge \neg  E_2$        & \verb`......1.................`\\
351$E $  & $= E_0 \, | \, E_1 \, | \, E_2$  & \verb`.........1.....1......1.`
354\caption{Parsing Decimal References}
358Figure \ref{fig:decref} shows the parallel parsing of
359decimal references together with error checking.
360The source data includes four instances of potential
361decimal references beginning with the \verb:&: character.
362Of these, only the first one is legal according to
363the decimal reference syntax, the other three instances
364are in error.   These references may be parsed in
365parallel as follows.  The
366starting marker bitstream $M_0$ is formed from the \verb:[&]:
367character-class bitstream as shown in the second row.  The next row shows the
368result of the marker advance operation $n(M_0)$ to
369produce the new marker bitstream $M_1$.  At this point,
370a hash mark is required, so the first error bitstream $E_0$ is
371formed using a bitwise ``and'' operation combined with negation,
372to indicate violations of this condition.
373Marker bitstream $M_2$ is then defined as those positions
374immediately following any $M_1$ positions not in error.
375In the following row, the condition that at least
376one digit is required is checked to produce error bitstream $E_1$.
377A parallel scan operation is then applied through the
378digit sequences as shown in the next row to produce
379marker bitstream $M_3$.  The final error bitstream $E_2$ is
380produced to identify any references without a
381closing semicolon.
382In the penultimate row, the final marker bitstream $M_4$ marks the
383positions of all fully-checked decimal references, while the
384last row defines a unified error bitstream $E$ 
385indicating the positions of all detected errors.
388One question that may arise is: how are marker bitstreams initialized?   In general,
389this is an important problem, and dependent on the task at hand.   
390In the XML parsing context,
391we rely on an important property of well-formed
392XML: after an initial filtering pass to identify
393XML comments, processing instructions and CDATA
394sections, every remaining \verb:<: in the
395file must be the initial character of a start,
396end or empty element tag, and every remaining \verb:&:
397must be the initial character of a general entity
398or character reference. These assumptions permit easy creation of
399marker bitstreams for XML tags and XML references.
401The parsing of XML start tags is a richer problem, involving
402sequential structure of attribute-value pairs as shown in Figure \ref{fig:xmlgrmr}.
403Using the bitstream addition technique, our method
404is to start with the opening angle bracket of all tags as
405the initial marker bitstream for parsing the tags in parallel,
406advance through the element name and then use an iterative
407process to move through attribute-value pairs.
409Figure \ref{fig:stag-ex}
410illustrates the parallel parsing of three XML start tags.
411The figure omits determination
412of error bitstreams, processing of single-quoted attribute values and handling
413of empty element tags, for simplicity.  In this figure, the first
414four rows show the source data and three character class bitstreams:
415$N$ for characters permitted in XML names,
416$W$ for whitespace characters,
417and $Q$ for characters permitted within a double-quoted attribute value string. 
423source data $\vartriangleright$ & \verb`--<e a= "137">---<el2 a="17" a2="3379">---<x>--`\\
424$N = $ name chars & \verb`11.1.1...111..111.111.1..11..11..1111..111.1.11`\\
425$W = $ white space & \verb`....1..1.............1......1..................`\\
426$Q = \neg$\verb:[">]: & \verb`11.11111.111.1111.111111.11.1111.1111.1111.1111`\\
428$M_0$ & \verb`..1..............1........................1....`\\
429$M_1 = n(M_0)$ & \verb`...1..............1........................1...`\\
430$M_{0,7} = s(M_1, N)$ & \verb`....1................1......................1..`\\
431$M_{0,8} = s(M_{0,7}, W) \wedge \neg$\verb:[>]: & \verb`.....1................1........................`\\
433$M_{1,1} = s(M_{0,8}$ & \verb`......1................1.......................`\\
434$M_{1,2} = s(M_{1,1}, W) \wedge$\verb:[=]: & \verb`......1................1.......................`\\
435$M_{1,3} = n(M_{1,2})$ & \verb`.......1................1......................`\\
436$M_{1,4} = s({1,3}, W) \wedge$\verb:["]: & \verb`........1...............1......................`\\
437$M_{1,5} = n(M_{1,4})$ & \verb`.........1...............1.....................`\\
438$M_{1,6} = s(M_{1,5}, Q) \wedge$\verb:["]: & \verb`............1..............1...................`\\
439$M_{1,7} = n(M_{1,6})$ & \verb`.............1..............1..................`\\
440$M_{1,8} = s(M_{1,7}, W) \wedge \neg$\verb:[>]: & \verb`.............................1.................`\\
442$M_{2,1} = s(M_{1,8}, N)$ & \verb`...............................1...............`\\
443$M_{2,2} = s(M_{2,1}, W) \wedge$\verb:[=]: & \verb`...............................1...............`\\
444$M_{2,3} = n(M_{2,2})$ & \verb`................................1..............`\\
445$M_{2,4} = s(M_{2,3}, W) \wedge$\verb:["]: & \verb`................................1..............`\\
446$M_{2,5} = n(M_{2,4})$ & \verb`.................................1.............`\\
447$M_{2,6} = s(M_{2,5}, Q) \wedge$\verb:["]: & \verb`.....................................1.........`\\
448$M_{2,7} = n(M_{2,6})$ & \verb`......................................1........`\\
449$M_{2,8} = s(M_{2,7}, W) \wedge \neg$\verb:[>]: & \verb`...............................................`
452\caption{Start Tag Parsing}
457The parsing process is illustrated in the remaining rows of the
458figure.    Each successive row shows the set of parsing markers as they
459advance in parallel using bitwise logic and addition.
460Overall, the sets of marker transitions can be divided into three groups.
462The first group
463$M_0$ through $M_{0,8}$ shows the initiation of parsing for each of the
464 tags through the
465opening angle brackets and  the element names, up to the first
466attribute name, if present.  Note that the there are no attribute names
467in the final tag shown, so the corresponding marker becomes zeroed
468out at the closing angle bracket.
469Since $M_{0,8}$ is not all $0$s, the parsing continues.
471The second group of marker transitions
472$M_{1,1}$ through $M_{1,8}$ deal with the parallel parsing of the first attribute-value
473pair of the remaining tags.
474After these operations, there are no more attributes
475in the first tag, so its corresponding marker becomes zeroed out.
476However, $M_{1, 8}$ is not all $0$s, as the second tags still has an unparsed attribute-value pair.
477Thus, the parsing continues.
479The third group of marker transitions $M_{2,1}$ through $M_{2,8}$ deal with the parsing of
480the second attribute-value pair of this tag.  The
481final transition to $M_{2,8}$ shows the zeroing out of all remaining markers
482once two iterations of attribute-value processing have taken place.
483Since $M_{2,8}$ is all $0$s, start tag parsing stops.
485The implementation of start tag processing uses a while loop that
486terminates when the set of active markers becomes zero,
487i.e.\  when some $M_{k, 8} = 0$.
489as an iteration over unbounded bitstreams, all start tags in the document
490are processed in parallel, using a number of iterations equal to the maximum
491number of attribute-value pairs in any one tag in the document.   
492However, in block-by-block processing, the cost of iteration is considerably reduced; the iteration for
493each block only requires as many steps as there are attribute-value pairs
494overlapping the block.
499%\subsection{Name Scans}
500%To illustrate the scanning of the name found in an XML start tag,
501%let us consider a sequence that might be found in an HTML file,
502%\verb:<div id="myid">:,
503%which is shown as the source data stream in Figure \ref{fig:stag-scan}.
508%source data & \verb:<div id="myid">:\\
509%$M_0$ & \verb`1..............`\\
510%$C_0$ & \verb`.111.11...1111.`\\
511%$M_1 = n(M_0)$ & \verb`.1.............`\\
512%$M_2 = s(M_1, D_0) \wedge \neg C_0$ & \verb`....1.........`\\
513%lastline & \verb`...............`
516%\caption{Scanning Names}
520%If we set our initial marker bitstream according to the procedure outlined in our discussion of marker bitstream initialization, we %obtain the bitstream $M_0$.
521%According to the grammar in Figure \ref{fig:stag-grmr}, we can then look for a \verb:Name: in an \verb:STag: after we have found a %5\verb:<:.
522%So, $M_1$ is the marker bitstream for the starting position of our name.
523%Although we do not know the length of the name, the $C_0$ bit vector can easily be set to $1$ for the characters that can be contained %in a name.
524%We can then use the scan function in a manner similar to how it was used in Figure \ref{fig:scan2} to scan through the entire name to %identify its end position.
526Following the pattern shown here, the remaining syntactic
527features of XML markup can similarly be parsed with
528bitstream based methods.   One complexity is that the
529parsing of comments,
530CDATA sections and processing instructions must be
531performed first to determine those regions of text
532within which ordinary XML markups are not parsed (i.e.,
533within each of these types of construct.   This is handled
534by first performance the parsing of these structures and
535then forming a {\em mask bitstream}, that is, a stream that
536identifies spans of text to be excluded from parsing
537(comment and CDATA interiors, parameter text to processing instructions).
540\section{XML Well-Formedness}
542In this section, we consider the full application of the parsing techniques
543of the previous section to the problem of XML well-formedness checking \cite{TR:XML}.
544% This application is useful as a well-defined and commercially significant
545% example to assess the overall applicability of parallel bitstream techniques.
546% To what extent can the well-formedness requirements of XML be
547% completely discharged using parallel bitstream techniques?
548% Are those techniques worthwhile in every instance, or
549% do better alternatives exist for certain requirements?
550% For those requirements that cannot be fully implemented
551% using parallel bitstream technology alone, what
552% preprocessing support can be offered by parallel bitstream
553% technology to the discharge of these requirements in other ways?
554% We address each of these questions in this section,
555% and look not only at the question of well-formedness, but also at
556We look not only at the question of well-formedness, but also at
557the identification of error positions in documents that
558are not well-formed.
561%\subsection{Error and Error-Check Bitstreams}
563Most of the requirements of XML well-formedness checking
564can be implemented using two particular types of computed
565bitstream: {\em error bitstreams}, introduced in the previous section, and {\em error-check bitstreams}.
566Recall that an error bitstream stream is a stream marking the location of definite errors in accordance with
567a particular requirement.  For example, the
568$E_0$, $E_1$, and $E_2$ bitstreams as computed during parsing of
569decimal character references in Figure \ref{fig:decref}
570are error bitstreams.  One bits mark definite errors and zero bits mark the
571absence of an error.   
572% absence of error according to the requirement.   
573Thus the complete absence of errors according to the
574requirements listed may be determined by forming the
575bitwise logical ``or'' of these bitstreams and confirming
576that the resulting value is zero. An error check bitstream is one
577that marks potential errors to be further checked in
578some fashion during post-bitstream processing.   
579An example is the bitstream marking the start positions
580of CDATA sections.   This is a useful information stream
581computed during bitstream processing to identify opening
582\verb:<![: sequences, but also marks positions to
583subsequently check for the complete opening
584delimiter  \verb:<![CDATA[: at each position.
586In typical documents, most of these error-check streams will be quite sparse
587% or even zero.   Many of the error conditions could
588or even zero.   Many error conditions could
589actually be fully implemented using bitstream techniques,
590but at the cost of a number of additional logical and shift
591operations.   In general, the conditions are
592easier and more efficient to check one-at-a-time using
593multibyte comparisons on the original source data stream.
594With very sparse streams, it is very unlikely that
595multiple instances occur within any given block, thus
596eliminating the benefit of parallel evaluation of the logic.
598The requirement for name checking merits comment.   XML
599names may use a wide range of Unicode character values.
600It is too expensive to check every instance of an XML name
601against the full range of possible values.   However, it is
602possible and quite inexpensive to use parallel bitstream
603techniques to verify that any ASCII characters within a name
604are indeed legal name start characters or name characters.
605Furthermore, the characters that may legally follow a
606name in XML are confined to the ASCII range.  This makes
607it useful to define a name scan character class to include all the legal ASCII characters
608for names as well as all non-ASCII characters. 
609A namecheck character class bitstream will then be defined to identify nonASCII
610characters found within namescans.   In most documents
611this bitstream will be all $0$s; even in documents with substantial
612internationalized content, the tag and attribute names used
613to define the document schema tend to be confined to the
614ASCII repertoire.   In the case that this bitstream is nonempty,
615the positions of all 1 bits in this bitstream denote characters
616that need to be individually validated.
618Attribute names within a single XML start tag or empty
619element tag must be unique.  This requirement could be
620implemented using one of several different approaches. Standard
621approaches include: sequential search, symbol lookup, and Bloom filters
624% In general, the use of error-check bitstreams is a straightforward,
625% convenient and reasonably efficient mechanism for
626% checking the well-formedness requirements.
628%\subsection{Tag Matching}
630Except for empty element tags, XML tags come in pairs with
631names that must be matched.   To discharge this requirement,
632we form a bitstream consisting of the disjunction of three
633bitstreams formed during parsing: the bitstream marking the
634positions of start or empty tags (which have a common
635initial structure), the bitstream marking tags that end using
636the empty tag syntax (``\verb:/>:''), and the bitstream
637marking the occurrences of end tags.   In post-bitstream
638processing, we iterate through this computed bitstream
639and match tags using an iterative stack-based approach.
641%\subsection{Document Structure}
643An XML document consists of a single root element with recursively
644defined structure together with material in the document
645prolog and epilogs.  Verifying this top-level structure and
646the structure of the prolog and epilog material is not
647well suited to parallel bitstream techniques, in particular, nor
648to any form of parallelism, in general.  In essence, the
649prolog and epilog materials occur once per document instance
650Thus the requirements to check this top-level structure
651for well-formedness are relatively minor, with an overhead
652that is quite low for sufficiently sized files.
656Overall, parallel bitstream techniques are quite well-suited to
657verification problems such as XML well-formedness checking. 
658Many of the character validation and syntax checking requirements
659can be conveniently and efficiently implemented using error streams.
660Other requirements are also supported by the computation of
661error-check streams for simple post-bitstream processing or
662composite stream over which iterative stack-based procedures
663can be defined for checking recursive syntax.
665\section{Compilation to Block-Based Processing} 
667While a Python implementation of the techniques described in the previous section works on unbounded bitstreams, a corresponding
668C implementation needs to process an input stream in blocks of size equal to the
669SIMD register width of the processor it runs on.
670So, to convert Python code into C, the key question becomes how
671to transfer information from one block to the next.
673The answer lies in the use of {\em carry bits}.
674The parallel scanning primitive uses only addition and bitwise logic.
675The logic operations do not require information flow
676accross block boundaries, so the information flow is entirely
677accounted by the carry bits for addition.   Carry bits also
678capture the information flow associated with upshift
679operations, which move information forward one position
680in the file.   In essence, an upshift by one position for
681a bitstream is equivalent to the addition of the stream
682to itself; the bit shifted out in an upshift is in this
683case equivalent to the carry generated by the additon.
684The only other information flow requirement in the
685calculation of parallel bitstreams occurs with the
686bitstream subtractions that are used to calculate span streams.
687In this case, the information flow is based on borrows
688generated, which can be handled in the same way as carries.
690Properly determining, initializing and inserting carry bits
691into a block-by-block implementation of parallel bitstream
692code is a task too tedious for manual implementation.
693We have thus developed compiler technology to automatically
694insert declarations, initializations and carry save/restore
695operations into appropriate locations when translating
696Python operations on unbounded bitstreams into the
697equivalent low-level C code implemented on a block-by-block
698bases.  Our current compiler toolkit is capable of inserting
699carry logic using a variety of strategies, including both
700simulated carry bit processing with SIMD registers, as
701well as carry-flag processing using the processor general
702purpose registers and ALU.   Details are beyond the
703scope of this paper, but are described in the on-line
704source code repository at
707\section{Performance Results}
709In this section, we compare the performance of our \verb:xmlwf:
710implementation using the Parabix2 technology described above with several
711other implementations.
712These include the original \verb:xmlwf:
713distributed as an example application of the \verb:expat: XML
714parser,  implementations based on the widely used Xerces
715open source parser using both SAX and DOM interfaces,
716and an implementation using our prior Parabix 1 technology with
717bit scan operations. 
719Table \ref{XMLDocChars} 
720shows the document characteristics of the XML instances selected for this performance study,
721including both document-oriented and data-oriented XML files.
722The 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),
723a modeling language for geographic information systems as well as an open interchange format for geographic transactions on the Internet.  The po.xml file is an example of purchase order data, while the soap.xml file contains a large SOAP message.
724Markup density is defined as the ratio of the total markup contained within an XML file to the total XML document size.
725This metric is reported for each document.
731File Name               & dewiki.xml            & jawiki.xml            & roads.gml     & po.xml        & soap.xml \\ \hline   
732File Type               & document      & document      & data  & data  & data   \\ \hline     
733File Size (kB)          & 66240                 & 7343                  & 11584         & 76450         & 2717 \\ \hline
734Markup Item Count       & 406792                & 74882                 & 280724        & 4634110       & 18004 \\ \hline               
735Attribute Count         & 18808                 & 3529                  & 160416        & 463397        & 30001\\ \hline
736Avg. Attribute Size     & 8                     & 8                     & 6             & 5             & 9\\ \hline
737Markup Density          & 0.07                  & 0.13                  & 0.57          & 0.76          & 0.87  \\ \hline
741 \caption{XML Document Characteristics} 
742 \label{XMLDocChars} 
745Table \ref{parsers-cpb} shows performance measurements for the
746various \verb:xmlwf: implementations applied to the
747test suite.   Measurements are made on a single core of an
748Intel Core 2 system running a stock 64-bit Ubuntu 10.10 operating system,
749with all applications compiled with llvm-gcc 4.4.5 optimization level 3.
750Measurements are reported in CPU cycles per input byte of
751the XML data files in each case.
752The first row shows the performance of the Xerces C parser
753using the tree-building DOM interface. 
754Note that the performance
755varies considerably depending on markup density.  Note also that
756the DOM tree construction overhead is substantial and unnecessary
757for XML well-formedness checking.  Using the event-based SAX interface
758to Xerces gives much better results as shown in the
759second row.   
760The third row shows the best performance of our byte-at-a-time
761parsers, using the original  \verb:xmlwf: based on expat.
763The remaining rows of Table \ref{parsers-cpb} show performance
764of parallel bitstream implementations.  The first row shows
765the performance of our Parabix 1 implementation using
766bit scan instructions.   While showing a substantial speed-up
767over the byte-at-a-time parsers in every case, note also that
768the performance advantage increases with increasing markup
769density, as expected.   The last two rows show different versions of
770the \verb:xmlwf: implemented based on the Parabix 2 technology
771as discussed in this paper.   They differ in the carry handling
772strategy, with the ``simd'' row referring to carry
773computations performed with simulated calculation of
774propagated and generated carries using SIMD operations, while the
775``adc64'' row refers to an implementation directly employing
776the processor carry flags and add-with-carry instructions on
77764-bit general registers.  In both cases, the overall
778performance is quite impressive, with the increased
779parallelism of parallel bit scans clearly paying off in
780improved performance for dense markup.
787Parser Class & Parser & dewiki.xml  & jawiki.xml    & roads.gml  & po.xml & soap.xml  \\ \hline 
789Byte & Xerces (DOM)    &    37.921   &    40.559   &    72.78   &    105.497   &    125.929  \\ \cline{2-7} 
790at-a & Xerces (SAX)   &     19.829   &    24.883   &    33.435   &    46.891   &    57.119      \\ \cline{2-7}
791Time & expat      &  12.639   &    16.535   &    32.717   &    42.982   &    51.468      \\ \hline 
792Parallel & Parabix1   &    8.313   &    9.335   &     13.345   &    16.136   &      19.047 \\ \cline{2-7}
793Bit& Parabix2 (simd)   &        6.103   &    6.445   &    8.034   &    8.685   &    9.53 \\ \cline{2-7} 
794Stream & Parabix2 (adc64)       &       5.123   &    5.996   &    6.852   &    7.648   &    8.275 \\ \hline
795 \end{tabular}
797 \caption{Parser Performance (Cycles Per Byte)} 
801%gcc (simd\_add)    &   6.174   &       6.405   &       7.948   &       8.565   &       9.172 \\ \hline
802%llvm (simd\_add)   &   6.104   &       6.335   &       8.332   &       8.849   &       9.811 \\ \hline
803%gcc (adc64)        &   9.23   &        9.921   &       10.394   &      10.705   &      11.751 \\ \hline
804%llvm (adc64)       &   5.757   &       6.142   &       6.763   &       7.424   &       7.952 \\ \hline
805%gcc (SAHFLAHF)    &    7.951   &       8.539   &       9.984   &       10.219   &      11.388 \\ \hline
806%llvm(SAHFLAHF)    &    5.61   &        6.02   &        6.901   &       7.597   &       8.183 \\ \hline
813In application to the problem of XML parsing and well-formedness
814checking, the method of parallel parsing with bitstream addition
815is effective and efficient.   Using only bitstream addition
816and bitwise logic, it is possible to handle all of the
817character validation, lexical recognition and parsing problems
818except for the recursive aspects of start and end tag matching.
819Error checking is elegantly supported through the use of error
820streams that eliminate separate if-statements to check for
821errors with each byte.   The techniques are generally very
822efficient particularly when markup density is high.   However, for some
823conditions that occur rarely and/or require complex combinations
824of upshifting and logic, it may be better to define simpler
825error-check streams that require limited postprocessing using
826byte matching techniques.
828The techniques have been implemented and assessed for present-day commodity processors employing current SIMD technology.
829As processor advances see improved instruction sets and increases
830in width of SIMD registers, the relative advantages of the
831techniques over traditional byte-at-a-time sequential
832parsing methods is likely to increase substantially.
833Of particular benefit to this method, instruction set modifications
834that provide for more convenient carry propagation for long
835bitstream arithmetic would be most welcome.
837A significant challenge to the application of these techniques
838is the difficulty of programming.   The method of prototyping
839on unbounded bitstreams has proven to be of significant value
840in our work.   Using the prototyping language as input to
841a bitstream compiler has also proven effective in generating
842high-performance code.   Nevertheless, direct programming
843with bitstreams is still a specialized skill; our future
844research includes developing yet higher level tools to
845generate efficient bitstream implementations from grammars,
846regular expressions and other text processing formalisms.
Note: See TracBrowser for help on using the repository browser.