source: docs/Working/icXML/icxml-main.tex @ 3633

Last change on this file since 3633 was 2872, checked in by nmedfort, 7 years ago

edits

File size: 7.2 KB
Line 
1% TEMPLATE for Usenix papers, specifically to meet requirements of
2%  USENIX '13
3%
4% Cleaned up and modernized by Emin Gun Sirer on Jan 7 2013 based on
5% previous versions developed by Matthew Ward, David Beazley,
6% De Clarke, and Fred Douglis.
7\documentclass[letterpaper,twocolumn,10pt]{article}
8\usepackage{usenix,epsfig}
9\usepackage{subfigure}
10\usepackage{amsmath}
11\usepackage{graphicx}
12\usepackage{CJKutf8}
13\usepackage{morefloats}
14\usepackage{amssymb}
15\begin{document}
16
17\def \xerces {Xerces-C++ 3.1.1}
18\def \icXML {icXML}
19\def \icXMLp {icXML-p}
20\def \PS {Parabix Subsystem}
21\def \MP {Markup Processor}
22\def \wrt {with respect to}
23\def \bitstream{bitstream}
24
25\title{\icXML{}:  Accelerating a Commercial XML Parser Using SIMD and Multicore Technologies}
26
27\author{
28  {\rm Nigel Medforth }\\
29  International Characters, Inc./SFU
30  \and
31  {\rm Dan Lin}\\
32  Simon Fraser University
33  \and
34  {\rm Kenneth S. Herdy}\\
35  Simon Fraser University
36  \and
37  {\rm Arrvindh Shriraman}\\
38  Simon Fraser University
39  \and
40  {\rm Robert D. Cameron}\\
41  ICI/Simon Fraser University
42% copy the following lines to add more authors
43% \and
44% {\rm Name}\\
45%Name Institution
46} % end author
47\date{} % no date on first page
48\maketitle
49
50\thispagestyle{empty}
51
52\subsection*{Abstract}
53\input{abstract.tex}
54\section{Introduction}
55
56Parallelization and acceleration of XML parsing is a widely
57studied problem that has seen the development of a number
58of interesting research prototypes using both SIMD and
59multicore parallelism.   Most works have investigated
60data parallel solutions on multicore
61architectures using various strategies to break input
62documents into segments that can be allocated to different cores.
63For example, one possibility for data
64parallelization is to add a pre-parsing step to compute
65a skeleton tree structure of an  XML document \cite{GRID2006}.
66The parallelization of the pre-parsing stage itself can be tackled with
67state machines \cite{E-SCIENCE2007, IPDPS2008}.
68Methods without pre-parsing have used speculation \cite{HPCC2011} or post-processing that
69combines the partial results \cite{ParaDOM2009}.
70A hybrid technique that combines data and pipeline parallelism was proposed to
71hide the latency of a ``job'' that has to be done sequentially \cite{ICWS2008}.
72
73Fewer efforts have investigated SIMD parallelism, although this approach
74has the potential advantage of improving single core performance as well
75as offering savings in energy consumption \cite{HPCA2012}.
76Intel introduced specialized SIMD string processing instructions in the SSE 4.2 instruction set extension
77and showed how they can be used to improve the performance of XML parsing \cite{XMLSSE42}.
78The Parabix framework uses generic SIMD extensions and bit parallel methods to
79process hundreds of XML input characters simultaneously \cite{Cameron2009, cameron-EuroPar2011}.
80Parabix prototypes have also combined SIMD methods with thread-level parallelism to
81achieve further acceleration on multicore systems \cite{HPCA2012}.
82
83In this paper, we move beyond research prototypes to consider
84the detailed integration of both SIMD and multicore parallelism into the
85Xerces-C++ parser of the Apache Software Foundation, an existing
86standards-compliant open-source parser that is widely used
87in commercial practice.    The challenge of this work is
88to parallelize the Xerces parser in such a way as to
89preserve the existing APIs as well as offering worthwhile
90end-to-end acceleration of XML processing.   
91To achieve the best results possible, we undertook
92a nine-month comprehensive restructuring of the Xerces-C++ parser,
93seeking to expose as many critical aspects of XML parsing
94as possible for parallelization, the result of which we named icXML.   
95Overall, we employed Parabix-style methods of transcoding, tokenization
96and tag parsing, parallel string comparison methods in symbol
97resolution, bit parallel methods in namespace processing,
98as well as staged processing using pipeline parallelism to take advantage of
99multiple cores.
100
101\begin{figure*}[th]
102\begin{center}
103\begin{tabular}{rr}\\
104Source Data & \verb`<document>fee<element a1='fie' a2 = 'foe'></element>fum</document>`\\
105Tag Openers & \verb`1____________1____________________________1____________1__________`\\
106Start Tag Marks & \verb`_1____________1___________________________________________________`\\
107End Tag Marks & \verb`___________________________________________1____________1_________`\\
108Empty Tag Marks & \verb`__________________________________________________________________`\\
109Element Names & \verb`_11111111_____1111111_____________________________________________`\\
110Attribute Names & \verb`______________________11_______11_________________________________`\\
111Attribute Values & \verb`__________________________111________111__________________________`\\
112% String Ends & \verb`1____________1_______________1__________1_1____________1__________`\\
113% Markup Identifiers & \verb`_________1______________1_________1______1_1____________1_________`\\
114% Deletion Mask & \verb`_11111111_____1111111111_1____1111_11_______11111111_____111111111`\\
115% Undeleted Data & \verb``{\tt\it 0}\verb`________>fee`{\tt\it 0}\verb`__________=_fie`{\tt\it 0}\verb`____=__foe`{\tt\it 0}\verb`>`{\tt\it 0}\verb`/________fum`{\tt\it 0}\verb`/_________`
116\end{tabular}
117\end{center}
118\caption{XML Source Data and Derived Parallel Bit Streams}
119\label{fig:parabix1}
120\end{figure*}
121
122The remainder of this paper is organized as follows.   
123Section \ref{background} discusses the structure of the Xerces and Parabix XML parsers and the fundamental
124differences between the two parsing models.   
125Section \ref{architecture} then presents the \icXML{} design based on a restructured Xerces architecture to
126incorporate SIMD parallelism using Parabix methods.   
127Section \ref{multithread} moves on to consider the multithreading of the \icXML{} architecture
128using the pipeline parallelism model. 
129Section \ref{performance} analyzes the performance of both the single-threaded and
130multi-threaded versions of \icXML{} in comparison to original Xerces,
131demonstrating substantial end-to-end acceleration of
132a GML-to-SVG translation application written against the Xerces API.
133Section \ref{conclusion} concludes the paper with a discussion of future work and the potential for
134applying the techniques discussed herein in other application domains.
135
136
137\section{Background}
138\label{background}
139
140\input{background-xerces}
141
142
143\input{background-parabix}
144
145\input{background-fundemental-differences.tex}
146
147\section{Architecture}
148\label{architecture}
149
150\input{arch-overview.tex}
151
152\input{arch-charactersetadapters.tex}
153
154\input{parfilter.tex}
155
156\input{arch-contentstream.tex}
157
158\input{arch-namespace.tex}
159
160\input{arch-errorhandling.tex}
161
162\section{Multithreading with Pipeline Parallelism}
163\label{multithread}
164
165\input{multithread.tex}
166
167\section{Performance}
168\label{performance}
169\input{performance.tex}
170
171\section{Conclusion and Future Work}
172\label{conclusion}
173\input{conclusion.tex}
174
175
176\section*{Availability}
177
178The icXML software is available from its Trac repository at
179\begin{center}
180{\tt http://parabix.costar.sfu.ca/icXML}
181\end{center}
182On-line discussion of icXML is taking place on the
183the Xerces-C development mailing list {\tt c-dev@xerces.apache.org}.
184
185{
186  \footnotesize 
187  \bibliographystyle{acm}
188  \bibliography{reference}
189}
190\end{document}
191
192
193
194
195
196
197
Note: See TracBrowser for help on using the repository browser.