# Changeset 3625 for docs

Ignore:
Timestamp:
Feb 18, 2014, 4:45:09 AM (5 years ago)
Message:

Location:
docs/Working/re
Files:
4 edited

### Legend:

Unmodified
 r3624 is far from ideal. We have developed a technique using SIMD methods for constant-time We have developed a general model using SIMD methods for constant-time long-stream addition up to 4096 bits. We assume the availability of the following SIMD/SIMT operations \end{itemize} In this model, the \verb#hsimd<64>::mask(X)# and \verb#simd<64>::spread(x)# model the minimum communication requirements between the parallel processing units (SIMD lanes or SIMT processors).    In essence, we just need the ability to quickly send and receive 1 bit of information per parallel unit.    The \verb#hsimd<64>::mask(X)# operation gathers 1 bit from each of the processors to a central resource. After calculations on the gather bits are performed, we then just need an operation to invert the communication, i.e., sending 1 bit each from the central processor to each of the parallel units.   There are a variety of ways in which these facilities may be implemented depending on the underlying architecture; details of our AVX2 and GPU implementations are presented later. Given these operations, our method for long stream addition of two $f \times 64$ bit values \verb:X: and \verb:Y: is the following. \item Determine an $f$-bit mask identifying the fields of {\tt R} that need to be incremented to produce the final sum.  Here we find a new application of MatchStar! MatchStar. $\text{\tt i} = \text{\tt MatchStar(c*2, b)}$ will generate another carry.  In fact, if there is a sequence of digits that are all ones, then the carry must bubble through each of them.   This is just MatchStar! each of them.   This is just MatchStar. \item Compute the final result {\tt Z}. of addition as a primitive and its particular application to regular expression matching as shown herein, it seems reasonable to expect such instructions to become available. such instructions to become available.    Alternatively, it may be worthwhile to simply ensure that the \verb#hsimd<64>::mask(X)# \verb#simd<64>::spread(X)# operations are efficiently supported.