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

Update start tag parsing figure.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.