[inclusive/exclusive]_并行扫描的算法 <algorithm> 提案 N3554

Question

提案N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum，例如：

template<
    class ExecutionPolicy,
    class InputIterator,
    class OutputIterator,
    class BinaryOperation>
OutputIterator inclusive_scan(
    ExecutionPolicy &&exec,
    InputIterator first,
    InputIterator last,
    OutputIterator result,
    BinaryOperation binary_op);

有说明

Effects: For each iterator i in [result,result + (last - first)), performs *i = prefix_sum, where prefix_sum is the result of the corresponding sum init + *iter_0 + *iter_1 + *iter_2 + ... or binary_op(init, binary_op(*iter_0, binary_op(*iter_1, binary_op(*iter_2, ...))) for every iterator iter_j in the range [first,first + (i - result) - 1) ... The order of operands of the sum is unspecified.

---

如何使此操作并行化？似乎，几乎根据定义，必须计算每个输出 prefix_sum 才能立即计算下一个 - 本质上导致串行操作。

---

编辑 非常感谢 Aasmund Eldhuset 的回答。就个人而言，我发现 "Prefix Sums 及其应用”，作者 Guy E. Blelloch 非常有用。

Answer 1

Parallel prefix sum 是一种经典的分布式编程算法，它优雅地使用归约，然后进行分布（如文章中所示）。关键的观察是，您可以在知道前导项之前计算部分和的 部分 。