Ignore:
Timestamp:
Feb 15, 2014, 8:54:07 PM (5 years ago)
Author:
cameron
Message:

Explain while loop termination; tone down long-addition claims

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/abstract.tex

    r3513 r3623  
    1 New parallel algorithms for the classical grep (global regular expression
    2 print) problem are introduced together with implementations using
    3 commodity SIMD and GPU technologies.   Building on the bitwise
    4 data parallelism underlying previous work in Unicode transcoding and
    5 XML parsing, the new algorithms add the important element of
    6 nondeterminism for tackling the full generality of regular
    7 expression processing.               On widely-deployed commodity hardware using
     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
    88128-bit SSE2 SIMD technology, our algorithm implementations can substantially
    99outperform traditional grep implementations based on NFAs, DFAs or
     
    1414of Intel AVX2 or future 512-bit extensions.   Our AVX2 implementation
    1515showed dramatic reduction in instruction count and significant
    16 improvement in speed.   Our GPU implementations show
    17 further acceleration limited primarily by data transfer speed.
    18 
    19 
     16improvement in speed.   Our GPU implementations show substantial
     17further acceleration. 
Note: See TracChangeset for help on using the changeset viewer.