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

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

Updates

File size: 909 bytes
RevLine 
[3469]1New parallel algorithms for the classical grep (global regular expression
2print) problem are introduced together with implementations using
[3465]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.  The algorithms are also designed to scale with the availability
11of additional parallel resources such as the wider SIMD facilities (256-bit)
12of Intel AVX2 or future 512-bit extensions.   Our GPU implementations show
13further acceleration limited only by data transfer speed.
14
15
Note: See TracBrowser for help on using the repository browser.