source: docs/Working/re/abstract.tex @ 3645

Last change on this file since 3645 was 3645, checked in by ksherdy, 5 years ago

Improved introduction section.

File size: 1.0 KB
Line 
1A new parallel algorithm for regular expression matching is developed
2and applied to the classical grep (global regular expression print)
3problem.  Building on the bitwise data parallelism previously
4applied to the manual implementation of token scanning in the
5Parabix XML parser, the new algorithm represents a general
6solution to the problem of regular expression matching using
7parallel bit streams.  On widely-deployed commodity hardware using
8128-bit SSE2 SIMD technology, our algorithm implementations can substantially
9outperform traditional grep implementations based on NFAs, DFAs or
10backtracking.  5X or better performance advantage against the
11best of available competitors is not atypical.
12The algorithms are also designed to scale with the availability
13of additional parallel resources such as the wider SIMD facilities (256-bit)
14of Intel AVX2 or future 512-bit extensions.   Our AVX2 implementation
15showed dramatic reduction in instruction count and significant
16improvement in speed.   Our GPGPU implementations show substantial
17further acceleration. 
Note: See TracBrowser for help on using the repository browser.