Ignore:
Timestamp:
Dec 7, 2011, 8:05:12 AM (8 years ago)
Author:
cameron
Message:

Updates to intro; abstract

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/HPCA2012/final_ieee/01-intro.tex

    r1751 r1752  
    11\section{Introduction}
    22Modern applications ranging from web search to analytics are mainly
    3 data centric operating large swathes of data. Information expansion
     3data centric operating over large swaths of data. Information expansion
    44and diversification of data has resulted in multiple textual storage
    5 formats. XML is a widely-used text-based data storage format. XML is a
    6 standard of the web consortium that provides a common framework for
    7 encoding and communicating data.  It is used in applications ranging
     5formats.  Of these, XML is one of the most widely used standards, providing
     6a common framework for encoding and communicating data. 
     7It is used in applications ranging
    88from Office Open XML in Microsoft Office to NDFD XML of the NOAA
    99National Weather Service, from KML in Google Earth to Castor XML in
    1010the Martian Rovers. To enable these diverse applications we need high
    11 performance, scalable, and energy efficient text processing stored in
    12 these XML documents.
     11performance, scalable, and energy efficient processing techniques
     12for textual data in general, and XML, in particular.
    1313
    1414%; in server
     
    1919
    2020Unfortunately, given the limited levels of parallelism that can be
    21 found in text processing, for example, XML parsing, is inherently
    22 sequential, it is not clear how this important class of application
     21found in traditional text processing, it is not clear how this important
     22class of application
    2323can benefit from the growth in multicore processors. As a widely cited
    24 Berkeley study~\cite{Asanovic:EECS-2006-183} reports, the ``thirteenth
    25 dwarf'' (parsers/finite state machines) which process text is
     24Berkeley study~\cite{Asanovic:EECS-2006-183} reports, text processing
     25applications represented by the ``thirteenth
     26dwarf'' (parsers/finite state machines) are
    2627considered to be the hardest application class to parallelize and
    27 process efficienctly.  Conventional software-based text parsers have
     28process efficiently.  Conventional software-based text parsers have
    2829many inefficiencies including considerable branch misprediction
    2930penalties due to complex input-dependent branching structures as well
     
    3132processing. ASIC chips that process XML textual data have been around
    3233since early 2003, but typically lag behind CPUs in technology due to
    33 cost constraints~\cite{xmlchip}. They also focus mainly on speeding up
    34 the parser computation itself and are limited by the poor memory
    35 behaviour.
    36 
    37 
     34cost constraints~\cite{xmlchip}. 
     35%They also focus mainly on speeding up
     36%the computational work alone, without addressing problems of poor memory
     37%behaviour.
    3838
    3939%
     
    4141%
    4242
    43 
    44 
    45 
    46 %However, classical Dennard voltage scaling has reached its limits
    47 %which gives the traditional byte-at-a-time processing methods little
    48 %space for further improvement. An alternative is to increase energy
    49 %efficiency by operating at more optimal core frequencies and achieve
    50 %better performance with a larger number of cores.
    51 %~\cite{blake-isca-2010}, in scaling our
    52 %chips~\cite{esmaeilzadeh-isca-2011}
    53 
    54 Recently, we developed a novel representation of
    55 data~\cite{Cameron2008,CameronLin2009}, Parabix (Parallel bitstreams),
    56 to aid parsers and text processing tools. Parabix transposes
    57 byte-oriented character data into parallel bit streams, where each bit
    58 represents one character from the input data. We explored the use of
    59 Parabix representation in UTF-8 to UTF-16 conversion and in specific
    60 internal passes of an XML parser~\cite{cameron-EuroPar2011}.
     43Parallel bit stream (Parabix) technology is a promising new approach
     44for high performance text processing taking advantage of the SIMD
     45capabilities of commodity processors.   Based on the transposition
     46of byte-oriented character data into parallel bit streams each
     47with one bit per input byte,
     48first-generation Parabix technology has been
     49applied to accelerate UTF-8 to UTF-16 transcoding \cite{Cameron2008} as
     50well as exact string matching in protein identification \cite{JMBE:31@99}.
     51It has also been applied to the problem of XML parsing using
     52a traditional recursive-descent parser accelerated with
     53sequential bit scans.  Most recently, the foundation of
     54second-generation Parabix technology and the toolchain
     55described in this paper has been established with the
     56introduction of a parallel scanning primitive to replace
     57sequential bit scans \cite{cameron-EuroPar2011}.
    6158
    6259
     
    8279
    8380
    84 
    85 
    86 
    87 
    88 
    89 
    90 
    91 
    9281In this paper, we generalize parallel bitstreams and develop the
    9382Parabix programming framework to help programmers build text
     
    9988of character positions in an input stream simultaneously dramatically
    10089improving the execution efficiency. We describe the overall Parabix
    101 tool chain, a novel execution framework and software build environment
     90tool chain, a novel execution framework and a software build environment
    10291that enables text processing applications to effectively exploit
    10392commodity multicores.
    10493
    105 
    106 We apply Parabix technology to the problem of XML parsing.
     94We study in detail the performance of Parabix technology
     95in application to the problem of XML parsing on multiple
     96architectures.
    10797Figure~\ref{perf-energy} showcases the overall efficiency of our
    108 framework. The Parabix-XML parser improves the performance %by
    109 ?$\times$ and energy efficiency
    110 %by ?$\times$ several-fold compared to widely-used software parsers,
    111 approaching the
    112 %?$cycles/input-byte$ performance of ASIC XML
    113 parsers~\cite{xmlchip,DaiNiZhu2010}. The Parabix-XML parser exploits
     98framework, dramatically improving both performance and
     99energy efficiency. The Parabix-XML parser exploits
    114100the bitstream technology to dramatically reduce branches in the
    115101parsing routines resulting in a more efficient pipeline. It also
    116102substantially improves register utilization which minimizes energy
    117103wasted on cache misses and data transfers.\footnote{The actual energy consumption of the XML
    118   ASIC chips is not published by the companies.} We make the following contributions:
     104  ASIC chips is not published by the companies.}
    119105
    120 
    121 
     106We make the following contributions:
    122107%
    123108
     
    127112processors.  While studied in the context of XML parsing, the Parabix
    128113framework can be widely applied to many problems in text processing
    129 and parsing.  We have released Parabix completely open source and are
     114and parsing.  We have released Parabix as open source and are
    130115interested in exploring the applications that can take advantage of
    131116our tool chain (\textit{http://parabix.costar.sfu.ca/}).
Note: See TracChangeset for help on using the changeset viewer.