# Changeset 2478

Ignore:
Timestamp:
Oct 18, 2012, 4:05:50 PM (7 years ago)
Message:

Rework introduction

File:
1 edited

### Legend:

Unmodified
 r2471 \documentclass[preprint]{sigplanconf} \documentclass[10pt,preprint]{sigplanconf} % The following \documentclass options may be useful: \begin{document} \conferenceinfo{PPoPP '13}{date, City.} \conferenceinfo{EuroSys '13}{date, City.} \copyrightyear{2013} \copyrightdata{[to be supplied]} \preprintfooter{short description of paper}   % 'preprint' option specified. \title{ICXML:  Accelerating a Commercial XML Parser Using Parallel Technologies} \title{ICXML:  Accelerating a Commercial XML Parser Using SIMD and Multicore Technologies} %\subtitle{Subtitle Text, if any} \authorinfo{Anonymous Hackers} {} {} % \authorinfo{Nigel Medforth \and Dan Lin \and Rob Cameron \and Arrvindh Shriraman} %            {Simon Fraser University} %            {\{nmedfort,lindanl,cameron,ashriram\}@cs.sfu.ca} % \authorinfo{Nigel Medforth \and Dan Lin \and Kenneth S. Herdy \and Arrvindh Shriraman \and Robert D. Cameron } %            {International Characters, Inc., and Simon Fraser University} %            {\{nmedfort,lindanl,ksherdy,ashriram,cameron\}@cs.sfu.ca} \maketitle \section{Introduction} Paragraph 1: Parallelization and acceleration of XML parsing is a widely studied problem that has seen the development of a number of interesting research prototypes. One possibility to data parallelizing the parsing process is by adding a pre-parsing step to get the skeleton that symbolized the tree structure of the XML document \cite{GRID2006}. The pre-parsing stage can also be parallelized using state machines \cite{E-SCIENCE2007, IPDPS2008}. Methods without pre-parsing require speculation \cite{HPCC2011} or post-processing that of interesting research prototypes using both SIMD and multicore parallelism.   Most works have investigated strategies for data parallel solutions on multicore architectures using various strategies to break input documents into segments that can be allocated to different cores. For example, one possibility for data parallelization is to add a pre-parsing step to compute a skeleton tree structure of an  XML document \cite{GRID2006}. The parallelization of the pre-parsing stage itself can be tackled with state machines \cite{E-SCIENCE2007, IPDPS2008}. Methods without pre-parsing have used speculation \cite{HPCC2011} or post-processing that combines the partial results \cite{ParaDOM2009}. A hybrid method that combines data parallelism and pipeline parallelism is proposed to hide the latency of the job'' that has to be done sequentially \cite{ICWS2008}. Intel introduced new string processing instructions in the SSE 4.2 instruction set extension and showed how it can be used to improve the performance of XML parsing \cite{XMLSSE42}. Parabix XML parser exploit the SIMD extensions to process hundreds of XML input characters simultaneously \cite{Cameron2009, cameron-EuroPar2011}. Parabix can also be combined with thread-level parallelism to achieve further improvement on multicore systems \cite{HPCA2012}. Paragraph 2: Fewer efforts have investigated SIMD parallelism, although this approach has the potential advantage of improving single core performance as well as offering savings in energy consumption. Intel introduced specialized SIMD string processing instructions in the SSE 4.2 instruction set extension and showed how they can be used to improve the performance of XML parsing \cite{XMLSSE42}. The Parabix framework uses generic SIMD extensions and bit parallel methods to process hundreds of XML input characters simultaneously \cite{Cameron2009, cameron-EuroPar2011}. Parabix prototypes have also combined SIMD methods with thread-level parallelism to achieve further acceleration on multicore systems \cite{HPCA2012}. In this paper, we move beyond research prototypes to consider the detailed integration of parallel methods into the Xerces-C++ parser of the Apache Software Foundation, an existing the detailed integration of both SIMD and multicore parallelism into the Xerces-C++ parser of the Apache Software Foundation, an existing standards-compliant open-source parser that is widely used in commercial practice.    Surprisingly, our results show that a speed-up of more than 100\% can be achieved in some applications, in apparent defiance of simple calculations based on Amdahl's law.  [Write text on these calculations based on reported costs of XML tokenization  (30\%?), transcoding...] Symbol table lookup: more than 15\%, compute key:3\% \cite{ZhaoBhuyan06} Schema valiation double, triple or quadruple the parsing cost. \cite{NicolaJohn03} Transcoding:  about 50\% \cite{Perkins05} Paragraph 3: in commercial practice.    The challenge of this work is to incorporate parallelize the Xerces parser in such a way as to preserve the existing APIs as well as offering worthwhile end-to-end acceleration of XML processing. To achieve the best results possible, we have undertaken a comprehensive restructuring of the Xerces-C++ parser, resolution, bit parallel methods in namespace processing, as well as staged processing with pipeline parallelism to take advantage of multiple cores. multiple cores. The remainder of this paper is organized as follows.   Section 2 discusses the structure of the Xerces and Parabix XML parsers and the fundamental differences between the two parsing models.   Section 3 then presents the icXML design based on a restructured Xerces architecture to incorporate SIMD parallelism using Parabix methods.   Section 4 presents a performance study demonstrating substantial end-to-end acceleration of a GML-to-SVG translation application written against the Xerces API. Section 5 moves on to consider the multithreading of the icXML architecture using the pipeline parallelism model.  Section 6 concludes the paper with a discussion of future work and the potential for applying the techniques discussed herein in other application domains. \section{Background}