c++ - 多线程 vector 和的可扩展性

Question

这是一段用于多线程 vector 求和的 C++11 代码。

#include <thread>

template<typename ITER>
void sum_partial(ITER a, ITER b, double & result) {
  result = std::accumulate(a, b, 0.0);
}

template<typename ITER>
double sum(ITER begin, ITER end, unsigned int nb_threads) {
  size_t len = std::distance(begin, end);
  size_t size = len/nb_threads;

  std::vector<std::thread> thr(nb_threads-1);
  std::vector<double> r(nb_threads);
  size_t be = 0;
  for(size_t i = 0; i < nb_threads-1; i++) {
    size_t en = be + size;
    thr[i] = std::thread(sum_partial<ITER>, begin + be, begin + en, std::ref(r[i]));
    be = en;
  }
  sum_partial(begin + be, begin + len, r[nb_threads-1]);
  for(size_t i = 0; i < nb_threads-1; i++)
    thr[i].join();
  return std::accumulate(r.begin(), r.end(), 0.0);
}

典型的用法是 sum(x.begin(), x.end(), n) 和 x 一个 double vector 。

这是一个图表，显示了计算时间作为线程数的函数(求和 10⁷ 值的平均时间，在没有其他任何运行的 8 核计算机上——我在 32 核计算机上试过，行为非常好类似)。

为什么可扩展性这么差？可以改进吗？

我(非常有限)的理解是，要具有良好的可伸缩性，线程应避免写入同一缓存行。这里所有线程都在 r 中写入一次，在它们计算的最后，我不认为它是限制因素。是不是内存带宽问题？

Answer 1

accumulate 对 cpu 运算单元的利用率较低，但缓存和内存吞吐量很可能是瓶颈，特别是对于 10^7 double，或 1000 万 double = 80MB 数据，这是更多比你的 CPU 缓存大小。

---

要克服缓存和内存吞吐量瓶颈，您可能需要 enable prefetch使用 -fprefetch-loop-arrays，甚至手动进行一些组装。