Changeset 4551

Timestamp:

May 14, 2015, 7:26:18 AM (3 years ago)

Author:

cameron

Message:

Strengthen claimed contributions, especially icGrep as a research artifact.

Location:

docs/Working/icGrep

Files:

• icgrep.pdf (modified) (previous)
• introduction.tex (modified) (2 diffs)

docs/Working/icGrep/introduction.tex

@@ -23 +23 @@
 a compressed active state array as well as to handling matching of
 multiple packet instances.
-These works have not generally tackled Unicode matching problems.
 
 Using parallel methods to accelerate matching of a single pattern on a 
@@ -35 +34 @@
 use dynamic convergence and range coalescing to dramatically reduce the number
 of states in play at any point, while Zhao et al. \cite{zhao2014challenging} address the problem using
-principled speculation.   Introducing a second line of research, 
-Cameron et al.~\cite{cameron2014bitwise} investigate new regular expression
-algorithms based on the concept of bitwise data parallelism, together with 
-implementations that exploit short vector SIMD instructions to accelerate
-regular expression matching even within a single core.
+principled speculation.   The second line of research is based on Parabix
+technology: the use of short vector SIMD instructions (e.g., Intel SSE or AVX instructions)
+to process bit streams in one-to-one correspondence with input character streams.
+Following this approach, Cameron et al.~\cite{cameron2014bitwise} have recently
+prototyped a new bitwise data parallel algorithm that shows significant
+acceleration of regular expression matching performance compared to sequential
+implementations even on a single core.
+
+These previous works in applying parallel methods to regular expression matching
+have generally focused on traditional ASCII-based matching problems.  
+However, documents and data formats increasingly use Unicode, particularly
+in the form of UTF-8.   W3Techs.com reports that the percentage of
+websites reporting UTF-8 as the character encoding has reached 84\% as of May 2015.
+But regular expression matching over UTF-8 introduces complexities
+of variable-length encodings for characters.   To process UTF-8 documents
+directly, Unicode regular expressions must generally undergo considerable 
+state expansion to equivalent regular expressions over byte sequences.
+Alternatively, if the price is paid to first transcode a UTF-8 document to UTF-16,
+the problem of very large transition tables arises.
 
 In this paper, we report on the use of the implementation of a full
-Unicode regular expression search tool, building on the bitwise
+UTF-8 regular expression search tool, building on the bitwise
 data parallel methods of the Parabix framework combined with the 
 dynamic compilation capabilities of LLVM~\cite{lattner2004llvm}.
 The result is \icGrep{}, 
 a high-performance, full-featured open-source grep implementation
-with systematic support for Unicode regular expressions.  As an alternative
+with systematic support for Unicode regular expressions, fully implementing
+Unicode level 1 requirements of Unicode Technical Standard \#18\cite{davis2012unicode}.
+As an alternative
 to classical grep implementations, \icGrep{} offers dramatic performance
 acceleration in Unicode regular expression matching. 
+
+The main contributions reported here are the extension of the bitwise data
+parallel methods for regular expression matching to handle UTF-8 natively,
+validating the bitwise data parallel method with the first complete
+implementation in a useful tool, and introducing \icGrep{} itself as
+research artifact.   From the latter perspective, \icGrep{} is significant 
+in several ways.   First, it allows the performance results reported here to 
+be independently replicated.  Secondly, it is a framework for further research 
+into regular expression matching using bitwise methods and is indeed being used
+to investigate Unicode level 2 requirements in a project funded by Google.
+Thirdly, it it fosters further research
+into bitwise data parallel algorithms generally and how they may take advantage
+of evolving architectural features.   Finally, \icGrep{} has also been
+designed as a teaching tool with many command line options to control
+algorithm features and print out internal representations of regular expressions and
+Parabix code.   
 
 The remainder of this paper is organized as follows.   Section \ref{sec:background}