为什么 C++ 标准中没有平行的“std::accumulate”?

Why is there no parallel `std::accumulate` in the C++ standard?

提问人:Anton Rydahl 提问时间:9/6/2023 最后编辑:genpfaultAnton Rydahl 更新时间:9/9/2023 访问量:3510

问:

我认为 C++ 标准中没有 std::accumulate 的并行版本令人困惑。在我看来,并行实现它是微不足道的,例如,基于 OpenMP 或 SIMD 指令。有没有人很好地解释为什么标准委员会选择引入并行版本而不是?是因为迭代器类型不同吗?std::reducestd::accumulate

C++ 并行处理 17 C+ +-标准库 累积

评论

7赞 Dave S 9/6/2023
你想要的是.查看 en.cppreference.com/w/cpp/algorithm/reducestd::reduce
8赞 user4581301 9/6/2023
这里很难问的问题。很多时候,“为什么标准库中没有X?”的答案是不令人满意的,“因为没有人写过一个有令人信服的理由来包含X的提案。
0赞 康桓瑋 9/6/2023
也许是 stackoverflow.com/questions/71093773/ 的傻瓜......
9赞 Peter 9/6/2023
@ThomasMatthews 没有。原因(如下面 Nicol Bolas 的回答所述)是并行性要求操作顺序无关紧要(例如,访问范围元素的顺序,并应用二进制操作),并且需要固定的顺序。如果二进制运算是可交换的,则并行化不会改变最终结果,只会改变达到结果的方式。如果实现不支持并行化,则所有并行化策略通常不会产生净效应,并且算法将按顺序运行。std::accumulate()
2赞 ojs 9/6/2023
FWIV,编译器可以并且确实将 SIMD 并行化应用于累积函数允许的情况。std::accumulate

答:

66赞 Nicol Bolas 9/6/2023 #1

他们引入了,因为不能像它所写的那样并行化。reduceaccumulate

C++ 标准定义了各种函数的预期行为。 定义如下:accumulate

通过使用初始值初始化累加器来计算其结果,然后使用 或 为 迭代器按顺序排列。accinitacc = std::move(acc) + *iacc = binary_op(std::move(acc), *i)i[first, last)

强调是后加的。这两个词使算法变得不可比拟。而且由于这些词是标准的一部分,因此允许用户依赖“按顺序”保证。它们可以进行或非关联操作,这些操作依赖于操作的顺序。因此,委员会不能在不破坏一堆代码的情况下删除这些单词。accumulateoperator+binary_op

而且他们不希望有一个与非并行版本行为根本不同的并行版本。因此,在没有“按顺序”保证的情况下引入(以及有助于使其可并行化的其他语言)。accumulatereduce

评论

7赞 10762409 9/7/2023
值得注意的是,即使它是非交换的,只要是关联的,就可以编写 std::accumulate 的并行版本,例如,如果正在做矩阵乘法。binary_opbinary_opbinary_op
4赞 Peter Cordes 9/7/2023
不可并行化,除非在假设规则的限制范围内。例如,编译器仍然可以对 的数组进行自动矢量化,因为它是真正关联的,这与 FP 加法不同。如果 GCC 预计它会盈利,它甚至可以并行化它(gcc.gnu.org/wiki/AutoParInGCC)。因此,它的真正好处是将 FP 数组或 FP 点积相加。并且要使线程级并行性明确用于实际的编译器/优化器,而不是像 SIMD 并行性那样必须发明的东西。std::accumulateuint32_t-ftree-parallelize-loops=4std::reduce