Changeset 884


Ignore:
Timestamp:
Feb 4, 2011, 11:21:43 AM (8 years ago)
Author:
cameron
Message:

Update start tag parsing figure.

Location:
docs/EuroPar2011
Files:
4 edited

Legend:

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

    r879 r884  
    143143        c4 = c3 &~ e2
    144144        e = e0 | e1 | e2
    145         return bitutil.latex_streams([('source data', u8data),
     145        return bitutil.latex_streams([('source data $\\vartriangleright$', u8data),
    146146                              ('$M_0$', bitutil.bitstream2string(c0, lgth, zero_ch)),
    147147                              ('$M_1 = n(M_0)$', bitutil.bitstream2string(c1, lgth, zero_ch)),
     
    268268        callouts.error = ParseError
    269269
    270         return bitutil.latex_streams([('source data', u8data),
    271                               ('$N = $name chars', bitutil.bitstream2string(lex.NameScan, lgth, zero_ch)),
    272                               ('$W = $white space', bitutil.bitstream2string(lex.WS, lgth, zero_ch)),
     270        return bitutil.latex_streams([('source data $\\vartriangleright$', u8data),
     271                              ('$N = $ name chars', bitutil.bitstream2string(lex.NameScan, lgth, zero_ch)),
     272                              ('$W = $ white space', bitutil.bitstream2string(lex.WS, lgth, zero_ch)),
    273273                              ('$Q = \\neg$\\verb:[">]:', bitutil.bitstream2string(DQuoteScan, lgth, zero_ch)),
    274274                              ('$M_0$', bitutil.bitstream2string(m0, lgth, zero_ch)),
    275275                              ('$M_1 = n(M_0)$', bitutil.bitstream2string(ElemNamePositions, lgth, zero_ch)),
    276                               ('$M_2 = s(M_1, N)$', bitutil.bitstream2string(ElemNameFollows, lgth, zero_ch)),
    277                               ('$M_3 = s(M_2, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart1, lgth, zero_ch)),
    278                               ('$M_4 = s(M_3, N)$', bitutil.bitstream2string(AttNameFollow1, lgth, zero_ch)),
    279                               ('$M_5 = s(M_4, W) \\wedge$\\verb:[=]:', bitutil.bitstream2string(EqExpected1, lgth, zero_ch)),
    280                               ('$M_6 = n(M_5)$', bitutil.bitstream2string(bitutil.Advance(EqExpected1), lgth, zero_ch)),
    281                               ('$M_7 = s(M_6, W) \\wedge$\\verb:["]:', bitutil.bitstream2string(AttValPos1, lgth, zero_ch)),
    282                               ('$M_8 = n(M_7)$', bitutil.bitstream2string(bitutil.Advance(DQuoteAttVal1), lgth, zero_ch)),
    283                               ('$M_9 = s(M_8, Q) \\wedge$\\verb:["]:', bitutil.bitstream2string(DQuoteAttEnd1, lgth, zero_ch)),
    284                               ('$M_{10} = n(M_9)$', bitutil.bitstream2string(AttValFollow1, lgth, zero_ch)),
    285                               ('$M_{11} = s(M_{10}, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart2, lgth, zero_ch)),
    286                               ('$M_{12} = s(M_{11}, N)$', bitutil.bitstream2string(AttNameFollow2, lgth, zero_ch)),
    287                               ('$M_{13} = s(M_{12}, W) \\wedge$\\verb:[=]:', bitutil.bitstream2string(EqExpected2, lgth, zero_ch)),
    288                               ('$M_{14} = n(M_{13})$', bitutil.bitstream2string(bitutil.Advance(EqExpected2), lgth, zero_ch)),
    289                               ('$M_{15} = s(M_{14}, W) \\wedge$\\verb:["]:', bitutil.bitstream2string(AttValPos2, lgth, zero_ch)),
    290                               ('$M_{16} = n(M_{15})$', bitutil.bitstream2string(bitutil.Advance(DQuoteAttVal2), lgth, zero_ch)),
    291                               ('$M_{17} = s(M_{16}, Q) \\wedge$\\verb:["]:', bitutil.bitstream2string(DQuoteAttEnd2, lgth, zero_ch)),
    292                               ('$M_{18} = n(M_{17})$', bitutil.bitstream2string(AttValFollow2, lgth, zero_ch)),
    293                               ('$M_{19} = s(M_{18}, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart3, lgth, zero_ch))])
    294 
    295 
    296 t1 = r"""-<d>---<elem1 a="17" b="33">---<elem1 a= "137" b ="xxx">----<c12 alpha="">---"""
     276                              ('$M_{0,7} = s(M_1, N)$', bitutil.bitstream2string(ElemNameFollows, lgth, zero_ch)),
     277                              ('$M_{0,8} = s(M_{0,7}, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart1, lgth, zero_ch)),
     278                              ('$M_{1,1} = s(M_{0,8}$', bitutil.bitstream2string(AttNameFollow1, lgth, zero_ch)),
     279                              ('$M_{1,2} = s(M_{1,1}, W) \\wedge$\\verb:[=]:', bitutil.bitstream2string(EqExpected1, lgth, zero_ch)),
     280                              ('$M_{1,3} = n(M_{1,2})$', bitutil.bitstream2string(bitutil.Advance(EqExpected1), lgth, zero_ch)),
     281                              ('$M_{1,4} = s({1,3}, W) \\wedge$\\verb:["]:', bitutil.bitstream2string(AttValPos1, lgth, zero_ch)),
     282                              ('$M_{1,5} = n(M_{1,4})$', bitutil.bitstream2string(bitutil.Advance(DQuoteAttVal1), lgth, zero_ch)),
     283                              ('$M_{1,6} = s(M_{1,5}, Q) \\wedge$\\verb:["]:', bitutil.bitstream2string(DQuoteAttEnd1, lgth, zero_ch)),
     284                              ('$M_{1,7} = n(M_{1,6})$', bitutil.bitstream2string(AttValFollow1, lgth, zero_ch)),
     285                              ('$M_{1,8} = s(M_{1,7}, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart2, lgth, zero_ch)),
     286                              ('$M_{2,1} = s(M_{1,8}, N)$', bitutil.bitstream2string(AttNameFollow2, lgth, zero_ch)),
     287                              ('$M_{2,2} = s(M_{2,1}, W) \\wedge$\\verb:[=]:', bitutil.bitstream2string(EqExpected2, lgth, zero_ch)),
     288                              ('$M_{2,3} = n(M_{2,2})$', bitutil.bitstream2string(bitutil.Advance(EqExpected2), lgth, zero_ch)),
     289                              ('$M_{2,4} = s(M_{2,3}, W) \\wedge$\\verb:["]:', bitutil.bitstream2string(AttValPos2, lgth, zero_ch)),
     290                              ('$M_{2,5} = n(M_{2,4})$', bitutil.bitstream2string(bitutil.Advance(DQuoteAttVal2), lgth, zero_ch)),
     291                              ('$M_{2,6} = s(M_{2,5}, Q) \\wedge$\\verb:["]:', bitutil.bitstream2string(DQuoteAttEnd2, lgth, zero_ch)),
     292                              ('$M_{2,7} = n(M_{2,6})$', bitutil.bitstream2string(AttValFollow2, lgth, zero_ch)),
     293                              ('$M_{2,8} = s(M_{2,7}, W) \\wedge \\neg$\\verb:[>]:', bitutil.bitstream2string(AttNameStart3, lgth, zero_ch))])
     294
     295
     296t1 = r"""--<e a= "137">---<el2 a="17" a2="3379">---<x>--"""
    297297
    298298
  • docs/EuroPar2011/europar-cameron.aux

    r879 r884  
    77\@writefile{toc}{\contentsline {author}{Robert D. Cameron \unskip {} \and Ehsan Amiri \and Kenneth S. Herdy \and Dan Lin \and Thomas C. Shermer \and Fred P. Popowich}{1}}
    88\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
    9 \citation{PPoPP08,CameronHerdyLin2008,Cameron2009}
     9\citation{Cameron2009,PPoPP08,CameronHerdyLin2008}
    1010\citation{CameronHerdyLin2008}
    1111\citation{CameronHerdyLin2008}
     
    1414\citation{DaiNiZhu2010}
    1515\citation{ZhangPanChiu09}
    16 \citation{PPoPP08,Cameron2009}
     16\citation{Cameron2009,PPoPP08}
    1717\@writefile{toc}{\contentsline {section}{\numberline {2}The Parallel Bitstream Method}{3}}
    1818\newlabel{sec:parabit}{{2}{3}}
     19\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Fundamentals}{3}}
    1920\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Basis and Character-Class Bitstreams}}{3}}
    2021\newlabel{fig:inputstreams}{{1}{3}}
    21 \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Fundamentals}{3}}
    2222\citation{CameronHerdyLin2008}
    23 \citation{HilewitzLee2006,CameronLin2009}
     23\citation{CameronLin2009,HilewitzLee2006}
    2424\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}A Parallel Scanning Primitive}{4}}
    2525\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Bitstream addition}}{5}}
     
    4646\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Python Prototyping}{10}}
    4747\@writefile{toc}{\contentsline {section}{\numberline {4}XML Well-Formedness}{10}}
     48\citation{DaiNiZhu2010}
    4849\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Error and Error-Check Bitstreams}{11}}
    49 \@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces XML Error Bitstreams}}{11}}
    50 \newlabel{tab:errstreams}{{1}{11}}
    51 \citation{DaiNiZhu2010}
    52 \@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces XML Error-Check Bitstreams}}{12}}
    53 \newlabel{tab:checkstreams}{{2}{12}}
    5450\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Tag Matching}{12}}
    55 \@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Document Structure}{13}}
    56 \@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Summary}{13}}
    57 \@writefile{toc}{\contentsline {section}{\numberline {5}Compilation to Block-Based Processing}{13}}
    58 \newlabel{sec:compile}{{5}{13}}
     51\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Document Structure}{12}}
     52\@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Summary}{12}}
     53\@writefile{toc}{\contentsline {section}{\numberline {5}Compilation to Block-Based Processing}{12}}
     54\newlabel{sec:compile}{{5}{12}}
    5955\citation{GML04}
    60 \@writefile{toc}{\contentsline {section}{\numberline {6}Performance Results}{14}}
    61 \@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces XML Document Characteristics}}{15}}
    62 \newlabel{XMLDocChars}{{3}{15}}
    63 \@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces Parser Performance (Cycles Per Byte)}}{15}}
    64 \newlabel{parsers-cpb}{{4}{15}}
    65 \@writefile{toc}{\contentsline {section}{\numberline {7}Conclusion}{15}}
     56\@writefile{toc}{\contentsline {section}{\numberline {6}Performance Results}{13}}
     57\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces XML Document Characteristics}}{14}}
     58\newlabel{XMLDocChars}{{1}{14}}
     59\@writefile{toc}{\contentsline {section}{\numberline {7}Conclusion}{14}}
    6660\bibstyle{plain}
    6761\bibdata{xmlperf}
     
    7165\bibcite{PPoPP08}{4}
    7266\bibcite{CameronHerdyLin2008}{5}
     67\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Parser Performance (Cycles Per Byte)}}{15}}
     68\newlabel{parsers-cpb}{{2}{15}}
    7369\bibcite{CameronLin2009}{6}
    7470\bibcite{DaiNiZhu2010}{7}
  • docs/EuroPar2011/europar-cameron.tex

    r883 r884  
    190190\section{The Parallel Bitstream Method}\label{sec:parabit}
    191191
    192 \begin{figure}[h]
     192\begin{figure}[b]
    193193\begin{center}
    194194\begin{tabular}{cr}\\
     
    457457
    458458Figure \ref{fig:stag-ex}
    459 illustrates the parallel parsing of four XML start tags.
     459illustrates the parallel parsing of three XML start tags.
    460460The figure omits determination
    461461of error bitstreams, processing of single-quoted attribute values and handling
     
    484484\begin{center}\footnotesize
    485485
    486 \begin{tabular}{l@{}lr}\\
    487 \multicolumn{2}{l}{source data $\vartriangleright$}  & \verb`-<d>--<ex1 a="17" b="33">---<ex1 a= "137" b ="xxx">----<c12 alpha="">---`\\
    488 $N$   & $= $\mbox{name chars} & \verb`1.1.11.111.1..11..1..11..111.111.1...111..1...111..1111.111.11111....111`\\
    489 $W$   & $= $\mbox{white space} & \verb`..........1......1..............1..1.....1.1...............1............`\\
    490 $Q $   & $ = \neg$\verb:[">]: & \verb`1.1111.111111.11.111.11.1111.1111111.111.1111.111.11111.1111111111..1111`\\
     486\begin{tabular}{lr}\\
     487source data $\vartriangleright$ & \verb`--<e a= "137">---<el2 a="17" a2="3379">---<x>--`\\
     488$N = $ name chars & \verb`11.1.1...111..111.111.1..11..11..1111..111.1.11`\\
     489$W = $ white space & \verb`....1..1.............1......1..................`\\
     490$Q = \neg$\verb:[">]: & \verb`11.11111.111.1111.111111.11.1111.1111.1111.1111`\\
    491491\\
    492 $M_0 $   & $ = $\verb:[<]: & \verb`.1....1.....................1..........................1................`\\
    493 $M_1 $   & $ = n(M_0)$ & \verb`..1....1.....................1..........................1...............`\\
    494 $M_{0,7} $   & $= s(M_1, N)$ & \verb`...1......1.....................1..........................1............`\\
    495 $M_{0,8} $   & $= s(M_{0,7}, W) \wedge \neg$\verb:[>]: & \verb`...........1.....................1..........................1...........`\\
     492$M_0$ & \verb`..1..............1........................1....`\\
     493$M_1 = n(M_0)$ & \verb`...1..............1........................1...`\\
     494$M_{0,7} = s(M_1, N)$ & \verb`....1................1......................1..`\\
     495$M_{0,8} = s(M_{0,7}, W) \wedge \neg$\verb:[>]: & \verb`.....1................1........................`\\
    496496\\
    497 $M_{1,1} $   & $= s(M_{0,8}, N)$ & \verb`............1.....................1..............................1......`\\
    498 $M_{1,2} $   & $= s(M_{1,1}, W) \wedge$\verb:[=]: & \verb`............1.....................1..............................1......`\\
    499 $M_{1,3} $   & $= n(M_{1,2})$ & \verb`.............1.....................1..............................1.....`\\
    500 $M_{1,4} $   & $= s({1,3}, W) \wedge$\verb:["]: & \verb`.............1......................1.............................1.....`\\
    501 $M_{1,5} $   & $= n(M_{1,4})$ & \verb`..............1......................1.............................1....`\\
    502 $M_{1,6} $   & $= s(M_{1,5}, Q) \wedge$\verb:["]: & \verb`................1.......................1..........................1....`\\
    503 $M_{1,7} $   & $= n(M_{1,6})$ & \verb`.................1.......................1..........................1...`\\
    504 $M_{1,8} $   & $= s(M_{1,7}, W) \wedge \neg$\verb:[>]: & \verb`..................1.......................1.............................`\\
     497$M_{1,1} = s(M_{0,8}$ & \verb`......1................1.......................`\\
     498$M_{1,2} = s(M_{1,1}, W) \wedge$\verb:[=]: & \verb`......1................1.......................`\\
     499$M_{1,3} = n(M_{1,2})$ & \verb`.......1................1......................`\\
     500$M_{1,4} = s({1,3}, W) \wedge$\verb:["]: & \verb`........1...............1......................`\\
     501$M_{1,5} = n(M_{1,4})$ & \verb`.........1...............1.....................`\\
     502$M_{1,6} = s(M_{1,5}, Q) \wedge$\verb:["]: & \verb`............1..............1...................`\\
     503$M_{1,7} = n(M_{1,6})$ & \verb`.............1..............1..................`\\
     504$M_{1,8} = s(M_{1,7}, W) \wedge \neg$\verb:[>]: & \verb`.............................1.................`\\
    505505\\
    506 $M_{2,1} $   & $= s(M_{1,8}, N)$ & \verb`...................1.......................1............................`\\
    507 $M_{2,2} $   & $= s(M_{2,1}, W) \wedge$\verb:[=]: & \verb`...................1........................1...........................`\\
    508 $M_{2,3} $   & $= n(M_{2,2})$ & \verb`....................1........................1..........................`\\
    509 $M_{2,4} $   & $= s(M_{2,3}, W) \wedge$\verb:["]: & \verb`....................1........................1..........................`\\
    510 $M_{2,5} $   & $= n(M_{2,4})$ & \verb`.....................1........................1.........................`\\
    511 $M_{2,6} $   & $= s(M_{2,5}, Q) \wedge$\verb:["]: & \verb`.......................1.........................1......................`\\
    512 $M_{2,7} $   & $= n(M_{2,6})$ & \verb`........................1.........................1.....................`\\
    513 $M_{2,8} $   & $= s(M_{2,7}, W) \wedge \neg$\verb:[>]: & \verb`........................................................................`
    514 
     506$M_{2,1} = s(M_{1,8}, N)$ & \verb`...............................1...............`\\
     507$M_{2,2} = s(M_{2,1}, W) \wedge$\verb:[=]: & \verb`...............................1...............`\\
     508$M_{2,3} = n(M_{2,2})$ & \verb`................................1..............`\\
     509$M_{2,4} = s(M_{2,3}, W) \wedge$\verb:["]: & \verb`................................1..............`\\
     510$M_{2,5} = n(M_{2,4})$ & \verb`.................................1.............`\\
     511$M_{2,6} = s(M_{2,5}, Q) \wedge$\verb:["]: & \verb`.....................................1.........`\\
     512$M_{2,7} = n(M_{2,6})$ & \verb`......................................1........`\\
     513$M_{2,8} = s(M_{2,7}, W) \wedge \neg$\verb:[>]: & \verb`...............................................`
    515514\end{tabular}
     515
     516
    516517
    517518\end{center}
     
    530531The first group
    531532$M_0$ through $M_{0,8}$ shows the initiation of parsing for each of the
    532 four tags through the
     533 tags through the
    533534opening angle brackets and  the element names, up to the first
    534535attribute name, if present.  Note that the there are no attribute names
    535 in the first tag shown, so the corresponding marker becomes zeroed
     536in the final tag shown, so the corresponding marker becomes zeroed
    536537out at the closing angle bracket.
    537538Since $M_{0,8}$ is not all $0$s, the parsing continues.
     
    539540The second group of marker transitions
    540541$M_{1,1}$ through $M_{1,8}$ deal with the parallel parsing of the first attribute-value
    541 pair of the three remaining tags.
     542pair of the remaining tags.
    542543After these operations, there are no more attributes
    543 in the final tag, so its corresponding marker becomes zeroed out.
    544 However, $M_{1, 8}$ is not all $0$s, as each of the middle two tags still have an unparsed attribute-value pair.
     544in the first tag, so its corresponding marker becomes zeroed out.
     545However, $M_{1, 8}$ is not all $0$s, as the second tags still has an unparsed attribute-value pair.
    545546Thus, the parsing continues.
    546547
    547548The third group of marker transitions $M_{2,1}$ through $M_{2,8}$ deal with the parsing of
    548 the second attribute-value pair of each of the two remaining tags.  The
     549the second attribute-value pair of this tag.  The
    549550final transition to $M_{2,8}$ shows the zeroing out of all remaining markers
    550551once two iterations of attribute-value processing have taken place.
     
    558559are processed in parallel, using a number of iterations equal to the maximum
    559560number of attribute-value pairs in any one tag in the document.   
    560 However, the cost of iteration is considerably reduced; the iteration for
     561However, in block-by-block processing, the cost of iteration is considerably reduced; the iteration for
    561562each block only requires as many steps as there are attribute-value pairs
    562563overlapping the block.
Note: See TracChangeset for help on using the changeset viewer.