source: docs/Working/re/conclusion.tex @ 3653

Last change on this file since 3653 was 3648, checked in by cameron, 6 years ago

Tone down long-stream addition; discuss scalability

File size: 2.6 KB
3A new class of regular expression matching algorithm has been
4introduced based on the concept of bit-parallel data streams
5together with the MatchStar operation.  The algorithm is
6fully general for nondeterministic regular expression matching;
7however it does not address the nonregular extensions
8found in Perl-compatible backtracking implementations.
9Taking advantage of the SIMD features available on commodity
10processors, its implementation in a grep offers consistently
11good performance in contrast to available alternatives. 
12For moderately complex expressions, 10X or better
13performance advantages over DFA-based gre2p and 5X performance
14advantage over nrgrep were frequently seen.
15While lacking some
16special optimizations found in other engines to deal with
17repeated substrings or to perform skipping actions based
18on fixed substrings, it nevertheless performs competitively
19in all cases. 
21A model for parallelized long-stream addition has also been presented
22in the paper, allowing our techniques to scale beyond
23the blocks of 128 bytes we use with the SSE2 implementation.
24This model allowed straightforward extension to the 256-byte
25block size used in our AVX2 implementation and should
26continue to scale well up for SIMD vectors up to 4096 bytes
27in length based on 64-bit additions.    The model also
28supports GPGPU implementation with some additional
29effort, and suggests that direct GPGPU support for
30the \verb#hsimd<64>::mask(X)# and
31\verb#simd<64>::spread(x)#  operations could
32be valuable.
34The principal overhead in this method is the transposition of
35input data to parallel bit stream form.   However, this overhead reduces
36as SIMD register widths increase.   It is also possible to introduce
37new SIMD instructions that could dramatically reduce the
38cost of transposition\cite{cameron2009architectural}.
40\paragraph*{Future Work}
42An important area of future work is to develop and assess
43multicore versions of the algorithm to handle regular expression
44matching problems involving larger rulesets than are
45typically encountered in the grep problem.  Such implementations
46could have useful application in tokenization and network
47intrusion detection for example.
49Another area of interest is to extend the capabilities of
50the underlying method with addition features for substring
51capture, zero-width assertions and possibly
52backreference matching.  Extending Unicode support beyond
53basic Unicode character handling to include full Unicode
54character class support and normalization forms is also
55worth investigating.
Note: See TracBrowser for help on using the repository browser.