Warum lässt OpenMP den Code langsamer laufen?

Question

Ich habe den folgenden Code, der OMP verwendet, um eine Monte-Carlo-Methode zu parallelisieren. Meine Frage ist, warum die serielle Version des Codes (monte_carlo_serial) viel schneller läuft als die parallele Version (monte_carlo_parallel). Ich führe den Code auf einem Rechner mit 32 Kernen aus und bekomme folgendes Ergebnis auf die Konsole:

-bash-4.1 $ gcc -fopenmp hello.c;
-bash-4.1 $ ./a.out
Pi (Serial): 3,140856
Zeit genommen 0 Sekunden 50 Millisekunden
Pi (Parallel): 3,3
Zeit genommen 127 Sekunden 990 Millisekunden

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <omp.h> 
#include <time.h> 

int niter = 1000000;   //number of iterations per FOR loop 

int monte_carlo_parallel() { 
    double x,y;      //x,y value for the random coordinate 
    int i;       //loop counter 
    int count=0;    //Count holds all the number of how many good coordinates 
    double z;      //Used to check if x^2+y^2<=1 
    double pi;      //holds approx value of pi 
    int numthreads = 32; 

#pragma omp parallel firstprivate(x, y, z, i) reduction(+:count) num_threads(numthreads) 
    { 
    srand48((int)time(NULL)^omp_get_thread_num()); //Give random() a seed value 
    for (i=0; i<niter; ++i)     //main loop 
     { 
     x = (double)drand48();    //gets a random x coordinate 
     y = (double)drand48();    //gets a random y coordinate 
     z = ((x*x)+(y*y));    //Checks to see if number is inside unit circle 
     if (z<=1) 
      { 
      ++count;    //if it is, consider it a valid random point 
      } 
     } 
    } 

    pi = ((double)count/(double)(niter*numthreads))*4.0; 
    printf("Pi (Parallel): %f\n", pi); 
    return 0; 
} 

int monte_carlo_serial(){ 
    double x,y;      //x,y value for the random coordinate 
    int i;       //loop counter 
    int count=0;    //Count holds all the number of how many good coordinates 
    double z;      //Used to check if x^2+y^2<=1 
    double pi;      //holds approx value of pi 

    srand48((int)time(NULL)^omp_get_thread_num()); //Give random() a seed value 

    for (i=0; i<niter; ++i)     //main loop 
    { 
     x = (double)drand48();    //gets a random x coordinate 
     y = (double)drand48();    //gets a random y coordinate 
     z = ((x*x)+(y*y));    //Checks to see if number is inside unit circle 
     if (z<=1) 
     { 
      ++count;    //if it is, consider it a valid random point 
     } 
    } 

    pi = ((double)count/(double)(niter))*4.0; 
    printf("Pi (Serial): %f\n", pi); 

    return 0; 
} 


void main(){ 
    clock_t start = clock(), diff; 

    monte_carlo_serial(); 

    diff = clock() - start; 
    int msec = diff * 1000/CLOCKS_PER_SEC; 
    printf("Time taken %d seconds %d milliseconds \n", msec/1000, msec%1000); 



    start = clock(), diff; 

    monte_carlo_parallel(); 

    diff = clock() - start; 
    msec = diff * 1000/CLOCKS_PER_SEC; 
    printf("Time taken %d seconds %d milliseconds \n", msec/1000, msec%1000); 

} 

Answer 1

Die Variable

count 

ist in allen Ihren gelaicht Threads geteilt. Jeder von ihnen muss die Zählung sperren, um sie zu erhöhen. Außerdem, wenn die Threads auf separaten CPUs laufen (und es gibt keinen möglichen Gewinn, wenn sie nicht sind), haben Sie die Kosten, den Wert der Zählung von einem Kern zum anderen und wieder zurück zu senden.

Dies ist ein Lehrbuch Beispiel für falsche Freigabe. Wenn Sie auf die Zählung in Ihrer seriellen Version zugreifen, befindet sie sich in einem Register und kostet 1 Zyklus zum Inkrementieren. In der parallelen Version ist es normalerweise nicht im Cache, Sie müssen den anderen Kernen sagen, dass sie diese Cache-Zeile ungültig machen, sie holen (L3 wird höchstens 66 Zyklen benötigen), inkrementieren und zurückspeichern. Jedes Mal, wenn die Anzahl von einem CPU-Kern zu einem anderen wechselt, haben Sie einen minimalen Kostenaufwand von ca. 125 Zyklen, der viel schlechter ist als 1. Die Threads können niemals parallel laufen, weil sie von der Anzahl abhängen.

Versuchen Sie, Ihren Code zu ändern, so dass jeder Thread seine eigene Zählung hat, dann summieren Sie alle Werte der Anzahl von allen Threads am Ende und Sie/möglicherweise/sehen eine Beschleunigung.