src/openpower/decoder/isa/remap_fft_yield.py

   1 # a "yield" version of the REMAP algorithm, for FFT Tukey-Cooley schedules
   2 # original code for the FFT Tukey-Cooley schedul:
   3 # https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.py
   4 """
   5     # Radix-2 decimation-in-time FFT (real, not complex)
   6     size = 2
   7     while size <= n:
   8         halfsize = size // 2
   9         tablestep = n // size
  10         for i in range(0, n, size):
  11             k = 0
  12             for j in range(i, i + halfsize):
  13                 jh = j+halfsize
  14                 jl = j
  15                 temp1 = vec[jh] * exptable[k]
  16                 temp2 = vec[jl]
  17                 vec[jh] = temp2 - temp1
  18                 vec[jl] = temp2 + temp1
  19                 k += tablestep
  20         size *= 2
  21 """
  22
  23 # python "yield" can be iterated. use this to make it clear how
  24 # the indices are generated by using natural-looking nested loops
  25 def iterate_butterfly_indices(SVSHAPE):
  26     # get indices to iterate over, in the required order
  27     n = SVSHAPE.lims[0]
  28     # createing lists of indices to iterate over in each dimension
  29     # has to be done dynamically, because it depends on the size
  30     # first, the size-based loop (which can be done statically)
  31     x_r = []
  32     size = 2
  33     while size <= n:
  34         x_r.append(size)
  35         size *= 2
  36     # invert order if requested
  37     if SVSHAPE.invxyz[0]: x_r.reverse()
  38
  39     if len(x_r) == 0:
  40         return
  41
  42     # start an infinite (wrapping) loop
  43     skip = 0
  44     while True:
  45         for size in x_r:           # loop over 3rd order dimension (size)
  46             x_end = size == x_r[-1]
  47             # y_r schedule depends on size
  48             halfsize = size // 2
  49             tablestep = n // size
  50             y_r = []
  51             for i in range(0, n, size):
  52                 y_r.append(i)
  53             # invert if requested
  54             if SVSHAPE.invxyz[1]: y_r.reverse()
  55             for i in y_r:       # loop over 2nd order dimension
  56                 y_end = i == y_r[-1]
  57                 k_r = []
  58                 j_r = []
  59                 k = 0
  60                 for j in range(i, i+halfsize):
  61                     k_r.append(k)
  62                     j_r.append(j)
  63                     k += tablestep
  64                 # invert if requested
  65                 if SVSHAPE.invxyz[2]: k_r.reverse()
  66                 if SVSHAPE.invxyz[2]: j_r.reverse()
  67                 for j, k in zip(j_r, k_r):   # loop over 1st order dimension
  68                     z_end = j == j_r[-1]
  69                     # now depending on MODE return the index
  70                     if SVSHAPE.skip == 0b00:
  71                         result = j              # for vec[j]
  72                     elif SVSHAPE.skip == 0b01:
  73                         result = j + halfsize   # for vec[j+halfsize]
  74                     elif SVSHAPE.skip == 0b10:
  75                         result = k              # for exptable[k]
  76
  77                     loopends = (z_end |
  78                                ((y_end and z_end)<<1) |
  79                                 ((y_end and x_end and z_end)<<2))
  80
  81                     yield result + SVSHAPE.offset, loopends
  82
  83 def demo():
  84     # set the dimension sizes here
  85     xdim = 8
  86     ydim = 0 # not needed
  87     zdim = 0 # again, not needed
  88
  89     # set total. err don't know how to calculate how many there are...
  90     # do it manually for now
  91     VL = 0
  92     size = 2
  93     n = xdim
  94     while size <= n:
  95         halfsize = size // 2
  96         tablestep = n // size
  97         for i in range(0, n, size):
  98             for j in range(i, i + halfsize):
  99                 VL += 1
 100         size *= 2
 101
 102     # set up an SVSHAPE
 103     class SVSHAPE:
 104         pass
 105     # j schedule
 106     SVSHAPE0 = SVSHAPE()
 107     SVSHAPE0.lims = [xdim, ydim, zdim]
 108     SVSHAPE0.order = [0,1,2]  # experiment with different permutations, here
 109     SVSHAPE0.mode = 0b01
 110     SVSHAPE0.skip = 0b00
 111     SVSHAPE0.offset = 0       # experiment with different offset, here
 112     SVSHAPE0.invxyz = [0,0,0] # inversion if desired
 113     # j+halfstep schedule
 114     SVSHAPE1 = SVSHAPE()
 115     SVSHAPE1.lims = [xdim, ydim, zdim]
 116     SVSHAPE1.order = [0,1,2]  # experiment with different permutations, here
 117     SVSHAPE0.mode = 0b01
 118     SVSHAPE1.skip = 0b01
 119     SVSHAPE1.offset = 0       # experiment with different offset, here
 120     SVSHAPE1.invxyz = [0,0,0] # inversion if desired
 121     # k schedule
 122     SVSHAPE2 = SVSHAPE()
 123     SVSHAPE2.lims = [xdim, ydim, zdim]
 124     SVSHAPE2.order = [0,1,2]  # experiment with different permutations, here
 125     SVSHAPE0.mode = 0b01
 126     SVSHAPE2.skip = 0b10
 127     SVSHAPE2.offset = 0       # experiment with different offset, here
 128     SVSHAPE2.invxyz = [0,0,0] # inversion if desired
 129
 130     # enumerate over the iterator function, getting new indices
 131     schedule = []
 132     for idx, (jl, jh, k) in enumerate(zip(iterate_butterfly_indices(SVSHAPE0),
 133                                           iterate_butterfly_indices(SVSHAPE1),
 134                                           iterate_butterfly_indices(SVSHAPE2))):
 135         if idx >= VL:
 136             break
 137         schedule.append((jl, jh, k))
 138
 139     # ok now pretty-print the results, with some debug output
 140     size = 2
 141     idx = 0
 142     while size <= n:
 143         halfsize = size // 2
 144         tablestep = n // size
 145         print ("size %d halfsize %d tablestep %d" % \
 146                 (size, halfsize, tablestep))
 147         for i in range(0, n, size):
 148             prefix = "i %d\t" % i
 149             k = 0
 150             for j in range(i, i + halfsize):
 151                 (jl, je), (jh, he), (ks, ke) = schedule[idx]
 152                 print ("  %-3d\t%s j=%-2d jh=%-2d k=%-2d -> "
 153                         "j[jl=%-2d] j[jh=%-2d] ex[k=%d]" % \
 154                                 (idx, prefix, j, j+halfsize, k,
 155                                       jl, jh, ks,
 156                                 ),
 157                                 "end", bin(je)[2:], bin(je)[2:], bin(ke)[2:])
 158                 k += tablestep
 159                 idx += 1
 160         size *= 2
 161
 162 # run the demo
 163 if __name__ == '__main__':
 164     demo()