OpenMP for 循环比串行代码花费更多时间

Question

我尝试使用 OpenMP 并行化代码片段，结果发现使用 OpenMP 需要 25X 时间才能完成程序。有什么不对的吗？我该如何优化它？

#include <iostream>
#include <cmath>
#include <random>
#include <chrono>
#include <cstdlib>
#include <omp.h>

using namespace std;

int main() {
        unsigned long long black_square = 1, digit_square = 13;
        //auto n = ((black_square)<<11) * static_cast<unsigned long long>(pow(digit_square,10));
        auto n = static_cast<unsigned long long>(1e9);
        srand(0);
        int tmp = 0;
        std::random_device rd;  // Will be used to obtain a seed for the random number engine
        std::mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()
        std::uniform_int_distribution<> distrib(1, 6);

        auto tStart = std::chrono::high_resolution_clock::now();
//#pragma omp parallel for schedule(static) reduction(+:tmp)
#pragma omp parallel for schedule(static) reduction(+:tmp) num_threads(8)
        for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==rand()%6))%static_cast<int>(1e9);
        //for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(gen)))%static_cast<int>(1e9);
        tmp%=static_cast<int>(1e9);
        auto tEnd = std::chrono::high_resolution_clock::now();

        cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
        return 0;
}

代码由

g++ -o a.out -O3 -std=c++11 -fopenmp tmp.cpp

编译，其中

g++

的版本为

8.5.0 20210514

。操作系统是RHEL8.9，有20个

Intel Xeon CPUs at 2.593GHz

。

串行代码平均运行时间为7.4s，而并行代码平均运行时间为180s。选项

-O3

、

-O2

、

-O1

具有相似的结果。随机生成器

mt19937

可以显着缩小性能差距，但并行代码仍然比串行版本慢得多。增加或减少

n

也会导致类似的结果。

Answer 1

rand()

函数不需要是线程安全的。因此，像您所做的那样同时从多个线程调用它是不安全的

glibc 的

rand()

版本是线程安全的，但它是通过将整个函数包装在互斥体中来实现的。因此一次只有一个线程可以调用

rand()

。由于在 rand 调用之外，您的代码执行的操作非常少，几乎所有执行时间都将在

rand()

内。

所以并行版本并不是真正的并行。每次调用 rand() 时，每个线程轮流一次执行一个。所以它比单线程没有优势。但实际上更糟糕的是，因为线程必须争夺谁获得互斥锁，在每次调用后唤醒和睡眠，并在每个 CPU 核心的缓存之间移动 PRNG 状态。所以比单线程差很多。

您应该做的是创建多个 PRNG 实例。有一个

gen

对象数组，每个线程一个。每个线程应该使用自己的 PRNG。确保每个对象在内存中相距足够远，不会共享缓存行，因此 PRNG 状态不需要在 CPU 缓存之间移动。