parallel algorithm course 03
parallel algorithm
note
recursion
scan
map, reduce, scan
compact alg
pick up using an indication arr
A = 0 1 2 3 4 5 6 F = 0 1 1 0 0 1 0
output = 1 2 5
key to do parallel, acknowledge the target position in advance
scan F
idx = 0 1 2 2 2 3 3
fragment sum
application
F zero flag put in the front, one flag in the back
two stage compact, \(F^{-1}\) first, then use \(F\)
scatter
make it into a large sparse matrix and then reduce sum
binary base sort
Radix sort.
for from lowbit to highbit
scan\(T_1(n,b)=O(bn)\)
\(T_\infty(n,b)=(blogn)\)
if from highbit to lowbit, need fragment scan
bit-wise thinking.