next up previous index
Next: The Code Up: Basic MPI Previous: Exercises

   
The Random Pie

In this section we are going to evaluate $\pi$, yet again, using a Monte Carlo method. Monte Carlo methods are quite popular because they are usually rather easy to code and to parallelize, but they can be also inaccurate and slow.

The way we're going to employ Monte Carlo in this code is as follows. The area of a circle is given by $\mathcal{A}_\circ = \pi r^2$, where r is the radius of the circle. For r = 1 we have that $\mathcal{A}_\circ = \pi$. The area of a square this circle is fitted in is $\mathcal{A}_\Box = 2\times2 = 4$. So the ratio of $\mathcal{A}_\circ/\mathcal{A}_\Box = \pi/4$.

Now imagine that you throw grains of sand, at random, at the square. We expect that $\pi /4$ of all grains will end up within the circle, the remaining grains landing outside.


  
Figure: Dividing the number of grains that have landed within the circle by the total number of sand grains thrown at the square should give us $\pi /4$.
\begin{figure}
\begin{center}
\begin{picture}
(4,4)(0,0)
\put(0,0){\framebox (4,4){}}
\put(2,2){\circle{4}}
\end{picture}\end{center}\end{figure}

Within this program we are going to have worker processes throw sand grains at random at the square and check if the grains have landed within or without the circle. Every now and then the processes will collect the results from each other in order to improve their estimate of $\pi$. We are going to have one process, set aside, whose only job will be to generate random numbers. The process will send the numbers to the workers on request. This guarantees that each worker is going to get different random numbers. In our other programs we dealt with this problem by using the process rank number to seed the random number generator differently. So this is a new strategy.

The process that is set aside will be excluded from the communicator, which the worker processes will use to exchange their estimates of $\pi$ with each other. So we are going to learn on this occasion how to construct such a communicator too.

The computation goes on until the required accuracy is reached, and this accuracy is passed through the command line, the parameter is called $\epsilon$, or until the maximum number of sand grains has been thrown on the square.



 
next up previous index
Next: The Code Up: Basic MPI Previous: Exercises
Zdzislaw Meglicki
2004-04-29