并行计算一个大向量的和

  • Z时代
  • 2024-01-10
  • 分类：问答

回答：

我有一个程序，目前花太长时间才能使用来汇总std::vector约1亿个元素std::accumulate，这是一个瓶颈。

我希望它更快，并且希望它是一个异步计算，因此GUI / Server不会阻塞。计算也应该使用 多线程， 这样我可以减少求和向量的时间。

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

回答：

我想知道如何在 做到这一点？我的程序理想上需要重用线程（例如 线程组 ），不确定如何存储和检索部分和，最后检索部分和。

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

如果有人展示了一些有关如何解决此问题的基本代码，那就太好了。

回答：

回答：

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**](http://coliru.stacked-crooked.com/a/4807261d61b7a726)

（并行版本的性能与Coliru上的顺序版本大致相同，可能只有1个内核可用）

回答：

在我的机器上（使用8个线程），并行版本平均提高了约120％的性能。

顺序求和：

花费时间：46毫秒

5000000050000000

--------------------------------

并行和：

花费时间：21毫秒

5000000050000000

但是，100,000,000个元素的绝对增益仅为边际（25 ms）。虽然，当累积不同类型的元素时，性能提升可能会大于int。

回答：

正如@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毫秒

5000000050000000

--------------------------------

并行求和：

花费时间：21毫秒

求和：5000000050000000

--------------------------------

OpenMP总和：

花费时间：21毫秒

总和：5000000050000000

以上是 并行计算一个大向量的和 的全部内容， 来源链接： utcz.com/qa/416870.html

回到顶部