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
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
45 def demo():
46 # set the dimension sizes here
47 xdim = 9
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
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
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:])
80 def preduce_y(vec, pred=None, operation=None):
81 if operation is None:
82 operation = operator.add
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
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
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
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)