c++ - [inclusive/exclusive]_scan in parallel 提案 N3554 的算法

Question

提案 N3554 (A Parallel Algorithms Library)对于 C++14，建议(除其他事项外)似乎是当前 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 Sumsand Their Applications" by Guy E. Blelloch非常有用。

Answer 1

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