Structured Parallel Programming

Chapter 5

Collectives

In Chapter 4, we introduced the map pattern, which describes embarrassing parallelism: parallel computations on a set of completely independent operations. However, obviously we need other patterns to deal with problems that are not completely independent.

The collective operations are a set of patterns that deal with a collection of data as a whole rather than as separate elements. The reduce pattern allows data to be summarized; it combines all the elements in a collection into a single element using some associative combiner operator. The scan pattern is similar but reduces every subsequence of a collection up to every position in the input. The usefulness of reduce is easy to understand. One simple example is summation, ...