New Parallel Algorithms

`std::accumulate()`

Adds each element to an initial value
Returns the result
By default, the operator + is used to perform the addition
We can pass a callable object as an optional fourth argument

`std::accumulate()` Execution

Specified to execute sequentially

std::vector<int> vec{1, 2, 3, 4, ,5, 6, 7};

// Sum the elements of vec, using initial value 0
auto sum = std::accumulate(vec.begin(), vec.end(), 0);

// Performed in left-to-right order, one addition at a time
((((0 + 1) + 2) + 3) + ...)

Cannot be parallelized
- Each operation must complete before the next one can start
Cannot be vectorized
- Each operation can only take two arguments

`std::reduce()` Execution

Re-implementation of std::accumulate()
Supports execution policies

std::vector<int> vec{1, 2, 3, 4, 5, 6, 7};

// Performed as seven additions (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7)
// May execute out of order
auto sum = std::reduce(se::seq, vec.begin(), vec.end(), 0);

// Performed as four parallel additions ((0 + 1) + (2 + 3) + (4 + 5) + (6 + 7))
auto sum = std::reduce(se::par, vec.begin(), vec.end(), 0);

`std::reduce()` and vectorization

std::reduce() also supports the other execution policies

// Performed as two vectorized additions (0 + 1 + 2 + 3) + (4 + 5 + 6 + 7)
auto sum = reduce(se::unseq, vec.begin(), vec.end(), 0);

// Performed as two parallel vectorized additions ((0 + 1 + 2 + 3) + (4 + 5 + 6 + 7))
auto sum = reduce(se::par_unseq, vec.begin(), vec.end(), 0);

Reduce with parallel execution resembles a tree of operations

`std::reduce()` Restrictions

reduce() will not give the correct answer if
- Reordering the operations alters the result, or
- Regrouping them alters the result
The operator used must be
- Commutative - order of operations is not important x + y == y + x
- Associative - grouping operations does not change the result (x + y) + z == x + (y + z)
- Not true for subtraction, floating point arithmetic, etc

`std::partial_sum()`

Calculates the sum of the elements so far

std::vector<int> vec{1, 2, 3, 4};
std::vector<int> vec2(vec.size());

std::partial_sum(vec.begin(), vec.end(), vec2.begin());
// The elements of vec2 will be {1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4};
// vec2 will contain {1, 3, 6, 10};

As with std::accumulate, the calculation must be done in a fixed order

`std::inclusive_scan()`

Works the same way as std::partial_sum

std::inclusive_scan(vec.begin(), vec.end(), vec2.begin());
// The elements of vec2 will be {1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4};
// vec2 will contain {1, 3, 6, 10};

We can optionally add an execution policy

// Request parallel execution
std::inclusive_scan(se::par, vec.begin(), vec.end(), vec2.begin());

`std::exclusive_scan()`

Similar but excludes the current element
Takes an extra argument
Uses it instead of the current element

std::vector<int> vec{1, 2, 3, 4};
std::vector<int> vec2(vec.size());

std::exclusive_scan(vec.begin(), vec.end(), vec2.begin(), -1);
// The elements of vec2 will be {-1, 1 + (-1), 1 + 2 + (-1), 1 + 2 + 3 + (-1)}
// vec2 will contain {-1, 0, 2, 5};

This produces the same result as

std::vector<int> vec{-1, 1, 2, 3};
std::inclusive_scan(vec.begin(), vec.end(), vec2.begin());

`std::transform()`

Takes an iterator range and a callable object
Applies the callable object to every element in the range
Stores the result in a destination
Similar to "map" in functional languages

// Double each element of vec and store the results in vec2
std::transform(vec.begin(), vec.end(),
              back_inserter(vec2), [](int n) { return 2 * n; });

Binary overload of `std::transform()`

std::transform can take an extra argument
- This represents a second source
- The function object is now a binary operator
- Applied to corresponding pairs of elements from each source
- The result is stored in the destination

// Add each element in vec to the corresponding element in vec2
// Store the result in vec3
std::transform(vec.begin(), vec.end(), vec2.begin(), std::back_inserter(vec3),
  [](int n1, int n1) { return n1 + n2; } );

Transform and Reduce Pattern

A very common pattern in parallel programming
Also known as "map and reduce"
- Divide the data into subsets
- Start a thread for each subset
- Each thread calls transform()
- transform() performs some operation on the thread's subset
- Call reduce() to combine each thread's results into the final answer
Naive approach:
- Start up some threads which call transform()
- Call reduce()
Using separate algorithm calls slows things down
- Each transform() thread has to store its result
- reduce() cannot start until all the transform() threads have finished
- reduce() has to read the results from the transform() threads
- reduce() may start up its own threads

`std::transform_reduce()`

Combines the two functions
- Avoids the overhead of separate transform() and reduce() calls
Is a re-implementation of std::inner_product()
- Support for execution policies

Debugging Grimoire