parallel algorithm course 03

Posted on March 23, 2022 by Shiguang Wu
Tags: PA

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

application


F zero flag put in the front, one flag in the back

two stage compact, \(F^{-1}\) first, then use \(F\)


scatter

what is 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.