OpenMP并行for循环远慢于串行代码，求问题排查与优化方案

我尝试用OpenMP并行化一段代码，结果启用OpenMP后程序完成耗时达到串行版本的25倍。请问问题出在哪里？该如何优化？

#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 CPU（主频2.593GHz）

初始测试结果 #

• 串行代码平均运行时间：7.4秒
• 并行代码（8线程）平均运行时间：180秒
• O1、O2、O3优化级别下性能表现相近
• 改用mt19937随机数生成器可显著缩小性能差距，但并行版本仍远慢于串行版本
• 调整迭代次数n的取值后，性能差异趋势一致

更新测试结果 #

尝试了数组法和firstprivate法两种优化方案，二者效果相当，均实现了有效并行；暂未验证firstprivate方案中各线程的随机序列是否一致。相关代码如下：

void array_approach(unsigned long long n, const int nThreads) {
        int tmp = 0;
        std::random_device rd;  // Will be used to obtain a seed for the random number engine
        vector<std::mt19937> rngs;
        for (int i=0; i<nThreads*64; i++) rngs.push_back(std::mt19937(rd())); // Standard mersenne_twister_engine seeded with rd()
        std::uniform_int_distribution<> distrib(1, 6);
        auto tStart = std::chrono::steady_clock::now();
#pragma omp parallel for schedule(static) reduction(+:tmp) num_threads(nThreads)
        for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(rngs[omp_get_thread_num()*64])))%static_cast<int>(1e9);
        tmp%=static_cast<int>(1e9);
        auto tEnd = std::chrono::steady_clock::now();
        cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
}

void private_approach(unsigned long long n, const int nThreads) {
        int tmp = 0;
        std::random_device rd;  // Will be used to obtain a seed for the random number engine
        std::mt19937 rng(rd());
        std::uniform_int_distribution<> distrib(1, 6);
        auto tStart = std::chrono::steady_clock::now();
#pragma omp parallel for schedule(static) reduction(+:tmp) firstprivate(rng) num_threads(nThreads)
        for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(rng)))%static_cast<int>(1e9);
        tmp%=static_cast<int>(1e9);
        auto tEnd = std::chrono::steady_clock::now();
        cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
}

内容的提问来源于stack exchange，提问作者cat