Реализация параллельного алгоритма для вычисления числа пи

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

Answer 1

Это можно улучшить, исправив некоторые ошибки OpenMP. Во-первых, поскольку вы суммируете (копии) count во всех параллельных потоках, вам необходимо применить оператор сокращения в конце параллельного сегмента, чтобы объединить все эти значения обратно в одно значение. Кроме того, переменные i, x, y и z должны иметь отдельные экземпляры для каждого параллельного потока - вам не нужно, чтобы потоки использовали один и тот же! Чтобы указать все это, ваша директива #pragma в верхней части цикла должна быть:

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

Кроме того, область действия этого цикла - for, поэтому вам больше ничего не нужно делать; после выхода из цикла автоматически произойдет синхронизация потоков. (И эта синхронизация необходима, чтобы count содержал все приращения из всех потоков!) В частности, ваши прагмы task и barrier не имеют смысла, так как в этот момент вы вернулись только к одному потоку - кроме того, нет смысла помещать эти вычисления в параллельное задание.

И еще одна проблема, которая возникла в связи с вероятной медлительностью и / или плохой случайностью системного генератора случайных чисел в этих случаях. Вы, вероятно, захотите изучить особенности этого в вашей системе и дать ему новое случайное начальное число в каждом потоке или использовать другой генератор случайных чисел в зависимости от того, что вы найдете.

Кроме того, это выглядит довольно разумно. Ничего другого вы не можете сделать с этим алгоритмом, поскольку он короткий и тривиально распараллеливаемый.

Answer 2

Функция rand не очень хорошая идея для использования здесь. Либо это не потокобезопасно, и у вас будут потоки, получающие повторяющиеся значения (не очень случайные), либо у него будет блокировка, и версия MP будет медленнее, чем однопоточная версия.

Я бы порекомендовал найти другой генератор случайных чисел, который можно использовать одновременно из нескольких потоков.