OpenMPを使用してコードを実行する速度が遅くなるのはなぜですか？

Question

OMPを使用してモンテカルロ法を並列化する次のコードがあります。私の質問は、シリアルバージョンのコード（monte_carlo_serial）がパラレルバージョン（monte_carlo_parallel）よりもずっと高速に動作する理由です。私は32コアのマシン上でコードを実行しており、次の結果をコンソールに出力します：

-bash-4.1 $ gcc -fopenmp hello.c;
-bash-4.1 $ ./a.out
パイ（シリアル）：3.140856
時間取ら0秒50ミリ秒
パイ（パラレル）：3.3
時間撮影した127秒990ミリ秒

#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

変数

count 

は、スポーンされたすべてのスレッドで共有されます。それらのそれぞれは、それを増やすためにカウントをロックする必要があります。さらに、スレッドが別々のCPU上で実行されている場合（そうでない場合は勝利できません）、あるコアから別のコアにカウント値を送り戻すコストが発生します。

これは、誤った共有の教科書の例です。あなたのシリアルバージョンでカウントにアクセスすると、レジスタに格納され、増分するには1サイクルかかるでしょう。並列バージョンでは、通常はキャッシュには存在しません。他のコアにキャッシュラインを無効にし、フェッチして（L3は最高で66サイクルかかる）、それをインクリメントして保存し直す必要があります。カウントが1つのCPUコアから別のCPUコアに移行するたびに、最小コストが125サイクルになります。これは1よりもはるかに悪いものです。スレッドはカウントに依存するため、並列実行できません。

各スレッドが独自のカウントを持つようにコードを修正してから、最後のすべてのスレッドのcountの値を合計し、高速化を確認してください。