source: docs/PACT2011/03-research.tex @ 1099

Last change on this file since 1099 was 1099, checked in by ksherdy, 8 years ago

Re-write many sections.

File size: 10.7 KB
Line 
1\section{Parabix}
2\label{section:parabix}
3%Describe key technology behind Parabix
4%Introduce SIMD;
5%Talk about SSE
6%Highlight which SSE instructions are important
7%TAlk about each pass in the parser; How SSE is used in every phase...
8%Benefits of SSE in each phase.
9
10
11% Extract section 2.2 and merge into 3.   Add a new subsection
12% in section 2 saying a bit about SIMD.   Say a bit about pure SIMD vertical
13% operations and then mention the pack operations that allow
14% us to implement transposition efficiently in parallel. 
15% Also note that the SIMD registers support bitwise logic across
16% their full width and that this is extensively used in our work.
17%
18% Also, it could be good to have a small excerpt of a byte-at-a-time
19% scanning loop for XML, e.g., extracted from Xerces in section 2.1. 
20% Just a few lines showing the while loop - Linda can tell you the file.
21%
22
23% This section focuses on the
24
25
26% With this method, byte-oriented character data is first transposed to eight parallel bit streams, one for each bit position within the character code units (bytes). These bit streams are then loaded into SIMD registers of width $W$ (e.g., 64-bit, 128-bit, 256-bit, etc). This allows $W$ consecutive code units to be represented and processed at once. Bitwise logic and shift operations, bit scans, population counts and other bit-based operations are then used to carry out the work in parallel \cite{CameronLin2009}.
27
28% The results of \cite{CameronHerdyLin2008} showed that Parabix, the predecessor of Parabix2, was dramatically faster than both Expat 2.0.1 and Xerces-C++ 2.8.0.
29% It is our expectation is that Parabix2 will outperform both Expat 2.0.1 and Xerces-C++ 3.1.1 in terms of energy consumption per source XML byte.
30% This expectation is based on the relatively-branchless code composition of Parabix2 and the more-efficient utilization of last-level cache resources.
31% The authors of \cite {bellosa2001, bircher2007, bertran2010} indicate that such factors have a considerable effect on overall energy consumption.
32% Hence, one of the foci in our study is the manner in which straight line SIMD code influences energy usage.
33
34This section provides an overview of the SIMD-based parallel bit stream XML parsers, Parabix1 and Parabix2. A comprehensive study of Parabix2 can be found in the technical report ``Parallel Parsing with Bitstream Addition: An XML Case Study'' \cite{Cameron2010}.
35
36\subsection{Parabix1}
37
38% Our first generation parallel bitstream XML parser---Parabix1---uses employs a less conventional approach of SIMD technology to represent text in parallel bitstreams. Bits of each stream are in one-to-one-correspondence with the bytes of a character stream. A transposition step first transforms sequential byte stream data into eight basis bitstreams for the bits of each byte.
39
40Parabix1 processes source XML in a functionally equivalent manner as that of many traditional recursive descent XML parsers. That is, Parabix1 moves sequentially through the source document, maintaining a single cursor position throughout the parsing process, and parsers recursively, depth first. Where Parabix1 differs from the traditional parser is that it scans for key markup characters using a series of basis bit streams.
41A bit stream is simply a sequence of $0$s and $1$s, where there is one such bit in the bit stream for each character in a source data stream. A basis bit stream is a bit stream that consists of only transposed textual XML data.
42In other words, a source character consisting of $M$ bits can be represented with $M$ bit streams and
43by utilizing $M$ SIMD registers of width $W$, it is possible to scan through $W$ characters in parallel.
44The register width $W$ varies between 64-bit for MMX, 128-bit for SSE, and 256-bit for AVX.
45Figure \ref{fig:BitstreamsExample} presents an example of the basis bit stream representation of 8-bit ASCII characters. $B_0 \ldots B_7$ are the individual bit streams. The $0$ bits in the bit streams are represented by periods to emphasize the $1$ bits.
46
47\begin{figure}[h]
48\begin{center}
49\begin{tabular}{cr}\\
50source data & \verb`<t1>abc</t1><tag2/>`\\
51$B_0$ & \verb`..1.1.1.1.1...11.1.`\\
52$B_1$ & \verb`...1.11.1..1...1111`\\
53$B_2$ & \verb`11.1...111.111.1.11`\\
54$B_3$ & \verb`1..1...11..11....11`\\
55$B_4$ & \verb`1111...1.11111..1.1`\\
56$B_5$ & \verb`1111111111111111111`\\
57$B_6$ & \verb`.1..111..1...111...`\\
58$B_7$ & \verb`...................`\\
59\end{tabular}
60\end{center}
61\caption{Example 8-bit ASCII Character Basis Bit Streams}
62\label{fig:BitstreamsExample}
63\end{figure}
64
65To transform byte-oriented character data to parallel bit stream representation, source data is first loaded into SIMD registered in sequential order. It is then converted to the transposed basis bit stream representation through a series of packs, shifts, and logical bitwise operations. Using the SIMD capabilities of current commodity processors, the transposition of source data to basis bit stream format incurs an amortized cost of approximately 1 cycle per byte \cite{CameronHerdyLin2008}.
66
67Throughout the XML parsing process we must identify significant XML characters. For example, the next opening angle bracket character `<'. For this purpose, we combine the basis bit streams using bitwise logic and compute character-class bit streams. Character-class streams mark the positions of characters as a single $1$-bit if present, $0$ otherwise. Each bit position in the computed bit stream is in one-to-one correspondence to the source data byte positions. For example, the $j$-th character is an open angle bracket `<' if and only if the $j$-th bit of $B_2, B_3, B_4, B_5 =$ 1 and the $j$-th bit of $B_0, B_1, B_6, B_7 =$ 0. Once generated, single cycle built-in {\em bit scan} operations are used to locate the positions significant XML character throughout parsing.
68
69A common operation in XML parsing is XML start tag validation. Starts tags begin with `<' and end with either ``/>'' or ``>'' (depending whether the element tag is an empty element tag or not, respectively). Figure \ref{fig:Parabix1StarttagExample} demonstrates the concept of start tag validation as performed in Parabix1 using character-class streams together with the processor built-in bit scan operation. The first bit stream $M_0$ is created and the parser begins scanning the source data for an open angle bracket `<', starting at position 1. Since the source data begins with `<', $M_0$ is assigned a cursor position of 1. The $advance$ operation then then shifts the $M_0$'s cursor position by 1, resulting in the creation of a new bit stream, $M_1$, with the cursor position at 2. The following $bitscan$ operation takes the cursor position from $M_1$ and sequentially scans every position until it locates either an `>'. It finds a `>' at position 4 and returns that as the new cursor position for $M_2$. Calculating $M_3$ advances the cursor again, and the $bitscan$ used to create $M_4$ locates the new opening angle bracket. This process continues in sequence until until all start tags are validated. Unlike traditional parsers, these sequential operations are accelerated significantly since the bit scan operation can skip up to $w$ positions, where $w$ is the processor word width in bits. This approach has recently been applied to Unicode transcoding and XML parsing to good effect, with research prototypes showing substantial speed-ups over even the best of byte-at-a-time alternatives \cite{CameronHerdyLin2008, Herdy2008, Cameron2009}.
70
71\begin{figure}[h]
72\begin{center}
73\begin{tabular}{lr}\\
74source data                     & \verb`<t1>abc</t1><tag2/>`\\
75$M_0 = 1$                       & \verb`1..................`\\
76$M_1 = advance(M_0)$            & \verb`.1.................`\\
77$M_2 = bitscan('>')$            & \verb`...1...............`\\
78$M_3 = advance(M_2)$            & \verb`....1..............`\\
79$M_4 = bitscan('<')$            & \verb`.......1...........`\\
80$M_5 = advance(M_4)$            & \verb`........1..........`\\
81$M_6 = advance(M_5)$            & \verb`.........1.........`\\
82$M_7 = bitscan('<')$            & \verb`............1......`\\
83$M_{8} = advance(M_7)$  & \verb`.............1.....`\\
84$M_{9} = bitscan('/')$  & \verb`.................1.`\\
85$M_{10} = advance(M_{9})$       & \verb`..................1`\\
86\end{tabular}
87\end{center}
88\caption{Parabix1 Start Tag Validation (Conceptual)}
89\label{fig:Parabix1StarttagExample}
90\end{figure}
91
92\subsection{Parabix2}
93
94In Parabix2, the sequential single-cursor parsing approach using bit scan instructions is replaced by a parallel parsing approach, using multiple cursors when possible, and bit stream addition operations to advance cursor positions.
95Unlike the single-cursor approach of Parabix1 (and conceptually of all sequential XML parsers),
96Parabix2 processes multiple cursors in parallel. For example, using the source data from
97Figure \ref{fig:Parabix1StarttagExample}, Figure \ref{fig:Parabix2StarttagExample} shows how Parabix2 identifies and advances each of the start tag bit streams. Unlike Parabix1, Parabix2 begins scanning by creating two character-class bit streams, $N$, denoting the position of every alpha numeric character within the basis stream, and $M_0$, marking the position of every potential start tag in the bit stream. $M_0$ is advanced to create $M_1$, which is fed into the first $scanto$ operation along with $N$.  To handle variable length tag names, the $scanto$ operation effectively locates the cursor positions of the end tags in parallel by adding $M_1$ to $N$, and uses the bitwise AND operation of the negation of $N$ to find only the true end tags of $M_1$. Because an end tag may end on an `/' or '>', $scanto$ is called again to advance any cursor from `/' to `>'. For additional details, refer to the technical report \cite{Cameron2010}.
98
99
100\begin{figure}[h]
101\begin{center}
102\begin{tabular}{lr}\\
103source data                     & \verb`<t1>abc</t1><tag2/>`\\
104$N = $ Tag Names                & \verb`.11......11..1111..`\\
105$M_0 = \texttt{[<]}$            & \verb`1...........1......`\\
106$M_1 = advance(M_0)$            & \verb`.1...........1.....`\\
107$M_2 = scanto(M_1, N)$          & \verb`...1.............1.`\\
108$M_3 = scanto(M_2, N)$          & \verb`...1..............1`
109\end{tabular}
110\end{center}
111\caption{Parabix2 Start Tag Validation (Conceptual)}
112\label{fig:Parabix2StarttagExample}
113\end{figure}
114
115In general, the set of bit positions in a bit stream may be considered to be the current parsing
116positions of multiple parses taking place in parallel throughout the source data stream. Although it is not explicitly shown in these prior examples,
117error bit streams can be used to identify any well-formedness errors found during the parsing process. Error positions are gathered and
118processed in as a final post processing step. A further aspect of the parallel cursor method with bit stream addition is that the conditional branch statements used to identify
119syntax error at each each parsing position are eliminated. Hence, Parabix2 offers additional parallelism over Parabix1 in the form of multiple cursor
120parsing as well as further reducing branch misprediction penalties.
121
122
Note: See TracBrowser for help on using the repository browser.