Changes between Version 12 and Version 13 of ShufflePatternLibrary


Ignore:
Timestamp:
Apr 30, 2014, 2:17:37 AM (5 years ago)
Author:
cameron
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ShufflePatternLibrary

    v12 v13  
    134134== Useful Functions ==
    135135{{{
    136 pattern_diff(P, m, k)
    137   [P[i + k] - P[i] for i in range(0, m-k)]
    138 }}}
    139 
    140 {{{
    141 circular_diff(P, m, k)
    142   [P[(i + k) mod m - P[i] for i in range(0, m-k)]
    143 }}}
     136def pattern_diff(P, m, k):
     137  return [P[i + k] - P[i] for i in range(0, m-k)]
     138
     139def pattern_signature(P):
     140  return (P[0], pattern_diff(P, len(P), 1))
     141}}}
     142
     143
    144144
    145145== Standard Pattern Examples ==
     
    151151=== The Rotate Pattern ===
    152152
    153 The double vector rotate pattern is recognized as follows.
    154 Form the first-order difference vector of the shuffle index vector.
    155 {{{
    156 
    157 }}}
     153Rotations may easily be identified as patterns which have a
     154pattern unit difference of 1 in all cases, except a single instance of a 1-n
     155difference, where n is the vector (or double vector) size.
     156
     157{{{
     158>>> pattern_diff([1,2,3,4,5,6,7,0], 8,1)
     159[1, 1, 1, 1, 1, 1, -7]
     160>>> pattern_diff([2,3,4,5,6,7,0,1], 8,1)
     161[1, 1, 1, 1, 1, -7, 1]
     162>>> pattern_diff([3,4,5,6,7,0,1,2], 8,1)
     163[1, 1, 1, 1, -7, 1, 1]
     164}}}
     165
     166A rotation may occur within lanes.   For example, the pattern [1,2,3,0,5,6,7,4]
     167is a rotate right 1 within each of 2 lanes.   The lane detection is accomplished
     168by noting that the n/2 pattern diff is a constant vector of n/2 values.
     169Then the rotation pattern is exposed by examining a single lane.
     170
     171
     172{{{
     173>>> pattern_diff([1,2,3,0,5,6,7,4], 8, 4)
     174[4, 4, 4, 4]
     175>>> pattern_diff([1,2,3,0,5,6,7,4], 4, 1)
     176[1, 1, -3]
     177>>>
     178}}}
     179
    158180
    159181=== The Shift Left Pattern ===
     182Shift left patterns require that the second shufflevector argument be
     183zeroinitializer so that 0s can be inserted on the right.   Note
     184the little-endianness issue.
     185
     186{{{
     187>>> pattern_signature([8,8,1,2,3,4,5,6])
     188(8, [0, -7, 1, 1, 1, 1, 1])
     189>>> pattern_signature([8,8,8,1,2,3,4,5])
     190(8, [0, 0, -7, 1, 1, 1, 1])
     191}}}
    160192
    161193=== The Shift Right Logical Pattern ===
    162194
    163 === The Shift Right Arithmetic Pattern ===
     195Shift right logical patterns require that the second shufflevector argument be
     196zeroinitializer so that 0s can be inserted on the left.   Note
     197Little-endianness.   The shift constant is conveniently
     198the value of the first element __times the field width__.
     199{{{
     200(2, [1, 1, 1, 1, 1, 1, 0])
     201>>> pattern_signature([1,2,3,4,5,6,7,8])
     202(1, [1, 1, 1, 1, 1, 1, 1])
     203>>> pattern_signature([0,1,2,3,4,5,6,7])
     204(0, [1, 1, 1, 1, 1, 1, 1])
     205>>> pattern_signature([5,6,7,8,8,8,8,8])
     206(5, [1, 1, 1, 0, 0, 0, 0])
     207}}}
     208
    164209
    165210=== The Zero-Extend Pattern ===
    166211
     212{{{
     213}}}
     214
    167215=== The Merge Pattern ===
     216Merge patterns have alternation n and 1-n values.
     217{{{
     218>>> pattern_signature([0,8,1,9,2,10,3,11])
     219(0, [8, -7, 8, -7, 8, -7, 8])
     220}}}
    168221
    169222=== The Pack Pattern ===
     223Pack patterns are characterized by a constant pattern difference of 2.
     224
     225{{{
     226>>> pattern_signature([0,2,4,6,8,10,12,14])
     227(0, [2, 2, 2, 2, 2, 2, 2])
     228>>> pattern_signature([1,3,5,7,9,11,13,15])
     229(1, [2, 2, 2, 2, 2, 2, 2])
     230}}}
    170231
    171232=== The Parallel Extract Pattern ===
     233{{{
     234}}}
    172235
    173236=== The Parallel Deposit Pattern ===
     237{{{
     238}}}
    174239
    175240=== Vectorized Sequential Code ===
    176241
    177 
    178 
    179 
    180 
     242{{{
     243}}}
     2443
     245
     246
     247