蒙特卡洛与 OpenMP

Question

我正在研究 OpenMP，需要将其实现到蒙特卡罗模拟中，以估计洗牌牌中连续国王的概率。然而，我实现后，所花费的时间仍然没有如图所示减少那么多。我的 OpenMP 代码是否被错误使用，尤其是 100000 和 1000000 次？感谢您的帮助，并提供代码来帮助。

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#include <omp.h>

using namespace std;

vector<string> org_deck = {
    "AS", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "10S", "JS", "QS", "KS",
    "AD", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "10D", "JD", "QD", "KD",
    "AC", "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "10C", "JC", "QC", "KC",
    "AH", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "10H", "JH", "QH", "KH"
};

bool KingQueen(const vector<string>& deck) {
    int n = deck.size();
    for (int i = 0; i < n - 1; i++) {
        if ((deck[i][0] == 'K' && deck[i + 1][0] == 'Q') ||
            (deck[i][0] == 'Q' && deck[i + 1][0] == 'K')) {

            return true;
        }
        if (i != n - 2 && ((deck[i][0] == 'K' && deck[i + 2][0] == 'Q') ||
            (deck[i][0] == 'Q' && deck[i + 2][0] == 'K'))) {

            return true;
        }
    }

    return false;
}

void MonteCarloOpenMP(int n) {
    int res = 0;
    double seconds = 0.0f;

    double seconds_openMP = 0.0f;

    cout << "Shuffled " << n << " times\n" << endl;

    double start_time = omp_get_wtime();

    #pragma omp parallel for reduction(+:res) schedule(static)
    for (int i = 0; i < n; ++i) {
        vector<string> deck = org_deck;
        unsigned seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(deck.begin(), deck.end(), default_random_engine(seed));
        if (KingQueen(deck)) {
            ++res;
        }

        if (i % (n / 10) == 0) {
            #pragma omp critical
            cout << "Progress " << (i * 100 / n) << "%" << endl;
        }
    }


    double end_time = omp_get_wtime();
    printf("\nTime taken for OpenMP: %.4f seconds\n", end_time-start_time);

    cout << "Probability: " << static_cast<double>(res) * 100.0 / n << "%" << endl;
    cout << "=================================" << endl;
}

int main() {
    omp_set_num_threads(4);

    for (int i = 1; i <= 6; ++i) {
        MonteCarloOpenMP(pow(10, i));
    }

    return 0;
}
 

如您所见，使用的时间不会减少，而是比不使用 OpenMP 的时间更多。

Answer 1

您在每次迭代中重新初始化随机生成器。这不太可能给出好的随机序列。相反，让你的生成器成为线程私有的。

// global
static random_device rd; 
static mt19937 rng;
#pragma omp threadprivate(rd) 
#pragma omp threadprivate(rng)

// in main, do a parallel seed:
#pragma omp parallel
rng = mt19937(rd());

// anywhere in your program use rng in parallel:
#pragma omp parallel
 {
    stringstream res;
    uniform_int_distribution<int> percent(1, 100);
    res << "Thread " << omp_get_thread_num() << ": " << percent(rng) << "\n";
    cout << res.str();
  }