# Changeset 3463 for docs/Working

Ignore:
Timestamp:
Sep 11, 2013, 9:15:51 PM (6 years ago)
Message:

Unbounded parallelism paras

File:
1 edited

### Legend:

Unmodified
 r3459 \section{Unbounded Bitwise Data Parallelism}\label{sec:bitwise} Whereas all traditional regular expression matching engines are fundamentally based on an element-at-a-time processing model, the approach we introduce in this paper is based on quite a different conceptual model: processing all elements of an input data stream simultaneously.    Depending on the available parallel processing resources, an actual implementation may divide an input stream into segments and process the segments sequentially.   Within each segment, all elements of the input stream are processed in parallel.   The approach is inherently scalable and can be adapted to a variety of parallel architectures. The fundamental primitives required are bitwise logic and long-stream addition. A key concept in this 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$\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.} Using the SIMD capabilities of commodity processors, the basis bit streams and character class bit streams may be efficiently computed using the Parabix framework that has been developed and used extensively for high-performance XML parsing \cite{}.  For example, working with the 128-bit SIMD registers on commodity Intel and AMD processors, the Parabix framework can be employed to process input streams in blocks of 128 bytes at a time.   However, the general model is not dependent on any particular data block size and can be scaled for arbitrary sized blocks depending on available resources. \section{Bitwise Regular Expression Matching with MatchStar}\label{sec:regexp}