为什么在N个线程上N次独立计算不快N倍？

Question

我有一个N核处理器(在我的情况下为4).为什么在N个线程上N完全独立的函数调用大约快N倍(当然创建线程有开销,但是进一步阅读)？

查看以下代码:

namespace ch = std::chrono;
namespace mp = boost::multiprecision;
constexpr static unsigned long long int num = 3555;

// mp_factorial uses boost/multiprecision/cpp_int, so I get legit results

    ch::steady_clock::time_point s1 = ch::steady_clock::now();
    auto fu1 = std::async(std::launch::async, mp_factorial, num);
    auto fu2 = std::async(std::launch::async, mp_factorial, num);
    auto fu3 = std::async(std::launch::async, mp_factorial, num);
    auto fu4 = std::async(std::launch::async, mp_factorial, num);
    fu1.get(); fu2.get(); fu3.get(); fu4.get();
    ch::steady_clock::time_point e1 = ch::steady_clock::now();

    ch::steady_clock::time_point s2 = ch::steady_clock::now();
    mp_factorial(num);
    mp_factorial(num);
    mp_factorial(num);
    mp_factorial(num);
    ch::steady_clock::time_point e2 = ch::steady_clock::now();

    auto t1 = ch::duration_cast<ch::microseconds>(e1 - s1).count();
    auto t2 = ch::duration_cast<ch::microseconds>(e2 - s2).count();

    cout << t1 << " " << t2 << endl;

我得到的结果如下:

11756 20317

这大约快2倍.我也试过很多数字,比如num = 355555.我得到了非常相似的结果:

177462588 346575062

为什么会这样？我完全了解Amdahl的定律,并且多核处理器并不总是number_of_cores快一点,但是当我有独立的操作时,我期望得到更好的结果.至少接近一些东西number_of_cores.

---

更新:

如您所见,所有线程都按预期工作,因此这不是问题:

Answer 1

这里的问题是你肯定有一些大块的数字,它们不适合处理器的L1和L2缓存,这意味着当内存控制器跳到整个地方时,处理器就会坐在它的小ALU手指上.为每个处理器读取一点内存.

当你在一个线程中运行时,那个线程至少在很大程度上只能在三个不同的内存区域上工作(a = b * c读取b和c写入a).

当你做4个线程时,你有四个不同的a = b * c;,每个有三个不同的数据流,导致更多的缓存,内存控制器和"打开页面"[这里的页面是一个DRAM术语,与MMU页面无关,但你也可能发现TLB未命中也是一个因素.

因此,由于每个线程消耗和生成大量数据,因此运行更多线程可以获得更好的性能,但不是4倍,内存接口是瓶颈.除了让机器具有更高效的存储器接口[并且可能不那么容易]之外,你无能为力 - 只要接受对于这种特殊情况,存储器就是计算的限制因素.

使用多线程求解的理想示例是那些需要大量计算但不会占用太多内存的示例.我有一个简单的素数计算器和一个计算"怪异数字"的计算器,当在N核上运行时,两者都能提供几乎完全Nx的性能提升[但我会开始使用这些数字比64位大很多倍,它会停止给予同样的好处]

编辑:还有可能:

• 你的代码调用的一些函数是锁定/阻塞其他线程[可能以忙等待方式,如果实现期望短等待时间,因为调用操作系统等待几十个时钟周期是没有意义的] - 像new和malloc和他们的自由对手的事情是合理的候选人.
• 错误共享 - 数据在CPU核心之间共享,导致缓存内容在处理器之间来回发送.从每个线程访问[和更新]的特别小的共享阵列可能导致这种情况出错,即使更新是通过无锁和原子操作完成的.

当你有这样的东西时,使用术语"假"共享

 // Some global array. 
 int array[MAX_THREADS];
 ....
 // some function that updates the global array
 int my_id = thread_id();
 array[my_id]++;

虽然每个线程都有自己的数组条目,但同一个缓存行从一个CPU反弹到另一个CPU.我曾经有一个SMP(在多核之前)dhrystone基准测试,当在2个处理器上运行时,其运行性能是一个处理器的0.7倍 - 因为其中一个常用的数据项存储为int array[MAX_THREADS].这当然是一个相当极端的例子......