Parallel Prefix Scan

Prefix scan computes cumulative operations, like R’s cumsum() for cumulative sums:

> x <− c (12 ,5 , 13 ) > cumsum( x ) [ 1 ] 12 17 30

The scan for sums of (12,5,13) would then be

(12, 12 + 5, 12 + 5 + 13) = (12, 17, 30),

as we saw above.