30
Scan
•Scan is the parallel prefix operation for associative operators: +, *, min, max, &, |
•Scan is like reduction, but uses ||
•Prefix sum from the first lecture is +||
•   A Ϋ  2  4   6   8   0
•+||A Ϋ  2  6  12  20  20
•Yes, “or scan” is ||| as in
•        B  Ϋ 0  0  0  1  1  0  1  1
•Run:=|||B  Ϋ 0  0  0  1  1  1  1  1
•[2..n] Run := (Run != Run@w)*Index1;
• pos := max<< Run;
Think globablly