# Changeset 3466 for docs

Ignore:
Timestamp:
Sep 12, 2013, 12:09:26 PM (6 years ago)
Message:

Location:
docs/Working/re
Files:
2 edited

### Legend:

Unmodified
 r3464 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 implement matching operations.   The closest previous work is that underlying bit-parallel XML parsing using 128-bit SSE2 SIMD 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}. addition technique involving a further application of MatchStar that enables us to scale the technique to $n$-bit addition in $log_{64} n$ steps. 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 of regular expression using the bitap and Wu-Manber NFA (nondeterministic finite automata) algorithms \cite{}. 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: to represent all possible current NFA states as a bit vector and to perform byte-at-a-time transitions using the bitwise operations.   Nevertheless, the agrep and nrgrep programs implemented using these techniques remain among the strongest competitors in overall performance to our implementations. 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} Section \ref{sec:unbounded} presents our basic algorithm using a model of unbounded bitwise data parallelism. Section \ref{sec:regexp} Section \ref{sec:analysis} \section{Unbounded Bitwise Data Parallelism}\label{sec:bitwise} \section{An Unbounded Model for Bitwise Regular Expression Matching}\label{sec:unbounded} Whereas all traditional regular expression matching engines are 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$\th bit of each byte.   These streams form $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