實現並行算法來計算pi

我想在OpenMP中使用線程實現以下代碼的並行版本，有沒有更好的方法來做到這一點？實現並行算法來計算pi

/* Program to compute Pi using Monte Carlo methods */ 

#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
#include <string.h> 
#include <time.h> 
#define SEED 35791246 

int main(int argc, char* argv) 
{ 
    int niter=0; 
    double x,y; 
    int i,count=0; /* # of points in the 1st quadrant of unit circle */ 
    double z; 
    double pi; 
    clock_t end_time, start_time; 


    printf("Enter the number of iterations used to estimate pi: "); 
    scanf("%d",&niter); 

    start_time = clock(); 
    /* initialize random numbers */ 
    srand(SEED); 
    count=0; 

#pragma omp parallel for 
     for (i=0; i<niter; i++) { 
     x = (double)rand()/RAND_MAX; 
     y = (double)rand()/RAND_MAX; 
     z = x*x+y*y; 
     if (z<=1) count++; 
    } 
#pragma omp task 
    pi=(double)count/niter*4; 
#pragma omp barrier 

    end_time = clock(); 

    printf("# of trials= %d , estimate of pi is %g, time= %f \n",niter,pi, difftime(end_time, start_time)); 

    return 0; 
}

來源

2010-03-02 kayn

可以通過修正一些OpenMP錯誤來改善它。首先，由於您在所有並行線程中總結（副本）count，因此需要在並行段末尾應用縮減操作符，將所有這些操作合併爲一個單一值。此外，變量i,x,y和z需要每個並行線程都有單獨的實例 - 您不希望線程使用同一個線程！要指定所有這一切，你#pragma指令在循環的頂部應該是：

#pragma omp parallel for private(i, x, y, z) reduction(+:count)

而且，該範圍是for循環，所以你不需要做別的事情;循環結束後會自動進行線程同步。（並且您需要同步才能讓count包含所有主題的所有增量！）特別是，您的task和barrier編譯指示是沒有意義的，因爲此時您只回到一個線程 - 此外，沒有任何意義將單一計算放在並行任務中。

在這些情況下，gabe提出了關於系統隨機數發生器的可能緩慢和/或隨機性差的問題。您可能想要調查系統中的細節，並在每個線程中給它一個新的隨機種子，或者根據您找到的內容使用不同的隨機數生成器。

除此之外，它看起來相當合理。除此之外，您可以對該算法做其他事情，因爲它很簡單並且可以並行化。

來源

2010-03-02 10:12:08

這一切對我來說都是有意義的。現在我仍然在學習如何使用OpenMP進行並行計算。根據Brooks的建議，我確實在私有（i，x，y，z）減少（+：count）時指定了#pragma omp parallel循環的頂部並再次運行程序。與串行算法相比，它仍然花費了更長的時間來進行計算。這使我想到rand函數的gabe引發的問題，它不是線程友好的。如何分配新的隨機種子在每個線程或在我的代碼中使用不同的隨機數發生器來提高算法的性能？ – kayn 2010-03-02 11:04:23

rand功能不是一個好主意在這裏使用。要麼它不是線程安全的，你將有線程獲得重複值（不是非常隨機），或者它將有一個鎖，MP版本將比單線程版本慢。

我會建議找到另一個隨機數發生器，可以從多個線程同時使用。

來源

2010-03-02 10:09:56 Gabe

這並不完全正確 - 正如http://www.thinkingparallel.com/2006/08/21/scoped-locking-vs-critical-in-openmp-a-personal-shootout/中的評論所述（請參閱第二條評論），OpenMP需要使用基本語言提供的rand（）等函數以確保線程安全。但是，對於重複值或內部鎖定緩慢的情況，您可能是正確的，因爲這些並不是「線程安全」問題，正如通常定義的那樣。關於選擇更好的選項的建議是明智的。 – 2010-03-02 10:16:23

'rand'需要保留一個可重複的內部值。這是非常設計，並使其固有鎖定或線程不安全。另外在傳統的UNIX和BSD系統中，它使用了一個非常糟糕的僞隨機數生成器。從良好的PRNG或RNG中讀取文件I/O的內核鎖至少再次限制速度。這種情況下重新發明輪子或使用第三方代碼實際上可能比使用標準庫函數更好。 – jbcreix 2010-03-03 15:04:33

實現並行算法來計算pi

回答

相關問題