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

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

Final edits

File size: 1.1 KB
1New parallel algorithms for the classical grep (global regular expression
2print) problem are introduced together with implementations using
3commodity SIMD and GPU technologies.   Building on the bitwise
4data parallelism underlying previous work in Unicode transcoding and
5XML parsing, the new algorithms add the important element of
6nondeterminism for tackling the full generality of regular
7expression processing.               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 GPU implementations show
17further acceleration limited primarily by data transfer speed.
Note: See TracBrowser for help on using the repository browser.