Parallel Computing for Data Science

Chapter 11

Parallel Prefix Scan

Prefix scan computes cumulative operations, like R’s cumsum() for cumu-

lative sums:

> x <− c ( 1 2 ,5 ,1 3 )

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

11.1 General Formulation

In its general, abstract form, we have some associative operator, ⊗, and pre-

fix scan inputs sequence of objects (x

0

, ..., x

n−1

), and outputs (s

0

, ..., s

n−1

),

where

s

0

= x

0

,

s

1

= x

0

⊗ x

1

,

s

2

= x

0

⊗ x

1

⊗ x

2

,

...,

s

n−1

= x

0

⊗ x

1

⊗ ... ⊗ x

n−1

(11.1)

233

234 CHAPTER 11. PREFIX SCAN