source: docs/HPCA2012/final_ieee/10-related.tex @ 1774

Last change on this file since 1774 was 1774, checked in by lindanl, 8 years ago

minor changes

File size: 3.0 KB
Line 
1\section{Related Work}
2\label{section:related}
3
4There has been work in the past which has sought to address the
5overheads of text processing in specific applications (e.g., XML
6parsers) and have adopted specialized hardware and software solutions
7for each application.
8% Event-based SAX (Simple API for XML) parsers avoid the tree
9% construction costs of the more flexible DOM (Document Object Model)
10% parsers \cite{Perkins05}.  Nicola and John specifically identified
11XML parsing as a threat to database performance  \cite{NicolaJohn03}
12outlines a number of potential directions for
13improving performance.  The commercial importance
14of XML parsing has spurred the development of numerous multi-threaded
15and hardware-based approaches: Multithreaded XML techniques include
16preparsing the XML file to locate key partitioning
17points~\cite{ParaDOM2009,LiWangLiuLi2009} and speculative
18p-DFAs~\cite{ZhangPanChiu09}. Hardware methods include custom XML
19chips \cite{Leventhal2009} and FPGA-based implementations
20\cite{DaiNiZhu2010}. Others have explored the design of custom
21hardware for bit parallel operations for text search in network
22processors~\cite{tan-sherwood-isca-2005}. Intel's SSE4.2 instructions targeted
23XML parsers, but these have not seen widespread use because of portability
24concerns and the programming challenges that accompany low level
25instructions~\cite{sse4}.
26
27Parallel bitstreams were introduced by Cameron et
28al.~\cite{CameronHerdyLin2008} and used it to implement an efficient
29UTF-8 to 16 parser. Subsequent work ~\cite{cameron-EuroPar2011}
30accelerated specific phases in an XML parser using widely available
31SSE2 instructions and proposed an inductive doubling instruction set
32~\cite{CameronLin2009}. In this paper, we have developed a generalized
33Parabix architecture and have described the software tool chain that
34programmers can use to build scalable text processing applications on
35commodity multicores. We have explored in the detail the tradeoffs
36between the SIMD implementations across processor generations (i.e.,
37SSE vs AVX) and multiple platfoms (ARM vs Intel). Finally, we have
38also explored the benefits of using pipeline-based multicore
39parallelism as a technique to eliminate imbalances in SIMD
40bitstream-based parallelization and improve overall efficiency.
41
42
43
44
45
46
47
48
49% To accelerate XML parsingmost of the recent work has
50% focused on parallelization through the use of multicore parallelism
51% for chip multiprocessors \cite{ZhangPanChiu09, },
52
53
54% In this paper, we have introduce parallel bit streams as a general
55% abstraction to parallelize and improve the performance general text
56% processing. We have developed a compiler tool chain and the runtime to
57% enable bit streams to exploit SIMD extensions found on commodity
58% processors.  We are also the first to perform a detailed analysis of
59% SIMD instruction extensions across three generations of Intel
60% processors including the new 256-bit AVX extensions. Finally, we have
61% shown the benefits of using multithreading in conjunction with data
62% parallel phases of the application.
Note: See TracBrowser for help on using the repository browser.