src/openpower/decoder/isa/remap_preduce_yield.py

   1 # a "yield" version of the Parallel Reduction REMAP algorithm.
   2 # the algorithm is in-place. it does not perform "MV" operations.
   3 # instead, where a masked-out value *should* be read from is tracked
   4 from copy import deepcopy
   5 import operator
   6
   7 # python "yield" can be iterated. use this to make it clear how
   8 # the indices are generated by using natural-looking nested loops
   9 def iterate_indices(SVSHAPE, pred=None):
  10     # get indices to iterate over, in the required order
  11     xd = SVSHAPE.lims[0]
  12     # create lists of indices to iterate over in each dimension
  13     ix = list(range(xd))
  14     # invert the indices if needed
  15     if SVSHAPE.invxyz[0]: ix.reverse()
  16     # start a loop from the lowest step
  17     step = 1
  18     steps = []
  19     while step < xd:
  20         step *= 2
  21         steps.append(step)
  22     # invert the indices if needed
  23     if SVSHAPE.invxyz[1]: steps.reverse()
  24     for step in steps:
  25         stepend = (step == steps[-1]) # note end of steps
  26         idxs = list(range(0, xd, step))
  27         results = []
  28         for i in idxs:
  29             other = i + step // 2
  30             ci = ix[i]
  31             oi = ix[other] if other < xd else None
  32             other_pred = other < xd and (pred is None or pred[oi])
  33             if (pred is None or pred[ci]) and other_pred:
  34                 if SVSHAPE.skip == 0b00: # submode 00
  35                     result = ci
  36                 elif SVSHAPE.skip == 0b01: # submode 01
  37                     result = oi
  38                 results.append([result + SVSHAPE.offset, 0])
  39             elif other_pred:
  40                 ix[i] = oi
  41         if results:
  42             results[-1][1] = (stepend<<1) | 1  # notify end of loops
  43         yield from results
  44
  45 def demo():
  46     # set the dimension sizes here
  47     xdim = 9
  48
  49     # set up an SVSHAPE
  50     class SVSHAPE:
  51         pass
  52     SVSHAPE0 = SVSHAPE()
  53     SVSHAPE0.lims = [xdim, 0, 0]
  54     SVSHAPE0.order = [0,1,2]
  55     SVSHAPE0.mode = 0b10
  56     SVSHAPE0.skip = 0b00
  57     SVSHAPE0.offset = 0       # experiment with different offset, here
  58     SVSHAPE0.invxyz = [0,0,0] # inversion if desired
  59
  60     SVSHAPE1 = SVSHAPE()
  61     SVSHAPE1.lims = [xdim, 0, 0]
  62     SVSHAPE1.order = [0,1,2]
  63     SVSHAPE1.mode = 0b10
  64     SVSHAPE1.skip = 0b01
  65     SVSHAPE1.offset = 0       # experiment with different offset, here
  66     SVSHAPE1.invxyz = [0,0,0] # inversion if desired
  67
  68     # enumerate over the iterator function, getting new indices
  69     shapes = list(iterate_indices(SVSHAPE0)), \
  70               list(iterate_indices(SVSHAPE1))
  71     for idx in range(len(shapes[0])):
  72         l = shapes[0][idx]
  73         r = shapes[1][idx]
  74         (l_idx, lend) = l
  75         (r_idx, rend) = r
  76         print ("%d->%d:%d" % (idx, l_idx, r_idx),
  77                "end", bin(lend)[2:], bin(rend)[2:])
  78
  79
  80 def preduce_y(vec, pred=None, operation=None):
  81     if operation is None:
  82         operation = operator.add
  83
  84     res = deepcopy(vec)
  85     xdim = len(vec)
  86     # set up an SVSHAPE
  87     class SVSHAPE:
  88         pass
  89     SVSHAPE0 = SVSHAPE()
  90     SVSHAPE0.lims = [xdim, 0, 0]
  91     SVSHAPE0.order = [0,1,2]
  92     SVSHAPE0.mode = 0b10
  93     SVSHAPE0.skip = 0b00
  94     SVSHAPE0.offset = 0       # experiment with different offset, here
  95     SVSHAPE0.invxyz = [0,0,0] # inversion if desired
  96
  97     SVSHAPE1 = SVSHAPE()
  98     SVSHAPE1.lims = [xdim, 0, 0]
  99     SVSHAPE1.order = [0,1,2]
 100     SVSHAPE1.mode = 0b10
 101     SVSHAPE1.skip = 0b01
 102     SVSHAPE1.offset = 0       # experiment with different offset, here
 103     SVSHAPE1.invxyz = [0,0,0] # inversion if desired
 104
 105     # enumerate over the iterator function, getting new indices
 106     shapes = list(iterate_indices(SVSHAPE0)), \
 107               list(iterate_indices(SVSHAPE1))
 108     for idx in range(len(shapes[0])):
 109         l = shapes[0][idx]
 110         r = shapes[1][idx]
 111         (l_idx, lend) = l
 112         (r_idx, rend) = r
 113         res[l_idx] = operation(res[l_idx], res[r_idx])
 114     return res
 115
 116 # run the demo
 117 if __name__ == '__main__':
 118     demo()
 119     vec = [1, 2, 3, 4, 9, 5, 6]
 120     res = preduce_y(vec)
 121     print (vec)
 122     print (res)