并行计算大向量的总和

Question

问题背景

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

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

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

升压.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%。

顺序求和：
耗时：46 ms
5000000050000000
--------------------------------
并行求和：
耗时：21 ms
5000000050000000

然而，100,000,000 个元素的绝对增益仅为边际（25 毫秒）。尽管如此，当累积不同的元素类型时，性能增益可能会比int.

开放MP

正如@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;
}

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

顺序求和：
耗时：46 ms
5000000050000000
--------------------------------
并行求和：
耗时：21 ms
求和：5000000050000000
--------------------------------
OpenMP总和：
花费的时间：21毫秒
总和：5000000050000000