Parallel Primitives

Usage: #include "parallel.h"

parallel fork

`parallel_do`	Work	Span
`auto parallel_do( auto&& L, // a function auto&& R // a function )`	$O(\mathcal{W}(L) + \mathcal{W}(R))$	$O(\max(\mathcal{S}(L), \mathcal{S}(R)))$

parallel_do runs two functions in parallel and returns their results as a pair. Both functions must return a value (i.e., neither may return void).

For example, parallel_do is useful for implementing manual divide-and-conquer algorithms. Here is an implementation of a divide-and-conquer summation for a sequence of numbers

auto parallel_sum(const sequence auto& S) {
  if (S.size() == 0) return 0;
  else if (S.size() == 1) return S[0];
  auto [L, R] = par::split_mid(S);
  auto [Lsum, Rsum] = par::parallel_do(
    [&]() { return parallel_sum(L); },
    [&]() { return parallel_sum(R); }
  );
  return Lsum + Rsum;
}

parallel loop

`parallel_for`	Work	Span
`void parallel_for( size_t start, // first index, inclusive size_t end, // last index, exclusive auto&& f // the loop body, taking an index )`	$\displaystyle\sum_{i=start}^{end-1} \mathcal{W}(f(i))$	$\displaystyle\max_{i=start}^{end-1} \mathcal{S}(f(i))$

parallel_for applies f to every index in the half-open range [start, end), in parallel. Unlike parallel_do, it does not collect results: f is run for its effects and anything it returns is discarded.

par::array_sequence<int> S(n);

par::parallel_for(0, S.size(), [&](int i) {
  S[i] = i * i;       // S becomes [0, 1, 4, 9, ...]
});

The loop body runs in parallel, so it must be safe to run every index at once. Writing to a distinct index per iteration, as above, is fine. Two iterations writing the same location, or one writing what another reads, is a data race, which is undefined.

Prefer the sequence operations wherever they fit. The example above is par::tabulate(n, [](int i) { return i * i; }), which says the same thing without mutation. When you want to run something for its effect rather than build a value, for_each and apply_each do that over a sequence directly.

Between them these cover very nearly everything: no lab in this course needs parallel_for. Reach for it only when what you are doing genuinely is a loop over a range of indices rather than anything to do with an existing sequence, and if you find yourself reaching for it often, there is probably a sequence operation that fits better.