c++ - 并行计算大 vector 的总和

Question

问题背景

我有一个程序目前需要很长时间才能使用 std::accumulate 总结大约 1 亿个元素的大型 std::vector，这是一个瓶颈。

我希望它更快，我希望它是一个异步计算，这样 GUI/服务器就不会阻塞。计算还应该使用多线程，这样我就可以减少对 vector 求和所需的时间。

我想拆分求和，让每个线程对 vector 的一部分求和，然后在计算所有部分和时，应将每个线程的部分和加在一起以获得总和。

Boost.Asio?

我想知道如何在 Boost.Asio 中解决这个问题？我的程序理想情况下需要重用线程(如线程组)，不确定如何存储和检索部分和以及最终检索部分和的总和。

我正在考虑创建一个调用 boost::asio::io_service::run 的线程组，传递一个处理程序来计算部分和，但我不确定如何传递部分总和到另一个处理程序并将所有部分总和加在一起。

如果有人能展示我如何处理这个的一些框架代码，那就太好了。

Answer 1

Boost.Asio 适合这个问题吗？

Boost.Asio 的主要目的是为网络 和I/O 编程 提供一个异步模型，而你描述的问题似乎没有太大意义处理网络和 I/O。

我认为最简单的解决方案是使用 Boost 或 C++ 标准库提供的线程原语。

并行算法

这是一个仅使用标准库创建的 accumulate 并行版本的示例。

/* Minimum number of elements for multithreaded algorithm.
   Less than this and the algorithm is executed on single thread. */
static const int MT_MIN_SIZE = 10000;

template <typename InputIt, typename T>
auto parallel_accumulate(InputIt first, InputIt last, T init) {
    // Determine total size.
    const auto size = std::distance(first, last);
    // Determine how many parts the work shall be split into.
    const auto parts = (size < MT_MIN_SIZE)? 1 : std::thread::hardware_concurrency();

    std::vector<std::future<T>> futures;

    // For each part, calculate size and run accumulate on a separate thread.
    for (std::size_t i = 0; i != parts; ++i) {
        const auto part_size = (size * i + size) / parts - (size * i) / parts;
        futures.emplace_back(std::async(std::launch::async,
            [=] { return std::accumulate(first, std::next(first, part_size), T{}); }));
        std::advance(first, part_size);
    }

    // Wait for all threads to finish execution and accumulate results.
    return std::accumulate(std::begin(futures), std::end(futures), init,
        [] (const T prev, auto& future) { return prev + future.get(); });
}

Live example _{(并行版本在 Coliru 上的性能与顺序版本大致相同，可能只有 1 个内核可用)}

时间

在我的机器上(使用 8 个线程)，并行版本的性能平均提高了 ~120%。

Sequential sum:
Time taken: 46 ms
5000000050000000
--------------------------------
Parallel sum:
Time taken: 21 ms
5000000050000000

但是，100,000,000 个元素的绝对增益仅很小(25 毫秒)。虽然，当累积不同的元素类型时，性能增益可能比 int 更大。

OpenMP

正如@sehe 在评论中提到的，值得一提的是，OpenMP 可能会为这个问题提供一个简单的解决方案，例如

template <typename T, typename U>
auto omp_accumulate(const std::vector<T>& v, U init) {
    U sum = init;

    #pragma omp parallel for reduction(+:sum)
    for(std::size_t i = 0; i < v.size(); i++) {
        sum += v[i];
    }

    return sum;
}

在我的机器上，此方法与使用标准线程原语的并行方法执行的相同。

Sequential sum:
Time taken: 46 ms
5000000050000000
--------------------------------
Parallel sum:
Time taken: 21 ms
Sum: 5000000050000000
--------------------------------
OpenMP sum:
Time taken: 21 ms
Sum: 5000000050000000