Implementation of a parallel algorithm for computing pi

Question

I would like to implement a parallel version of the code below using threads in OpenMP, is there a better way to do this?

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

This can be improved by fixing some OpenMP errors. First, since you are summing (copies) of count in all parallel threads, you need to apply the reduction operator at the end of the parallel segment to combine all of them back into one value. In addition, the variables i , x , y and z must have separate instances for each parallel thread — you do not want the threads to use the same one! To indicate all this, your #pragma at the top of the loop should be:

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

In addition, the scope is a for loop, so you don't have to do anything; automatically there will be a synchronization of flows after an exit of a cycle. (And you need this synchronization to get count , to contain all increments from all threads!) In particular, your task and barrier pragmas are pointless, since at that moment you return to one thread - and, in addition, there is no point in setting this single computation into a parallel task.

And there is a problem associated with the probability of slowness and / or bad randomness of the random number generator of the system in these cases. You will probably want to study the features of this in your system and give it a new random seed in each thread, or use a different random number generator, depending on what you find.

In addition, he looks pretty reasonable. You can not do much more with this algorithm, since it is short and trivially parallelizable.

Answer 2

The rand function is not recommended for use here. Either it is not thread safe and you will have threads receiving duplicate values ​​(not very random), or it will have a lock and the MP version will be slower than the single thread version.

I would recommend finding another random number generator that can be used simultaneously from multiple threads.