c - OpenMP 令人尴尬的并行循环，没有加速

Question

我有一个看似非常简单的并行 for 循环，它只是将零写入整数数组。但事实证明线程越多，循环越慢。我认为这是由于某些缓存抖动造成的，所以我研究了调度、 block 大小、__restrict__、将并行 for 嵌套在并行 block 中，然后刷新。然后我注意到读取数组进行归约也比较慢。

这显然应该非常简单，并且应该接近线性加速。我在这里缺少什么？

完整代码:

#include <omp.h>
#include <vector>
#include <iostream>
#include <ctime>

void tic(), toc();

int main(int argc, const char *argv[])
{
    const int COUNT = 100;
    const size_t sz = 250000 * 200;
    std::vector<int> vec(sz, 1);

    std::cout << "max threads: " << omp_get_max_threads()<< std::endl;

    std::cout << "serial reduction" << std::endl;
    tic();
    for(int c = 0; c < COUNT; ++ c) {
        double sum = 0;
        for(size_t i = 0; i < sz; ++ i)
            sum += vec[i];
    }
    toc();

    int *const ptr = vec.data();
    const int sz_i = int(sz); // some OpenMP implementations only allow parallel for with int

    std::cout << "parallel reduction" << std::endl;
    tic();
    for(int c = 0; c < COUNT; ++ c) {
        double sum = 0;
        #pragma omp parallel for default(none) reduction(+:sum)
        for(int i = 0; i < sz_i; ++ i)
            sum += ptr[i];
    }
    toc();

    std::cout << "serial memset" << std::endl;
    tic();
    for(int c = 0; c < COUNT; ++ c) {
        for(size_t i = 0; i < sz; ++ i)
            vec[i] = 0;
    }
    toc();

    std::cout << "parallel memset" << std::endl;
    tic();
    for(int c = 0; c < COUNT; ++ c) {
        #pragma omp parallel for default(none)
        for(int i = 0; i < sz_i; ++ i)
            ptr[i] = 0;
    }
    toc();

    return 0;
}

static clock_t ClockCounter;

void tic()
{
    ClockCounter = std::clock();
}

void toc()
{
    ClockCounter = std::clock() - ClockCounter;
    std::cout << "\telapsed clock ticks: " << ClockCounter << std::endl;
}

运行这个会产生:

g++ omp_test.cpp -o omp_test --ansi -pedantic -fopenmp -O1
./omp_test
max threads: 12
serial reduction
  elapsed clock ticks: 1790000
parallel reduction
  elapsed clock ticks: 19690000
serial memset
  elapsed clock ticks: 3860000
parallel memset
  elapsed clock ticks: 20800000

如果我使用 -O2 运行，g++ 能够优化串行减少并且我得到零时间，因此 -O1。此外，放置 omp_set_num_threads(1); 使时间更加相似，尽管仍然存在一些差异:

g++ omp_test.cpp -o omp_test --ansi -pedantic -fopenmp -O1
./omp_test
max threads: 1
serial reduction
  elapsed clock ticks: 1770000
parallel reduction
  elapsed clock ticks: 7370000
serial memset
  elapsed clock ticks: 2290000
parallel memset
  elapsed clock ticks: 3550000

这应该是相当明显的，我觉得我没有看到非常基本的东西。我的 CPU 是具有超线程的 Intel(R) Xeon(R) CPU E5-2640 0 @ 2.50GHz，但在具有 4 个内核且没有超线程的同事的 i5 上观察到相同的行为。我们都在运行 Linux。

编辑

似乎有一个错误是在时间方面，运行时:

static double ClockCounter;

void tic()
{
    ClockCounter = omp_get_wtime();//std::clock();
}

void toc()
{
    ClockCounter = omp_get_wtime()/*std::clock()*/ - ClockCounter;
    std::cout << "\telapsed clock ticks: " << ClockCounter << std::endl;
}

产生更多“合理”时间:

g++ omp_test.cpp -o omp_test --ansi -pedantic -fopenmp -O1
./omp_test
max threads: 12
serial reduction
  elapsed clock ticks: 1.80974
parallel reduction
  elapsed clock ticks: 2.07367
serial memset
  elapsed clock ticks: 2.37713
parallel memset
  elapsed clock ticks: 2.23609

但是，仍然没有加速，只是不再慢了。

EDIT2:

正如 user8046 所建议的，代码受内存限制很大。正如 Z boson 所建议的那样，串行代码很容易被优化掉，并且不确定这里测量的是什么。所以我做了一个小改动，将求和放在循环之外，这样它就不会在 c 的每次迭代中都归零。我还用 sum+=F(vec[i]) 替换了归约操作，用 vec[i] = F(i) 替换了 memset 操作。运行为:

g++ omp_test.cpp -o omp_test --ansi -pedantic -fopenmp -O1 -D"F(x)=sqrt(double(x))"
./omp_test
max threads: 12
serial reduction
  elapsed clock ticks: 23.9106
parallel reduction
  elapsed clock ticks: 3.35519
serial memset
  elapsed clock ticks: 43.7344
parallel memset
  elapsed clock ticks: 6.50351

计算平方根给线程增加了更多工作，最终有一些合理的加速(大约 7x，这是有道理的，因为超线程内核共享内存 channel )。

Answer 1

您发现了时间错误。仍然没有加速，因为您的两个测试用例都受内存限制。在典型的消费类硬件上，所有内核共享一条内存总线，因此使用更多线程不会给您带来更多带宽，而且，因为这是瓶颈，加速。如果您减小问题大小使其适合缓存，或者确定增加每个数据的计算次数，这可能会改变，例如，如果您正在计算 exp(vec[i]) 或 1/vec[ 的减少一世]。对于 memset:你可以用一个线程使内存饱和，你永远不会在那里看到加速。 (只有当您可以访问具有更多线程的第二个内存总线时，就像某些多插槽架构一样)。 关于减少的一个评论，这很可能不是用锁实现的，那将是非常低效的，但是使用一个没有那么糟糕的对数加速的加法树。