Spezielle Anweisungen zum Zuordnen von Arrays mit OpenMP?

Question

Meine einfache for Schleife für Parallelisierung in OpenMP ist

vector<double> xs; 
    vector<double> ys; 
    xs.resize(N); 
    ys.resize(N); 
    if(rank0) printf("Assigning points ...\n"); 
#pragma omp parallel for 
    for(long i = 0; i < N; i++) { 
     xs[i] = ((double)rand()/(double)RAND_MAX); 
     ys[i] = ((double)rand()/(double)RAND_MAX); 
    } 

Aber das dauert wesentlich länger, als ich die #pragma omp parallel for als enthalten, wenn ich dies nicht tun. Dies wird oft beobachtet, wenn ich keine korrekte reduction oder etwas ähnliches verwende, also frage ich mich, ob es noch etwas gibt, was ich für diese #pragma tun muss.

Benötigt diese for Schleife noch etwas in der #pragma?

Bitte beachten Sie, dass diese Frage in direktem Zusammenhang mit der Verwendung von rand() steht.

Answer 1

Meine unmittelbare Vermutung wäre, dass das Problem von der Tatsache herrührt, dass rand() einen einzelnen Startwert verwendet, der jedes Mal aktualisiert wird, wenn Sie rand() aufrufen. Dies bedeutet, dass, obwohl es keinen Konflikt zwischen den Arrays gibt, an die Sie schreiben, jeder Aufruf von rand() wahrscheinlich die Synchronisierung zwischen den Threads erzwingt.

Es gibt verschiedene Möglichkeiten, dies zu umgehen. Ein offensichtlicher wäre die neue Zufallszahl-Erzeugungs Klassen in C++ 11 zu nutzen, mit einem separaten Zufallszahlengenerator-Objekt für jeden Thread, so etwas wie diese:

std::mt19937_64 a; 
    std::mt19937_64 b; 

    std::uniform_real_distribution<double> da; 
    std::uniform_real_distribution<double> db; 

#pragma omp parallel for private(a, b) 
    for (long i = 0; i < N; i++) { 
     xs[i] = da(a); 
     ys[i] = db(b); 
    } 

zumindest in einem Schnelltest auf meinem System, das läuft in etwa 4 Sekunden single-threaded, und etwa 1 Sekunde mit OpenMP aktiviert (und das ist auf einem 4-Core-Prozessor, so dass fast perfekt Skalierung ist).

Beachten Sie, wenn Sie auf einem 32-Bit-System sind (oder zumindest einen Compiler verwenden, die 32-Bit-Code erzeugt) dies wahrscheinlich wesentlich schneller sein wird, wenn Sie mt19937 statt mt19937_64 verwenden. Dies wird nur 32 Bits der Zufälligkeit für jede generierte Zahl haben, aber das ist wahrscheinlich so viel wie rand() produziert sowieso. Auf einem 64-Bit-System/Compiler erwarten Sie, dass mt19937_64 genauso schnell läuft und eine wesentlich größere Zufälligkeit erzeugt.

Eine weitere kleine Anmerkung: hier habe ich nur die Standard-Seed (die 1 ist) für jeden Generator verwendet. Vielleicht möchten Sie Samen nach dem Zufallsprinzip erzeugen, z. B. von std::random_device, und den Generator jedes Threads separat säen, damit Sie keine Doppelungen von Zahlen zwischen den Threads erhalten.

Answer 2

Es stellt sich heraus, dass rand nicht Thread sicher ist. Eine einfache Alternative ist drand48_r für das, was ich versuchte zu verwenden. Ändern meiner Schleife wie folgt zeigt die genaue Beschleunigung, die ich erwartet hatte:

#pragma omp parallel for private(ii, rBuf, trand) shared(xs,ys) 
    for(ii = 0; ii < N; ii++) { 
     drand48_r(&rBuf, &trand); 
     xs[ii] = trand; 
     drand48_r(&rBuf, &trand); 
     ys[ii] = trand; 
    }