Changeset 884 for docs/EuroPar2011/europar-cameron.tex

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

Update start tag parsing figure.

File:
1 edited

Legend:

Unmodified
 r883 \section{The Parallel Bitstream Method}\label{sec:parabit} \begin{figure}[h] \begin{figure}[b] \begin{center} \begin{tabular}{cr}\\ Figure \ref{fig:stag-ex} illustrates the parallel parsing of four XML start tags. illustrates the parallel parsing of three XML start tags. The figure omits determination of error bitstreams, processing of single-quoted attribute values and handling \begin{center}\footnotesize \begin{tabular}{l@{}lr}\\ \multicolumn{2}{l}{source data $\vartriangleright$}  & \verb-------------\\ $N$   & $=$\mbox{name chars} & \verb1.1.11.111.1..11..1..11..111.111.1...111..1...111..1111.111.11111....111\\ $W$   & $=$\mbox{white space} & \verb..........1......1..............1..1.....1.1...............1............\\ $Q$   & $= \neg$\verb:[">]: & \verb1.1111.111111.11.111.11.1111.1111111.111.1111.111.11111.1111111111..1111\\ \begin{tabular}{lr}\\ source data $\vartriangleright$ & \verb----------\\ $N =$ name chars & \verb11.1.1...111..111.111.1..11..11..1111..111.1.11\\ $W =$ white space & \verb....1..1.............1......1..................\\ $Q = \neg$\verb:[">]: & \verb11.11111.111.1111.111111.11.1111.1111.1111.1111\\ \\ $M_0$   & $=$\verb:[<]: & \verb.1....1.....................1..........................1................\\ $M_1$   & $= n(M_0)$ & \verb..1....1.....................1..........................1...............\\ $M_{0,7}$   & $= s(M_1, N)$ & \verb...1......1.....................1..........................1............\\ $M_{0,8}$   & $= s(M_{0,7}, W) \wedge \neg$\verb:[>]: & \verb...........1.....................1..........................1...........\\ $M_0$ & \verb..1..............1........................1....\\ $M_1 = n(M_0)$ & \verb...1..............1........................1...\\ $M_{0,7} = s(M_1, N)$ & \verb....1................1......................1..\\ $M_{0,8} = s(M_{0,7}, W) \wedge \neg$\verb:[>]: & \verb.....1................1........................\\ \\ $M_{1,1}$   & $= s(M_{0,8}, N)$ & \verb............1.....................1..............................1......\\ $M_{1,2}$   & $= s(M_{1,1}, W) \wedge$\verb:[=]: & \verb............1.....................1..............................1......\\ $M_{1,3}$   & $= n(M_{1,2})$ & \verb.............1.....................1..............................1.....\\ $M_{1,4}$   & $= s({1,3}, W) \wedge$\verb:["]: & \verb.............1......................1.............................1.....\\ $M_{1,5}$   & $= n(M_{1,4})$ & \verb..............1......................1.............................1....\\ $M_{1,6}$   & $= s(M_{1,5}, Q) \wedge$\verb:["]: & \verb................1.......................1..........................1....\\ $M_{1,7}$   & $= n(M_{1,6})$ & \verb.................1.......................1..........................1...\\ $M_{1,8}$   & $= s(M_{1,7}, W) \wedge \neg$\verb:[>]: & \verb..................1.......................1.............................\\ $M_{1,1} = s(M_{0,8}$ & \verb......1................1.......................\\ $M_{1,2} = s(M_{1,1}, W) \wedge$\verb:[=]: & \verb......1................1.......................\\ $M_{1,3} = n(M_{1,2})$ & \verb.......1................1......................\\ $M_{1,4} = s({1,3}, W) \wedge$\verb:["]: & \verb........1...............1......................\\ $M_{1,5} = n(M_{1,4})$ & \verb.........1...............1.....................\\ $M_{1,6} = s(M_{1,5}, Q) \wedge$\verb:["]: & \verb............1..............1...................\\ $M_{1,7} = n(M_{1,6})$ & \verb.............1..............1..................\\ $M_{1,8} = s(M_{1,7}, W) \wedge \neg$\verb:[>]: & \verb.............................1.................\\ \\ $M_{2,1}$   & $= s(M_{1,8}, N)$ & \verb...................1.......................1............................\\ $M_{2,2}$   & $= s(M_{2,1}, W) \wedge$\verb:[=]: & \verb...................1........................1...........................\\ $M_{2,3}$   & $= n(M_{2,2})$ & \verb....................1........................1..........................\\ $M_{2,4}$   & $= s(M_{2,3}, W) \wedge$\verb:["]: & \verb....................1........................1..........................\\ $M_{2,5}$   & $= n(M_{2,4})$ & \verb.....................1........................1.........................\\ $M_{2,6}$   & $= s(M_{2,5}, Q) \wedge$\verb:["]: & \verb.......................1.........................1......................\\ $M_{2,7}$   & $= n(M_{2,6})$ & \verb........................1.........................1.....................\\ $M_{2,8}$   & $= s(M_{2,7}, W) \wedge \neg$\verb:[>]: & \verb........................................................................ $M_{2,1} = s(M_{1,8}, N)$ & \verb...............................1...............\\ $M_{2,2} = s(M_{2,1}, W) \wedge$\verb:[=]: & \verb...............................1...............\\ $M_{2,3} = n(M_{2,2})$ & \verb................................1..............\\ $M_{2,4} = s(M_{2,3}, W) \wedge$\verb:["]: & \verb................................1..............\\ $M_{2,5} = n(M_{2,4})$ & \verb.................................1.............\\ $M_{2,6} = s(M_{2,5}, Q) \wedge$\verb:["]: & \verb.....................................1.........\\ $M_{2,7} = n(M_{2,6})$ & \verb......................................1........\\ $M_{2,8} = s(M_{2,7}, W) \wedge \neg$\verb:[>]: & \verb............................................... \end{tabular} \end{center} The first group $M_0$ through $M_{0,8}$ shows the initiation of parsing for each of the four tags through the tags through the opening angle brackets and  the element names, up to the first attribute name, if present.  Note that the there are no attribute names in the first tag shown, so the corresponding marker becomes zeroed in the final tag shown, so the corresponding marker becomes zeroed out at the closing angle bracket. Since $M_{0,8}$ is not all $0$s, the parsing continues. The second group of marker transitions $M_{1,1}$ through $M_{1,8}$ deal with the parallel parsing of the first attribute-value pair of the three remaining tags. pair of the remaining tags. After these operations, there are no more attributes in the final tag, so its corresponding marker becomes zeroed out. However, $M_{1, 8}$ is not all $0$s, as each of the middle two tags still have an unparsed attribute-value pair. in the first tag, so its corresponding marker becomes zeroed out. However, $M_{1, 8}$ is not all $0$s, as the second tags still has an unparsed attribute-value pair. Thus, the parsing continues. The third group of marker transitions $M_{2,1}$ through $M_{2,8}$ deal with the parsing of the second attribute-value pair of each of the two remaining tags.  The the second attribute-value pair of this tag.  The final transition to $M_{2,8}$ shows the zeroing out of all remaining markers once two iterations of attribute-value processing have taken place. are processed in parallel, using a number of iterations equal to the maximum number of attribute-value pairs in any one tag in the document. However, the cost of iteration is considerably reduced; the iteration for However, in block-by-block processing, the cost of iteration is considerably reduced; the iteration for each block only requires as many steps as there are attribute-value pairs overlapping the block.