实现并行算法来计算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

回答

相关问题