Parallel reduce notes
orig = [1,2,3,4,5,6, 7, 8, 9,10,11]
shift1 = [0,1,2,3,4,5, 6, 7, 8, 9,10]
mask = [1,0,1,0,1,0, 1, 0, 1, 0, 1]
sum = [1,0,5,0,9,0,13, 0,17, 0,21]
orig = [1,0,5,0,9, 0,13, 0,17, 0,21]
shift2 = [0,0,1,0,5, 0, 9, 0,13, 0,17]
mask = [1,0,1,0,1, 0, 1, 0, 1, 0, 1]
sum = [1,0,6,0,14,0,22, 0,30, 0,38]
orig = [1,5,5,9,9,13,13,17,17,21,21]
# example of shiftRight add, mult by bitmask, the filter
1,2,3,4,5,6,7,8,9,10,11
1,0,5,0,9,0,13,0,17,0,21
1,5, 9,13,17,21
0,1, 5, 9,13,17
0,1, 0, 1, 0, 1
0,6, 0,22, 0,38
6,22,38
0, 6,22
1, 0, 1
6, 0,60
6,60
0, 6
0, 1
0,66
##########################################
res1 = (orig[0] + orig[1]) * [1,0,1,...]
res1 = filterZeros(res1)
res2 = (res1[0] + res1[1]) * [0,1,0...]
res2 = filterZeros(res2)
res3 = (res2[0] + res2[1]) * [1,0,1,...]
res3 = filterZeros(res3)
1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
3, 3, 7, 7,11,11,15,15,19,19,11
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0
10, 18, 26, 34, 30
1, 2, 3, 4, 5
0, 1, 2, 3, 4
1, 3, 5, 7, 9
1, 0, 1, 0, 1
1, 0, 5, 0, 9
1, 5, 5, 9, 9 # backfill
1, 5, 5, 9, 9
0, 1, 5, 5, 9 # pass forward
1, 0, 1, 0, 1
0, 6, 0,14, 0
6, 6,14,14, 0 # backfill
0, 6, 6,14,14 # pass forward
1, 0, 1, 0, 1
1, 0, 5, 0, 9
1, 1, 5, 5, 9
0, 1, 0, 1, 0
0, 1, 0, 5, 0
// basic version where the right acts as a sink
1, 2, 3, 4, 5
0, 1, 2, 3, 4
1, 0, 1, 0, 1
1, 0, 5, 0, 9
1, 0, 5, 0, 9
0, 1, 0, 5, 0
0, 1, 0, 1, 1
0, 1, 0, 5, 9
0, 1, 0, 5, 9
0, 0, 1, 0, 5
1, 0, 1, 0, 1
0, 0, 1, 0,14
0, 0, 1, 0,14
0, 0, 0, 1, 0
0, 1, 0, 1, 1
0, 0, 0, 1,14
0, 0, 0, 1,14
0, 0, 0, 0, 1
1, 0, 1, 0, 1
0, 0, 0, 0,15
// pair values to add
1, 2, 3, 4, 5 //length 1 blocks
3, 3, 7, 7, 5 //length 2 blocks
10, 10, 10, 10, 5 //length 4 blocks
15, 15, 15, 15, 15
// pairs indices
0-1, 1-0, 2-3, 3-2, 4
0-2, 1-3, 2-0, 3-1, 4
0-4, 1-5, 2-6, 3-7, 4-0
// beyond the borders, the value is zero wrt the last element, but repeats the last value wrt any other
img1[0] = img0[0] + img0[1]
img1[1] = img0[1] + img0[0]
(0,1), (2,3), (4,5)
(0,2), (1,3), (4,6)
(0,4), (1,5), (2,6), (3,7), (4,0)
#first iteration
1, 2, 3, 4, 5 [0, 0, 0, 0, 0]
2, 3, 4, 5, 0 #shift left 1
3, 5, 7, 9, 5 #sum
1, 0, 1, 0, 1 #mask
3, 0, 7, 0, 5 #outL
1, 2, 3, 4, 5
0, 1, 2, 3, 4 #shift right 1
1, 3, 5, 7, 9 #sum
0, 1, 0, 1, 0 #mask
0, 3, 0, 7, 0 #outR
3, 0, 7, 0, 5 #outL
0, 3, 0, 7, 0 #outR
3, 3, 7, 7, 5 #out
#second iteration
3, 3, 7, 7, 5
7, 7, 5, 0, 0 # shift left 2
10,10,12, 7, 5 #sum
1, 1, 0, 0, 1 #mask
10,10, 0, 0, 5 #outR
3, 3, 7, 7, 5
0, 0, 3, 3, 7 #shift right 2
3, 3,10,10,12 #sum
0, 0, 1, 1, 0 #mask
0, 0,10,10, 0 #outL
10,10, 0, 0, 5 #outR
0, 0,10,10, 0 #outL
10,10,10,10, 5 #out
#third iteration
10,10,10,10, 5
0, 0, 0, 0,10 #shift right 4
10,10,10,10,15 #sum
0, 0, 0, 0, 1 #mask ???? works, but shouldn't it start with 1's?
0, 0, 0, 0, 15 #outR
10,10,10,10, 5
5, 0, 0, 0, 0 #shift left 4
15,15,15,15, 5 #sum
1, 1, 1, 1, 0 #mask
15,15,15,15, 0 #outL
0, 0, 0, 0,15 #outR
15,15,15,15, 0 #outL
15,15,15,15,15
lesson: there's a border of zeros, and then it starts repeating????
XXX bad math!!! now it's corrected
start out as zeros, but get summed like other elements if they get involved?
1, 2, 3, 4, 5, 6 [?, ?]
3, 3, 7, 7,11,11 [0, 0]
10,10,10,10,11,11 [11, 11]
21,21,21,21,21,21
1, 2, 3, 4, 5 [0, ?]
3, 3, 7, 7, 5 [0, 0]
10,10,10,10, 5
15,15,15,15
Parallel reduce - Masked sum propagation