source: docs/Working/re/ppopp-re.tex @ 3471

%-----------------------------------------------------------------------------
%
%               Template for sigplanconf LaTeX Class
%
% Name:         sigplanconf-template.tex
%
% Purpose:      A template for sigplanconf.cls, which is a LaTeX 2e class
%               file for SIGPLAN conference proceedings.
%
% Guide:        Refer to "Author's Guide to the ACM SIGPLAN Class,"
%               sigplanconf-guide.pdf
%
% Author:       Paul C. Anagnostopoulos
%               Windfall Software
%               978 371-2316
%               paul@windfall.com
%
% Created:      15 February 2005
%
%-----------------------------------------------------------------------------


\documentclass{sigplanconf}

% The following \documentclass options may be useful:

% preprint      Remove this option only once the paper is in final form.
% 10pt          To set in 10-point type instead of 9-point.
% 11pt          To set in 11-point type instead of 9-point.
% authoryear    To obtain author/year citation style instead of numeric.

\usepackage{amsmath}


\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}

\conferenceinfo{PPoPP 2014}{February 15-19, 2013, Orland, Florida, United States} 
\copyrightyear{2013} 
\copyrightdata{978-1-nnnn-nnnn-n/yy/mm} 
\doi{nnnnnnn.nnnnnnn}

% Uncomment one of the following two, if you are not going for the 
% traditional copyright transfer agreement.

%\exclusivelicense                % ACM gets exclusive license to publish, 
                                  % you retain copyright

%\permissiontopublish             % ACM gets nonexclusive license to publish
                                  % (paid open-access papers, 
                                  % short abstracts)

\titlebanner{banner above paper title}        % These are ignored unless
\preprintfooter{short description of paper}   % 'preprint' option specified.

\title{Bitwise Data Parallelism in Regular Expression Matching}
\subtitle{Subtitle Text, if any}

\authorinfo{Robert D. Cameron \and Kenneth S. Herdy \and Dan Lin \and Meng Lin \and Ben Hull \and Thomas S. Shermer \and Arrvindh Shriraman}
           {Simon Fraser University}
           {\{cameron,ksherdy,lindanl,linmengl,bhull,shermer,ashriram\}@cs.sfu.ca}

\maketitle

\begin{abstract}
\input{abstract}
\end{abstract}
\category{Theory of computation}{Formal languages and automata theory}{Regular languages}
\category{Computer systems organization}{Parallel architectures}{Single instruction, multiple data}

% general terms are not compulsory anymore, 
% you may leave them out
%\terms
%term1, term2

\keywords
regular expression matching, grep, parallel bit stream technology

\section{Introduction}

The use of regular expressions to search texts for occurrences
of string patterns has a long history and
remains a pervasive technique throughout computing applications today.
% {\em a brief history}
The origins of regular expression matching date back to automata theory 
developed by Kleene in the 1950s \cite{kleene1951}.
Thompson \cite{thompson1968} is credited with the first construction to convert regular expressions
to nondeterministic finite automata (NFA). 
Following Thompson's approach, a regular expression of length m is first converted 
to an NFA with O(m) nodes. It is then possible to search a text of length n using the 
NFA in worst case O(mn) time. Often, a more efficient choice 
is to convert the NFA into a DFA. A DFA has only a single active state at any time
in the matching process and 
hence it is possible to search a text at of length n in worst-case O(n) optimal. 
However, it is well known that the conversion of an NFA to an equivalent DFA may result 
in state explosion. That is, the number of resultant DFA states may increase exponentially. 
In \cite{Baeza-yates_anew} a new approach to text searching was proposed based on bit-parallelism \cite{baeza1992new}.
This technique takes advantage of the intrinsic parallelism of bitwise operations
within a computer word. Given a w-bit word, the Shift-Or algorithm \cite{Baeza-yates_anew} algorithm uses the 
bit-parallel approach to
simulate an NFA in O($nm/w$) worst-case time. 

A disadvantage of the bit-parallel Shift-Or pattern matching approach
in comparison to simple string matching algorithms is an inability to skip input characters. 
For example, the Boyer-Moore family of algorithms \cite{boyer1977fast} skip input characters
to achieve sublinear times in the average case. Backward Dawg Matching 
(BDM) string matching algorithms \cite{crochemore1994text} based on suffix automata are able to skip characters. 
The Backward Nondeterministic Dawg Matching (BNDM) pattern matching algorithm \cite{wu1992fast} 
combines the bit-parallel advantages of Shift-Or and with the character skipping advantages of the BDM algorithm. 
The nrgrep pattern matching tool is built over the BNDM algorithm, 
and hence the name nrgrep \cite{navarro2000}. 

{\em a brief review}  
There has been considerable interest in using parallelization techniques
to improve the performance of regular expression matching on parallel hardware
such as multi-core processors (CPUs), graphics processing units (GPUs),
field-programmable gate arrays (FPGAs), and even more exotic architectures such as 
the Cell Broadband Engine (Cell BE). % FPGA results (synthesis of patterns into logic circuits) vs. memory based approaches (STTs in memory)
%CPU
Scarpazza and Braudaway \cite{scarpazza2008fast} demonstrated that 
text processing algorithms that exhibit irregular memory access patterns
can be efficiently executed on multicore hardware. 
In related work, Pasetto et al. presented a flexible tool that 
performs small-ruleset regular expression matching at a rate of 
2.88 Gbps per chip on Intel Xeon E5472 hardware \cite{pasetto2010}.
Naghmouchi et al. demonstrated that the Aho-Corasick (AC)
string matching algorithm \cite{aho1975} is well suited for parallel 
implementation on multi-core CPUs, GPUs and the Cell BE \cite{scarpazza2011top, naghmouchi2010}. 
On each hardware, both thread-level parallelism (additional cores) and data-level parallelism
(wide SIMD units) are leveraged for performance.
Salapura et. al., advocated the use of vector-style processing for regular expressions 
in business analytics applications and leveraged the SIMD hardware available 
on multi-core processors to acheive a speedup of better than 1.8 over a
range of data sizes of interest \cite{salapura2012accelerating}.
%Cell
In \cite{scarpazza2008}, Scarpazza and Russell presented a SIMD tokenizer 
that delivered 1.00–1.78 Gbps on a single
Cell BE chip and extended this approach for emulation on the Intel Larrabee
instruction set \cite{scarpazza2009larrabee}.
On the Cell BE, Scarpazza \cite{scarpazza2009cell} described a pattern matching 
implementation that delivered a throughput of 40
Gbps for a small dictionary of approximately 100 patterns, and a throughput of 3.3-3.4
Gbps for a larger dictionary of thousands of patterns. Iorio and van Lunteren \cite{iorio2008} 
presented a string matching implementation for automata that achieves 
4 Gbps on the Cell BE.
% GPU
In more recent work, Tumeo et al. \cite{tumeo2010efficient} presented a chunk-based
implementation of the AC algorithm for
accelerating string matching on GPUs. Lin et al., proposed 
the Parallel Failureless Aho-Corasick (PFAC) 
algorithm to accelerate pattern matching on GPU hardware and
achieved 143 Gbps throughput, 14.74 times faster
than the AC algorithm performed on a four core
multi-core processor using OpenMP \cite{lin2013accelerating}.

Whereas the existing approaches to parallelization have been
based on adapting traditional sequential algorithms to emergent
parallel architectures, we introduce both a new algorithmic
approach and its implementation on SIMD and GPU architectures.
This approach relies on a bitwise data parallel view of text
streams as well as a surprising use of addition to match
runs of characters in a single step.  The closest previous 
work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD
technology together with a parallel scanning primitive also 
based on addition \cite{cameron2011parallel}.   
However, in contrast to the deterministic, longest-match
scanning associated with the ScanThru primitive of that 
work, we introduce here a new primitive MatchStar
that can be used in full generality for nondeterministic
regular expression matching.   We also introduce a long-stream
addition technique involving a further application of MatchStar
that enables us to scale the technique to $n$-bit addition
in $log_{64} n$ steps.   We ultimately apply this technique,
for example, to perform
synchronized 4096-bit addition on GPU warps of 64 threads.

There is also a strong keyword match between the bit-parallel
data streams used in our approach and the bit-parallelism
used for NFA state transitions in the classical algorithms of 
Wu and Manber \cite{wu1992agrep}, Baez-Yates and Gonnet \cite{baeza1992new}
and Navarro and Raffinot \cite{navarro1998bit}.
However those algorithms use bit-parallelism in a fundamentally
different way: representing all possible current NFA states
as a bit vector and performing parallel transitions to a new
set of states using table lookups and bitwise logic.    Whereas
our approach can match multiple characters per step, bit-parallel
NFA algorithms proceed through the input one byte at a time.
Nevertheless, the agrep \cite{wu1992agrep} and 
nrgrep \cite{navarro2000} programs implemented using these techniques remain
among the strongest competitors in regular expression matching
performance, so we include them in our comparative evaluation.


The remainder of this paper is organized as follows.
Section \ref{sec:bitwise} presents our basic algorithm and MatchStar
using a model of arbitrary-length bit-parallel data streams.
Section \ref{sec:blockwise} discusses the block-by-block 
implementation of our techniques including the long stream
addition techniques for 256-bit addition with AVX2 and
4096-bit additions with GPGPU SIMT.
Section \ref{sec:analysis} 
Section \ref{sec:SSE2} 
Section \ref{sec:AVX2} 
Section \ref{sec:GPU} 
Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work.


\section{Matching with Bit-Parallel Data Streams}\label{sec:bitwise}

Whereas the traditional approaches to regular expression matching
using NFAs, DFAs or backtracking all rely on a byte-at-a-time 
processing model, the approach  we introduce in this paper is based 
on quite a different concept:  a data-parallel approach to simultaneous
processing of data stream elements.  Indeed, our most abstract model
is that of unbounded data parallelism: processing all elements of
the input data stream simultaneously.   In essence, we view
data streams as (very large) integers.   The fundamental operations
we apply are based on bitwise logic and long-stream addition.

Depending on the available parallel processing resources, an actual
implementation may divide an input stream into blocks  and process
the blocks sequentially.   Within each block  all elements of the
input stream are processed together, relying the availability of
bitwise logic and addition scaled to the block size.   On commodity
Intel and AMD processors with 128-bit SIMD capabilities (SSE2),
we typically process input streams 128 bytes at a time.   In this
case, we rely on the Parabix tool chain \cite{lin2012parabix}
to handle the details of compilation to block-by-block processing.
As weh show later, however, we have also adapted Parabix technology to processing
blocks of 4K bytes at time in our GPGPU implementation, relying
on our implementation of 4096-bit addition implemented using
SIMT processing of 64 threads.

A key concept in this streaming approach is the derivation of bit streams
that are parallel to the input data stream, i.e., in one-to-one
correspondence with the data element positions of the input
streams.   Typically, the input stream is a byte stream comprising
the 8-bit character code units of a particular encoding such
as extended ASCII, ISO-8859-1 or UTF-8.   However, the method may also
easily be used with wider code units such as the 16-bit code units of
UTF-16.   In the case of a byte stream, the first step is to transpose
the byte stream into eight parallel bit streams, such that bit stream
$i$ comprises the $i^\text{th}$ bit of each byte.   These streams form
a set of basis bit streams from which many other parallel bit
streams can be calculated, such as character class bit
streams such that each bit $j$ of the stream specifies
whether character $j$ of the input stream is in the class
or not.   {\bf perhaps a figure here.}


\section{Block-at-a-Time Processing}\label{sec:blockwise}




\section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis}

\begin{enumerate}
\item Operations
\item Memory behaviour per input byte: note tables of DFA/NFA.

Bille and Throup \em{Faster regular expression matching}\cite{bille2009faster}

\end{enumerate}



\section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2}
\subsection{Implementation Notes}
\subsection{Evaluation Methodology}
\subsection{Comparison}



\section{SIMD Scalability}\label{sec:AVX2}
\subsection{AVX Stream Addition}
  We use MatchStar for carry propagation.

\section{GPU Implementation}\label{sec:GPU}

\section{Miscellaneous}
\subsection{Skipping}
\subsection{Unicode}

\section{Conclusion}\label{sec:Concl}
\subsection{Contributions}
\begin{enumerate}
\item New Algorithm Class for Regular Expression Matching
\item MatchStar for Character Class Repetition
\item Long Stream Addition
\item Implementations showing performance and scalability
\end{enumerate}
\subsection{Future Work}
\begin{enumerate}
\item Substring capture
\item Unicode character classes
\item Nonregular regexp features: zero-width assertions, backreferences
\item Multicore for ruleset parallelism
\end{enumerate}



%\appendix
%\section{Appendix Title}

%This is the text of the appendix, if you need one.

\acks

This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada and
MITACS, Inc.

% We recommend abbrvnat bibliography style.

\bibliographystyle{abbrvnat}

% The bibliography should be embedded for final submission.
 
\bibliography{reference}

%\begin{thebibliography}{}
%\softraggedright

%\bibitem[Smith et~al.(2009)Smith, Jones]{smith02}
%P. Q. Smith, and X. Y. Jones. ...reference text...
%
%\end{thebibliography}


\end{document}