# Changeset 3477

Ignore:
Timestamp:
Sep 14, 2013, 9:04:14 AM (6 years ago)
Message:

Location:
docs/Working/re
Files:
2 edited

### Legend:

Unmodified
 r3476 $\text{\tt i} = \text{\tt MatchStar(c*2+p, b)}$ $\text{\tt q} = \text{\tt i >> f}$ As described subsequently, we use a two-level long-stream addition technique in both our AVX2 and GPU implementations.  In principle, one can extend the technique to additional levels.  Using 64-bit adders throughout, $\lceil\lg_{64}{n}\rceil)$ steps are needed for $n$-bit addition. A three-level scheme could coordinate 64 groups each performing 4096-bit long additions in a two-level structure. However, whether there are reasonable architectures that can support fine-grained SIMT style coordinate at this level is an open question. Using the methods outlined, it is quite conceivable that instruction set extensions to support long-stream addition could be added for future SIMD and GPU processors.   Given the fundamental nature of addition as a primitive and its novel application to regular expression matching as shown herein, it seems reasonable to expect such instructions to become available. \raggedbottom \section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis}