多线程向量和的可伸缩性

Question

这是一个用于多线程向量和的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双精度矢量.

这是一个图表,显示计算时间作为线程数的函数(求和10⁷值的平均时间,在没有其他运行的8核计算机上 - 我尝试在32核计算机上,行为非常相似).

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

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

Answer 1

accumulateCPU 运算单元的利用率较低，但缓存和内存吞吐量很可能是瓶颈，特别是对于 10^7 double，或 1000 万个 double = 80MB 数据，这远远超过了 CPU 缓存大小。

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