使用 std::exclusive_scan 和执行策略 std::execution::par 计算前缀积

Question

我正在计算 prefix product with std::exclusive_scan

#include <algorithm>/
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> input{1,2,3,4,5,6,7,8,9};
    std::exclusive_scan(std::begin(input), std::end(input),
                        std::begin(input),
                        1, std::multiplies<> {});

    std::cout << "exclusive_scan: "
    for (auto const product : input) {
        std::cout << product << " ";
    }
    std::cout << '\n';
    return 0;
}

输出符合预期exclusive_scan: 1 1 2 6 24 120 720 5040 40320。

现在我想将它与 std::execution::par 并行化并更改代码：

#include <algorithm>
#include <execution>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> input{1,2,3,4,5,6,7,8,9};
    std::exclusive_scan(std::execution::par,
                        std::begin(input), std::end(input),
                        std::begin(input),
                        1, std::multiplies<> {});

    std::cout << "exclusive_scan: "
    for (auto const product : input) {
        std::cout << product << " ";
    }
    std::cout << '\n';
    return 0;
}

但现在输出是 exclusive_scan: 1 1 1 1 1 1 1 1 1

我正在使用 gcc 10.2.0 并链接到 -ltbb。

为什么我不能将 std::exclusive_scan 与 std::execution::par 一起使用？
我的实现方式有问题吗？
需要进行哪些更改？

Answer 1

当您将 exclusive_scan 与默认执行策略一起使用时，如：

exclusive_scan(input.begin(), input.end(), output.begin(), initial_value, operate)

发生的事情是：

initial_value_temp = operate(input[0], initial_value);
output[0] = initial_value;
initial_value = initial_value_temp

initial_value_temp = operate(input[1], initial_value);
output[1] = initial_value;
initial_value = initial_value_temp

     ⋮

initial_value_temp = operate(input[last], initial_value);
output[last] = initial_value;
initial_value = initial_value_temp

然而，当您尝试对其应用 execution::par 时，出于某种原因，可能是为了更好的并行化，它的工作方式如下：

output[0] = initial_value;
initial_value = operate(input[0], initial_value);

output[1] = initial_value;
initial_value = operate(input[1], initial_value);

     ⋮

output[last] = initial_value;
initial_value = operate(input[last], initial_value);

如果 input 和 output 不同，它们应该完全相同。但是，当它们相同时，流程就会中断，而这正是您想要做的。

要修复它，最简单的方法是创建一个输出容器：

std::vector<int> input{1,2,3,4,5,6,7,8,9};

std::vector<int> output;
output.reserve(input.size());

std::exclusive_scan(std::execution::par, 
                    std::begin(input), 
                    std::end(input), 
                    std::back_inserter(output),
                    1, std::multiplies{});

注意 execution::par 实际上会尝试将整个任务分配到不同的线程中，然后再将它们合并。有很多关于它应该如何工作的文章。但是，这里的要点是您试图在生成输出的同时编辑输入。而且只有 9 个数字，它从来没有为我创建任何并行线程（创建一个可能会慢得多）。

使用 std::exclusive_scan 和执行策略 std::execution::par 计算前缀积

Calculate prefix product with std::exclusive_scan and execution policy std::execution::par

c++

stl

c++17

tbb