为什么我通过与 OpenMP 并行化获得的加速在达到一定的工作负载大小后会降低？

Question

我正在尝试使用 OpenMP 并编写了一小段代码来感受一下在加速方面的期望：

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>

void SingleThreaded(std::vector<float> &weights, int size)
{
    auto totalWeight = 0.0f;

    for (int index = 0; index < size; index++)
    {
        totalWeight += weights[index];
    }

    for (int index = 0; index < size; index++)
    {
        weights[index] /= totalWeight;
    }
}

void MultiThreaded(std::vector<float> &weights, int size)
{
    auto totalWeight = 0.0f;

#pragma omp parallel shared(weights, size, totalWeight) default(none)
    {
        // clang-format off
#pragma omp for reduction(+ : totalWeight)
        // clang-format on
        for (int index = 0; index < size; index++)
        {
            totalWeight += weights[index];
        }

#pragma omp for
        for (int index = 0; index < size; index++)
        {
            weights[index] /= totalWeight;
        }
    }
}

float TimeIt(std::function<void(void)> function)
{
    auto startTime = std::chrono::high_resolution_clock::now().time_since_epoch();
    function();
    auto endTime = std::chrono::high_resolution_clock::now().time_since_epoch();
    std::chrono::duration<float> duration = endTime - startTime;

    return duration.count();
}

int main(int argc, char *argv[])
{
    std::vector<float> weights(1 << 24);
    std::srand(std::random_device{}());
    std::generate(weights.begin(), weights.end(), []()
                  { return std::rand() / static_cast<float>(RAND_MAX); });

    for (int size = 1; size <= weights.size(); size <<= 1)
    {
        auto singleThreadedDuration = TimeIt(std::bind(SingleThreaded, std::ref(weights), size));
        auto multiThreadedDuration = TimeIt(std::bind(MultiThreaded, std::ref(weights), size));

        std::cout << "Size: " << size << std::endl;
        std::cout << "Speed up: " << singleThreadedDuration / multiThreadedDuration << std::endl;
    }
}

我在 Win10 上使用 MinGW g++ 编译并运行上面的代码，如下所示：

g++ -O3 -static -fopenmp OpenMP.cpp; ./a.exe

输出（见下文）显示向量大小为 524288 时的最大加速约为 4.2。这意味着多线程代码运行比向量的单线程代码快 4.2 倍大小为 524288.

Size: 1
Speedup: 0.00614035
Size: 2
Speedup: 0.00138696
Size: 4
Speedup: 0.00264201
Size: 8
Speedup: 0.00324149
Size: 16
Speedup: 0.00316957
Size: 32
Speedup: 0.00315457
Size: 64
Speedup: 0.00297177
Size: 128
Speedup: 0.00569801
Size: 256
Speedup: 0.00596125
Size: 512
Speedup: 0.00979021
Size: 1024
Speedup: 0.019943
Size: 2048
Speedup: 0.0317662
Size: 4096
Speedup: 0.181818
Size: 8192
Speedup: 0.133713
Size: 16384
Speedup: 0.216568
Size: 32768
Speedup: 0.566396
Size: 65536
Speedup: 1.10169
Size: 131072
Speedup: 1.99395
Size: 262144
Speedup: 3.4772
Size: 524288
Speedup: 4.20111
Size: 1048576
Speedup: 2.82819
Size: 2097152
Speedup: 3.98878
Size: 4194304
Speedup: 4.00481
Size: 8388608
Speedup: 2.91028
Size: 16777216
Speedup: 3.85507

所以我的问题是：

为什么矢量越小，多线程代码越慢？纯粹是因为创建线程和分配工作的开销，还是我做错了什么？
为什么我得到的加速比在一定大小后会下降？
在我使用的 CPU (i7 7700k) 上，我理论上可以实现的最佳加速是多少？
物理 CPU 内核和逻辑 CPU 内核之间的区别在加速方面是否重要？
我在代码中是否犯了任何明显的错误？我可以改进什么吗？

Answer 1

我同意你的理论；这可能是设置的开销。
虽然你的处理器上的 CPU 个内核有自己的 L1 和 L2 缓存，但它们都共享一个 8M L3 缓存，一旦向量变得太大而无法放入 L3 缓存，就会存在风险的线程相互从缓存中逐出彼此的页面。
我假设“逻辑核心”是指超线程？那些实际上不能并行计算，它们只能在另一个线程运行时“填充”。阻塞等待内存。在高速缓存有效的计算绑定代码中，这可能会大大限制它们的并行性潜力。
我不知道你的编译器在多大程度上对它编译的代码进行了向量化；我将针对完全矢量化的实现（例如，使用良好的 BLAS 实现中的 cblas_sasum 和 cblas_sscal）对您拥有的两个函数进行基准测试。您现在很有可能在 table 上留下很多单线程性能。

为什么我通过与 OpenMP 并行化获得的加速在达到一定的工作负载大小后会降低？

Why does the speedup I get by parallelizing with OpenMP decrease after a certain workload size?

c++

multithreading

openmp