并行算法[包含/独占] _scan并行<算法>提案N3554

Question

用于C++ 14的提议N3554(并行算法库),提出(除其他外),似乎是当前的并行版本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);

随着解释

效果:对于[result,result +(last - first))中的每个迭代器,执行*i = prefix_sum,其中prefix_sum是相应的sum init +*iter_0 +*iter_1 +*iter_2 + ...或binary_op的结果(init,binary_op(*iter_0,binary_op(*iter_1,binary_op(*iter_2,...)))对于范围内的每个迭代器iter_j [first,first +(i - result) - 1)...顺序总和的操作数未指定.

---

如何将此操作并行？看起来,几乎按照定义,每个输出prefix_sum必须计算出下一个要计算的 - 通常导致串行操作.

---

编辑非常感谢Aasmund Eldhuset的回答.就个人而言,我发现Guy E. Blelloch的"前缀和及其应用"非常有用.

Answer 1

并行前缀和是一种经典的分布式编程算法,它优雅地使用缩减后跟分布(如文章所示).关键的观察是,您可以在知道主要条款之前计算部分和的部分.