source: docs/PACT14/abstract.tex @ 4502

Last change on this file since 4502 was 3883, checked in by cameron, 5 years ago

Reference cleanups; use GPU instead of GPGPU

File size: 1.0 KB
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 GPU implementations show
17further acceleration. 
Note: See TracBrowser for help on using the repository browser.