实现一个并行算法以计算pi

Question

我想使用OpenMP中的线程来实现下面代码的并行版本，是否有更好的方法可以实现？

/* 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;
}

- kayn

Answer 1

通过纠正一些OpenMP错误，可以改进它。首先，在所有并行线程中汇总（副本）count，需要在并行段的末尾应用归约运算符将所有线程组合成单个值。此外，变量i、x、y和z需要为每个并行线程具有独立实例——不希望线程使用相同的实例！为了指定所有这些，您在循环顶部的#pragma指令应该是：

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

此外，该for循环的作用域已经涵盖了所有内容，因此您无需进行其他操作；在循环结束后，线程将自动同步。（而您需要这种同步来获取所有线程增量的总和！）特别是，您的task和barrier指令在那一点上是没有意义的，因为此时您又回到了单个线程--而且，将单个计算放入并行任务中也没有意义。

此外，还有一个问题，即gabe提出的系统随机数生成器可能会很慢或者随机性较差。您可能需要在每个线程中调查系统的具体情况，并为其提供新的随机种子，或者根据您发现的情况使用不同的随机数生成器。

除此之外，它看起来相当合理。由于它很短且可以轻松并行化，所以对该算法的改进空间不大。

- Brooks Moses

---

现在我已经理解了一切。我仍在学习如何使用OpenMP并行计算。根据Brooks的建议，在循环顶部指定了#pragma omp parallel for private(i, x, y, z) reduction(+:count)，然后再次运行程序。与串行算法相比，它仍需要更长的时间来进行计算。这让我想到了gabe提出的rand函数不支持线程的问题。我该如何为每个线程分配一个新的随机种子或在我的代码中使用不同的随机数生成器来提高算法的性能？ - kayn

Answer 2

rand函数不适合在此处使用。它可能不是线程安全的，导致线程获取到重复值（不够随机），或者会有锁，使得多线程版本比单线程版本慢。

我建议找到另一个可以同时从多个线程中使用的随机数生成器。

- Gabe

---

这并不完全正确——正如在 http://www.thinkingparallel.com/2006/08/21/scoped-locking-vs-critical-in-openmp-a-personal-shootout/ 中所述的评论中（参见第二条评论），OpenMP 要求由基本语言提供的函数，如 rand()，是线程安全的。然而，您关于内部锁定导致的重复值或缓慢的观点可能是正确的，因为这些问题并不是通常定义的“线程安全”问题。选择更好选项的建议是明智的。 - Brooks Moses

“rand”需要保持可重复的内部值。这基本上是设计如此，使其固有地被锁定或线程不安全。此外，在传统的UNIX和BSD系统中，它使用非常糟糕的伪随机数生成器。从好的PRNGs或RNGs读取会再次限制速度，至少需要内核锁定文件I/O。这是一个情况，重新发明轮子或使用第三方代码实际上可能比使用标准库函数更好。 - user14554