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

Long stream addition figure

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/ppopp-re.tex

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