普通并发代码的吞吐量不会随着线程数的增加而增加

Question

我正在尝试使用 OpenMP 来对我实现的数据结构的速度进行基准测试。但是，我似乎犯了一个根本性错误：无论我尝试对什么操作进行基准测试，吞吐量都会随着线程数的增加而减少而不是增加。下面你可以看到尝试对 for 循环的速度进行基准测试的代码，因此我希望它可以（某种程度上）与线程数量成线性比例，但它不会（在有和没有的双核笔记本电脑上编译 -带有 c++11 的 g++ 上的 O3 标志）。

#include <omp.h>
#include <atomic>
#include <chrono>
#include <iostream>

thread_local const int OPS = 10000;
thread_local const int TIMES = 200;

double get_tp(int THREADS)
{
    double threadtime[THREADS] = {0};

    //Repeat the test many times
    for(int iteration = 0; iteration < TIMES; iteration++)
    {
        #pragma  omp  parallel num_threads(THREADS)
        {
            double start, stop;
            int loc_ops = OPS/float(THREADS);
            int t = omp_get_thread_num();

            //Force all threads to start at the same time
            #pragma  omp  barrier
            start = omp_get_wtime();


            //Do a certain kind of operations loc_ops times
            for(int i = 0; i < loc_ops; i++)
            {
                //Here I would put the operations to benchmark
                //in this case a boring for loop
                int x = 0;
                for(int j = 0; j < 1000; j++)
                    x++;
            }

        stop = omp_get_wtime();
        threadtime[t] += stop-start;
        }
    }

    double total_time = 0;
    std::cout << "\nThread times: ";
    for(int i = 0; i < THREADS; i++)
    {
        total_time += threadtime[i];
        std::cout << threadtime[i] << ", ";
    }
    std::cout << "\nTotal time: " << total_time << "\n";
    double mopss = float(OPS)*TIMES/total_time;
    return mopss;
}

int main()
{
    std::cout << "\n1  " << get_tp(1) << "ops/s\n";
    std::cout << "\n2  " << get_tp(2) << "ops/s\n";
    std::cout << "\n4  " << get_tp(4) << "ops/s\n";
    std::cout << "\n8  " << get_tp(8) << "ops/s\n";
}

在双核上使用 -O3 输出，所以我们不希望吞吐量在 2 个线程后增加，但是当从 1 个线程到 2 个线程时吞吐量甚至没有增加，它减少了 50%：

1 Thread 
Thread times: 7.411e-06, 
Total time: 7.411e-06
2.69869e+11 ops/s

2 Threads 
Thread times: 7.36701e-06, 7.38301e-06, 
Total time: 1.475e-05
1.35593e+11ops/s

4 Threads 
Thread times: 7.44301e-06, 8.31901e-06, 8.34001e-06, 7.498e-06, 
Total time: 3.16e-05
6.32911e+10ops/s

8 Threads 
Thread times: 7.885e-06, 8.18899e-06, 9.001e-06, 7.838e-06, 7.75799e-06, 7.783e-06, 8.349e-06, 8.855e-06, 
Total time: 6.5658e-05
3.04609e+10ops/s

为了确保编译器不会删除循环，我还尝试在测量时间后输出 "x"，据我所知问题仍然存在。我还在具有更多内核的机器上尝试了代码，它的行为非常相似。如果没有 -O3，吞吐量也不会扩展。所以我的基准测试方式显然有问题。我希望你能帮助我。

Answer 1

循环几乎肯定仍在优化，即使您在外循环之后输出 x 的值。编译器可以用一条指令简单地替换整个循环，因为循环边界在编译时是常量。事实上，在 this example:

#include <iostream>

int main()
{
    int x = 0;
    for (int i = 0; i < 10000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            ++x;
        }
    }

    std::cout << x << '\n';
    return 0;
}

循环替换为单个汇编指令mov esi, 10000000。

始终在进行基准测试时检查程序集输出，以确保您衡量的是您认为的自己；在这种情况下，您只是在测量创建线程的开销，当然创建的线程越多开销就越大。

考虑让最内层的循环做一些无法优化的事情。随机数生成是一个很好的候选者，因为它应该在恒定时间内执行，并且它具有置换 PRNG 状态的副作用（使其没有资格被完全删除，除非事先知道种子 and 编译器能够解开 PRNG 中的所有突变）。

For example:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 r;
    std::uniform_real_distribution<double> dist{0, 1};

    for (int i = 0; i < 10000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            dist(r);
        }
    }

    return 0;
}

两个循环和 PRNG 调用在这里都保持原样。

Answer 2

我不确定您为什么将性能定义为每总CPU时间的操作总数，然后对数字的递减函数感到惊讶线程。这种情况几乎总是普遍存在，除非缓存效应开始发挥作用。真正的性能指标是每个挂钟时间操作数.

用简单的数学推理很容易证明。给定总工作量 W 和每个内核的处理能力 P，单个内核的时间为 T_1 = W / P。在 n 个核心之间平均分配工作意味着每个核心都为 T_1,n = (W / n + H) / P 工作，其中 H 是由并行化本身引起的每个线程的开销。这些总和是 T_n = n * T_1,n = W / P + n (H / P) = T_1 + n (H / P)。开销始终是正值，即使在所谓的令人尴尬的并行性 的微不足道的情况下也是如此，在这种情况下，没有两个线程需要通信或同步。例如，启动 OpenMP 线程需要时间。你无法摆脱开销，你只能通过确保每个线程都有很多工作要做来在线程的生命周期内分摊它。因此，T_n > T_1 并且在这两种情况下都具有固定数量的操作，n 核上的性能将始终低于单核。此规则的唯一例外是大小为 W 的工作的数据不适合较低级别的缓存但大小为 W / n 的工作的数据的情况。这导致超过核心数量的巨大加速，称为 超线性加速 。您正在线程函数内部进行测量，因此您忽略了 H 的值，并且 T_n 应该或多或少等于 T_1 在计时器精度内，但是...

多线程运行在多个CPU核心上运行，它们都争夺有限的共享CPU资源，即末级缓存（如果有）、内存带宽和热封套。

当您简单地递增标量变量时，内存带宽不是问题，但当代码开始实际将数据移入和移出 CPU 时，内存带宽就会成为瓶颈。数值计算的一个典型例子是稀疏矩阵向量乘法 (spMVM)——一个经过适当优化的 spMVM 例程，使用 double 非零值和 long 索引占用了如此多的内存带宽，以至于可以每个 CPU 套接字低至两个线程使内存总线完全饱和，在这种情况下，昂贵的 64 核 CPU 是一个非常糟糕的选择。对于所有具有低算术强度（每单位数据量的操作）的算法都是如此。

当谈到热包络时，大多数现代 CPU 都采用动态电源管理，并且会根据内核的活动数量对内核进行超频或降频。因此，虽然 n 个降频内核在每单位时间执行的总工作 多于单个内核，但就 每总 CPU 时间工作，这是您使用的指标。

考虑到所有这些，还有最后一件事（但并非最不重要）要考虑——定时器分辨率和测量噪声。您的运行时间以几微秒为单位。除非你的代码运行运行在一些专门的硬件上，除了运行你的代码什么都不做（即，不与守护进程、内核线程和其他进程共享时间，也没有中断处理），你需要基准测试运行长几个数量级，最好至少持续几秒钟。

普通并发代码的吞吐量不会随着线程数的增加而增加

Throughput of trivially concurrent code does not increase with the number of threads

c++

concurrency

multithreading

openmp

microbenchmark