Changeset 895


Ignore:
Timestamp:
Feb 5, 2011, 5:05:29 PM (9 years ago)
Author:
cameron
Message:

Trim intro and tighten section 2.

Location:
docs/EuroPar2011
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • docs/EuroPar2011/Demo/bitutil.py

    r879 r895  
    131131                stream >>= 1
    132132        return str
     133
     134def string2bitstream(s):
     135        rslt = 0
     136        for i in s[::-1]:
     137                rslt *= 2
     138                if i == '1': rslt += 1
     139        return rslt
     140
     141
    133142
    134143def print_aligned_streams(stream_list):
  • docs/EuroPar2011/Demo/europar.py

    r884 r895  
    1919        cursor = lex.Digit & ~ bitutil.Advance(lex.Digit)
    2020        cursor2 = cursor + lex.Digit
    21         bitutil.print_aligned_u8_byte_streams([('source data', chardata[::-1]),
     21        bitutil.print_aligned_u8_byte_streams([('source data $\\vartriangleleft$', chardata[::-1]),
    2222                              ('cursor', bitutil.bitstream2stringLE(cursor, lgth, zero_ch)),
    2323                              ('[0-9] stream', bitutil.bitstream2stringLE(lex.Digit, lgth, zero_ch)),
     
    3030        cursor = lex.Digit & ~ bitutil.Advance(lex.Digit)
    3131        cursor2 = cursor + lex.Digit
    32         return bitutil.latex_streams([('source data', chardata[::-1]),
    33                               ('$C_0$', bitutil.bitstream2stringLE(cursor, lgth, zero_ch)),
     32        return bitutil.latex_streams([('source data $\\vartriangleleft$', chardata[::-1]),
     33                              ('$M_0$', bitutil.bitstream2stringLE(cursor, lgth, zero_ch)),
    3434                              ('$D$', bitutil.bitstream2stringLE(lex.Digit, lgth, zero_ch)),
    35                               ('$C_1 = C_0 + D$', bitutil.bitstream2stringLE(cursor2, lgth, zero_ch))])
     35                              ('$M_1 = M_0 + D$', bitutil.bitstream2stringLE(cursor2, lgth, zero_ch))])
    3636
    3737def latex_numeric_scan2(chardata, cursorstr):
     
    4141        (u8, control, lex) = byteclass.classify_bytes(bit)
    4242        (u8x, control2, lex2) = byteclass.classify_bytes(bit2)
    43         cursor = lex2.Digit
     43        cursor = bitutil.string2bitstream(cursorstr)
    4444        temp = (cursor + lex.Digit)
    4545        cursor2 = temp & ~lex.Digit
     
    5353                              ('$B_1$', bitutil.bitstream2stringLE(bit[6], lgth, zero_ch)),
    5454                              ('$B_0$', bitutil.bitstream2stringLE(bit[7], lgth, zero_ch)),
    55                               ('\\verb:[#]:', bitutil.bitstream2stringLE(lex.Hash, lgth, zero_ch)),
    5655                              ('\\verb:[0-9]:', bitutil.bitstream2stringLE(lex.Digit, lgth, zero_ch)),
    5756                              ('$D = $\\verb:[0-9]:', bitutil.bitstream2stringLE(lex.Digit, lgth, zero_ch)),
    58                               ('$M_0 =$\\verb:[#]:', bitutil.bitstream2stringLE(lex.Hash, lgth, zero_ch)),
     57                              ('$M_0 =$', bitutil.bitstream2stringLE(cursor, lgth, zero_ch)),
    5958                              ('$M_0 + D$',  bitutil.bitstream2stringLE(temp, lgth, zero_ch)),
    6059                              ('$M_1 = (M_0 + D) \\wedge \\neg D$', bitutil.bitstream2stringLE(cursor2, lgth, zero_ch))])
     
    6261def europar1():
    6362  return latex_numeric_scan2('--123----13794----1----456---249371----',
    64                              '..1......1........1............1.......')
     63                             '...........1......1....1.....1.........')
    6564
    6665
  • docs/EuroPar2011/europar-cameron.aux

    r894 r895  
    11\relax
    22\citation{Asanovic:EECS-2006-183}
    3 \citation{Scarpazza:2009}
    4 \citation{XMLSSE42}
    5 \@writefile{toc}{\contentsline {title}{Parallel Scanning with Bitstream Addition: An XML Case Study}{1}}
    6 \@writefile{toc}{\authcount {6}}
    7 \@writefile{toc}{\contentsline {author}{Robert D. Cameron \and Ehsan Amiri \and Kenneth S. Herdy \and Dan Lin \and Thomas C. Shermer \and Fred P. Popowich}{1}}
    8 \@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
    9 \citation{Cameron2009,PPoPP08,CameronHerdyLin2008}
    10 \citation{CameronHerdyLin2008}
     3\citation{PPoPP08,CameronHerdyLin2008,Green2009}
    114\citation{CameronHerdyLin2008}
    125\citation{Herdy2008}
     
    147\citation{DaiNiZhu2010}
    158\citation{ZhangPanChiu09}
    16 \citation{Cameron2009,PPoPP08}
     9\@writefile{toc}{\contentsline {title}{Parallel Scanning with Bitstream Addition: An XML Case Study}{1}}
     10\@writefile{toc}{\authcount {6}}
     11\@writefile{toc}{\contentsline {author}{Robert D. Cameron \and Ehsan Amiri \and Kenneth S. Herdy \and Dan Lin \and Thomas C. Shermer \and Fred P. Popowich}{1}}
     12\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
    1713\@writefile{toc}{\contentsline {section}{\numberline {2}The Parallel Bitstream Method}{2}}
    1814\newlabel{sec:parabit}{{2}{2}}
    1915\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Fundamentals}{2}}
     16\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Basis and Character-Class Bitstreams}}{2}}
     17\newlabel{fig:inputstreams}{{1}{2}}
    2018\citation{CameronHerdyLin2008}
    21 \citation{CameronLin2009,HilewitzLee2006}
    22 \@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Basis and Character-Class Bitstreams}}{3}}
    23 \newlabel{fig:inputstreams}{{1}{3}}
    24 \@writefile{toc}{\contentsline {subsection}{\numberline {2.2}A Parallel Scanning Primitive}{4}}
    25 \@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Bitstream addition}}{4}}
     19\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}A Parallel Scanning Primitive}{3}}
     20\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Parallel Scan Using Bitstream Addition and Mask}}{4}}
    2621\newlabel{fig:scan1}{{2}{4}}
    27 \@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Parallel Scan Using Addition and Mask}}{5}}
    28 \newlabel{fig:scan2}{{3}{5}}
    29 \@writefile{toc}{\contentsline {section}{\numberline {3}XML Scanning and Parsing}{5}}
    30 \newlabel{sec:errorstream}{{3}{5}}
    31 \@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces XML Grammar: Decimal Character References and Start Tags}}{5}}
    32 \newlabel{fig:xmlgrmr}{{4}{5}}
    33 \@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Parsing Decimal References}}{6}}
    34 \newlabel{fig:decref}{{5}{6}}
    35 \@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Start Tag Parsing}}{7}}
    36 \newlabel{fig:stag-ex}{{6}{7}}
     22\@writefile{toc}{\contentsline {section}{\numberline {3}XML Scanning and Parsing}{4}}
     23\newlabel{sec:errorstream}{{3}{4}}
     24\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces XML Grammar: Decimal Character References and Start Tags}}{5}}
     25\newlabel{fig:xmlgrmr}{{3}{5}}
     26\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Parsing Decimal References}}{5}}
     27\newlabel{fig:decref}{{4}{5}}
     28\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Start Tag Parsing}}{6}}
     29\newlabel{fig:stag-ex}{{5}{6}}
    3730\citation{TR:XML}
    38 \@writefile{toc}{\contentsline {section}{\numberline {4}XML Well-Formedness}{8}}
     31\@writefile{toc}{\contentsline {section}{\numberline {4}XML Well-Formedness}{7}}
    3932\citation{DaiNiZhu2010}
    40 \@writefile{toc}{\contentsline {section}{\numberline {5}Compilation to Block-Based Processing}{10}}
    41 \newlabel{sec:compile}{{5}{10}}
     33\@writefile{toc}{\contentsline {section}{\numberline {5}Compilation to Block-Based Processing}{9}}
     34\newlabel{sec:compile}{{5}{9}}
    4235\@writefile{toc}{\contentsline {section}{\numberline {6}Performance Results}{10}}
    43 \citation{GML04}
    44 \@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces XML Document Characteristics}}{11}}
    45 \newlabel{XMLDocChars}{{1}{11}}
     36\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces XML Document Characteristics}}{10}}
     37\newlabel{XMLDocChars}{{1}{10}}
     38\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Parser Performance (Cycles Per Byte)}}{11}}
     39\newlabel{parsers-cpb}{{2}{11}}
     40\@writefile{toc}{\contentsline {section}{\numberline {7}Conclusion}{11}}
    4641\bibstyle{plain}
    4742\bibdata{xmlperf}
    48 \@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Parser Performance (Cycles Per Byte)}}{12}}
    49 \newlabel{parsers-cpb}{{2}{12}}
    50 \@writefile{toc}{\contentsline {section}{\numberline {7}Conclusion}{12}}
    5143\bibcite{Asanovic:EECS-2006-183}{1}
    5244\bibcite{TR:XML}{2}
    53 \bibcite{Cameron2009}{3}
    54 \bibcite{PPoPP08}{4}
    55 \bibcite{CameronHerdyLin2008}{5}
    56 \bibcite{CameronLin2009}{6}
    57 \bibcite{DaiNiZhu2010}{7}
    58 \bibcite{Herdy2008}{8}
    59 \bibcite{HilewitzLee2006}{9}
    60 \bibcite{GML04}{10}
    61 \bibcite{XMLSSE42}{11}
    62 \bibcite{Leventhal2009}{12}
    63 \bibcite{Scarpazza:2009}{13}
    64 \bibcite{ZhangPanChiu09}{14}
     45\bibcite{PPoPP08}{3}
     46\bibcite{CameronHerdyLin2008}{4}
     47\bibcite{DaiNiZhu2010}{5}
     48\bibcite{Green2009}{6}
     49\bibcite{Herdy2008}{7}
     50\bibcite{GML04}{8}
     51\bibcite{Leventhal2009}{9}
     52\bibcite{ZhangPanChiu09}{10}
  • docs/EuroPar2011/europar-cameron.bbl

    r879 r895  
    1414\newblock W3C Recommendation, 2008.
    1515
    16 \bibitem{Cameron2009}
    17 Rob Cameron, Ken Herdy, and Ehsan Amiri.
    18 \newblock Parallel bit stream technology as a foundation for {XML} parsing
    19   performance.
    20 \newblock In {\em International Symposium on Processing {XML} Efficiently:
    21   Overcoming Limits on Space, Time, or Bandwidth}, August 2009.
    22 
    2316\bibitem{PPoPP08}
    2417Robert~D. Cameron.
     
    3427  York, NY, USA, 2008. ACM.
    3528
    36 \bibitem{CameronLin2009}
    37 Robert~D. Cameron and Dan Lin.
    38 \newblock Architectural support for swar text processing with parallel bit
    39   streams: the inductive doubling principle.
    40 \newblock In {\em {ASPLOS} '09: Proceeding of the 14th international conference
    41   on Architectural support for programming languages and operating systems},
    42   pages 337--348, New York, NY, USA, 2009. ACM.
    43 
    4429\bibitem{DaiNiZhu2010}
    4530Zefu Dai, Nick Ni, and Jianwen Zhu.
     
    4934  New York, NY, USA, 2010. ACM.
    5035
     36\bibitem{Green2009}
     37J.R. Green, H.~Mahmoud, and M.~Dumontier.
     38\newblock Modeling tryptic digestion on the {Cell BE} processor.
     39\newblock In {\em Proceedings of the Canadian Conference on Electrical and
     40  Computer Engineering (CCECE '09)}, May 2009.
     41
    5142\bibitem{Herdy2008}
    5243Kenneth~S. Herdy, David~S. Burggraf, and Robert~D. Cameron.
     
    5445  presentation of geographic data in web-based mapping systems.
    5546\newblock In {\em Proceedings of {SVG} Open 2008}, August 2008.
    56 
    57 \bibitem{HilewitzLee2006}
    58 Yedidya Hilewitz and Ruby~B. Lee.
    59 \newblock Fast bit compression and expansion with parallel extract and parallel
    60   deposit instructions.
    61 \newblock In {\em {ASAP} '06: Proceedings of the IEEE 17th International
    62   Conference on Application-specific Systems, Architectures and Processors},
    63   pages 65--72, Washington, DC, USA, 2006. IEEE Computer Society.
    6447
    6548\bibitem{GML04}
     
    6952\newblock John Wiley \& Sons, Inc., 2004.
    7053
    71 \bibitem{XMLSSE42}
    72 Zhai Lei.
    73 \newblock {XML} parsing accelerator with intel® streaming {SIMD} extensions 4
    74   (intel® {SSE4}).
    75 \newblock
    76   {http://software.intel.com/en-us/articles/xml-parsing-accelerator-with-intel%
    77 -streaming-simd-extensions-4-intel-sse4/}, 2008.
    78 
    7954\bibitem{Leventhal2009}
    8055Michael Leventhal and Eric Lemoine.
     
    8257\newblock In {\em International Symposium on Processing {XML} Efficiently:
    8358  Overcoming Limits on Space, Time, or Bandwidth}, August 2009.
    84 
    85 \bibitem{Scarpazza:2009}
    86 Daniele~Paolo Scarpazza and Gregory~F. Russell.
    87 \newblock High-performance regular expression scanning on the cell/b.e.
    88   processor.
    89 \newblock In {\em Proceedings of the 23rd international conference on
    90   Supercomputing}, ICS '09, pages 14--25, New York, NY, USA, 2009. ACM.
    9159
    9260\bibitem{ZhangPanChiu09}
  • docs/EuroPar2011/europar-cameron.tex

    r894 r895  
    9393\section{Introduction}
    9494
    95 
    96 
    97 Traditional byte-at-a-time parsing technology is increasingly
    98 mismatched to the capabilities of modern processors.   Current
    99 commodity processors generally possess 64-bit general purpose registers
    100 as well as 128-bit SIMD registers, with 256-bit registers now
    101 appearing.   General purpose processing on graphics processors
    102 can make available 512-bit or wider registers.   Parsing models
    103 based on the traditional loading and processing of 8 bits at a time
    104 would seem to be greatly underutilizing processor resources.
    105 
    106 Unfortunately, parsing is hard to parallelize.   Indeed, in their seminal
    107 report outlining the landscape of parallel computing research,
    108 researchers from Berkeley identified the finite state machine
    109 methods underlying parsing and lexical processing as the hardest
    110 of the "13 dwarves" to parallelize, concluding at one point that
    111 "nothing helps." \cite{Asanovic:EECS-2006-183}   SIMD methods, in particular, would seem to
    112 be ill-suited to parsing, because textual data streams are seldom organized in
    113 convenient 16-byte blocks, tending to consist instead of
    114 variable-length items in generally unpredictable patterns.
    115 Nevertheless, there have been some notable works such as that of
    116 Scarpazza in applying the multicore and SIMD capabilities of the
    117 Cell/BE processor to regular expression matching \cite{Scarpazza:2009}.
    118 Intel has also signalled the importance of accelerated string
    119 processing to its customers through the introduction of new string processing
    120 instructions in the SSE 4.2 instruction set extension, demonstrating
    121 how those features may be used to advantage in activities such as
    122 XML parsing \cite{XMLSSE42}. 
    123 
    124 Our research has been exploring a promising alternative approach, however, based on
    125 the concept of {\em parallel bitstreams} \cite{Cameron2009,PPoPP08,CameronHerdyLin2008}.   
    126 In this approach, byte streams
    127 are first sliced into eight basis bitstreams, one for each
    128 bit position within the byte.  Bit stream $i$ thus comprises
    129 the $i$th bit of each byte.   Using 128-bit SIMD registers, then,
    130 bitwise logic operations on these basis bitstreams allows
    131 byte classification operations to be carried out in parallel
    132 for 128 bytes at a time.  For example, consider a character class
    133 bitstream \verb:[<]: using a 1 bit to mark the position of
    134 opening angle brackets in a byte stream.  This stream may
    135 computed as logical combination of the basis bitstreams using
    136 only seven bitwise logical operations per 128 bytes.
    137 
    138 Based on this approach, our prior work has shown how parallel
    139 bitstreams may be used to accelerate XML parsing by further
    140 taking advantage of processor {\em bit scan} instructions, commonly
    141 found within commodity processors \cite{CameronHerdyLin2008}.
    142 On current Intel or AMD processors, for example, these instructions
    143 allow one to determine the position of the first 1 bit in a group of 64
    144 in a single instruction.   Using these techniques, our Parabix 1
    145 parser demonstrated offered considerable accelaration of XML
    146 parsing in statistics gathering \cite{CameronHerdyLin2008} as well
    147 as GML to SVG conversion \cite{Herdy2008}.
     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.
     109
     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}. 
    148116Other efforts to accelerate XML parsing include the use of custom
    149117XML chips \cite{Leventhal2009}, FPGAs \cite{DaiNiZhu2010}, and
     
    152120In this paper, we further increase the parallelism in our methods
    153121by introducing a new parallel scanning primitive using bitstream
    154 addition.   In essence, multiple 1 bits in a marker stream
    155 identify current scanning positions for multiple instances
    156 of a particular syntactic context within a byte stream.
    157 These multiple marker positions may each be independently
    158 advanced in parallel using addition and masking. 
    159 The net result is a new scanning primitive that
    160 allows multiple instances
    161 of syntactic elements to be parsed simultaneously.   For example,
    162 in dense XML markup, one might find several instances of particular
    163 types of markup tags within a given 64-byte block of text; parallel
    164 addition on 64-bit words allows all such instances to be processed at once.
     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.
     128
     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.
     140
    165141
    166142% The remainder of this paper is organized as follows.
     
    212188
    213189A 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.
    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{Cameron2009,PPoPP08}.
     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.
    215191
    216192The starting point for bitstream methods are \emph{basis} bitstreams
     
    242218transposition and less than 1 CPU cycle per byte for all the character
    243219classes needed for XML parsing \cite{CameronHerdyLin2008}.
    244 Improved instruction sets using parallel extract operations or
    245 inductive doubling techniques may further reduce this overhead significantly \cite{CameronLin2009,HilewitzLee2006}.
     220%Improved instruction sets using parallel extract operations or
     221%inductive doubling techniques may further reduce this overhead significantly \cite{CameronLin2009,HilewitzLee2006}.
    246222
    247223Beyond the bitwise logic needed for character class determination,
     
    266242Figure \ref{fig:scan1} illustrates the basic concept
    267243underlying parallel parsing with bitstream addition.
    268 As with the previous figures, all streams are shown in little-endian
     244All streams are shown in little-endian
    269245representation, with streams reading from right-to-left.
    270 The first row shows a source data stream that includes three
    271 spans of digits, $13840$, $1139845$, and $127$, with other nondigit characters shown
     246The first row shows a source data stream that includes several
     247spans of digits, together with other nondigit characters shown
    272248as hyphens.  The second row specifies the parsing problem
    273 using a marker bitstream $M_0$ to mark three initial
    274 marker positions at the start of each span of digits.
     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.
    275253The parallel parsing task is to move each
    276 of the three markers forward through the corresponding spans of
     254of the four markers forward through the corresponding spans of
    277255digits to the immediately following positions.
    278256
    279257\begin{figure}[tbh]
    280258\begin{center}
    281 \begin{tabular}{l@{}lr}\\
    282 \multicolumn{2}{l}{source data $\vartriangleleft$}
    283                           & \verb`--721----5489311-----04831------`\\
    284 $M_0$ &                   & \verb`....1..........1.........1......`\\
    285 $D$   & $= \verb`[0..9]`$ & \verb`..111....1111111.....11111......`\\
    286 $M_1$ & $ = M_0 + D$      & \verb`.1......1...........1...........`
     259\begin{tabular}{cr}\\
     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..............`
    287265\end{tabular}
     266
     267
    288268\end{center}
    289 \caption{Bitstream addition}
     269\caption{Parallel Scan Using Bitstream Addition and Mask}
    290270\label{fig:scan1}
    291271\end{figure}
     
    298278class bitstreams.  As a marker 1 bit is combined using binary addition to
    299279a span of 1s, each 1 in the span becomes 0, generating
    300 a carry to add to the next position to the left.  
    301 For each span, the process terminates at the left end
     280a carry to add to the next position to the left.
     281For each such span, the process terminates at the left end
    302282of the span, generating a 1 bit in the immediately
    303 following position.   In this way, binary addition produces the marker bitstream
    304 $M_1$, with each of the three markers
    305 moved independently through their respective spans of digits to the position at the end.
    306 
    307 However, the simple addition technique shown in Figure \ref{fig:scan1}
    308 does not account for digits in the source stream that do
    309 not play a role in a particular scanning operation.
    310 Figure \ref{fig:scan2} shows an example and how this
    311 may be resolved.   The source data stream is again shown in row 1,
    312 and the marker bitstream defining the initial marker positions
    313 for the the parallel parsing tasks shown in row 2.   
    314 Row 3 again contains the character class bitstream for digits $D$.
    315 Row 4 shows the result of bitstream addition, in which
    316 marker bits are advanced, but additional bits not
    317 involved in the scan operation are included in the result.
    318 However, these are easily removed in row 5, by masking
     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
    319289off any bits from the digit bitstream; these can never
    320290be marker positions resulting from a scan.
     
    323293(conflict-free) set of initial markers specified in $M_0$.
    324294
    325 \begin{figure}[tbh]
    326 \begin{center}
    327 \begin{tabular}{l@{}lr}\\
    328 \multicolumn{2}{l}{source data $\vartriangleleft$}     
    329                                                         & \verb`--134--31--59127---3--3474--`\\
    330 $M_0$ &                                                 & \verb`....1.........1..........1..`\\
    331 $D$   & $= \verb`[0..9]`$ & \verb`..111..11..11111...1..1111..`\\
    332 $M_1$ & $= M_0 + D$       & \verb`.1.....11.1....1...1.1......`\\
    333 $M_2$ & $= (M_0 + D) \wedge \neg D$ & \verb`.1........1..........1......`
    334 \end{tabular}
    335 \end{center}
    336 \caption{Parallel Scan Using Addition and Mask}
    337 \label{fig:scan2}
    338 \end{figure}
    339295
    340296% The addition and masking technique allows matching of
     
    765721including both document-oriented and data-oriented XML files.
    766722The 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),
    767 a 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.
     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.
    768724Markup density is defined as the ratio of the total markup contained within an XML file to the total XML document size.
    769725This metric is reported for each document.
  • docs/EuroPar2011/xmlperf.bib

    r879 r895  
    258258month=aug}
    259259
     260@inproceedings{Green2009,
     261title={Modeling Tryptic Digestion on the {Cell BE} Processor},
     262author = {Green, J.R. and  Mahmoud, H. and  Dumontier, M.},
     263booktitle = {Proceedings of the Canadian Conference on Electrical and Computer Engineering (CCECE '09)},
     264year = {2009},
     265location={St. John's, Newfoundland},
     266month=may}
     267
Note: See TracChangeset for help on using the changeset viewer.