High Performance Computing

Project 2 (Estimating Pi Using MPI)

TASK: Write a parallel program using MPI that estimates the number pi using a Monte Carlo simulation.

Instructions for ‘mpi_pi.c’

The basic idea is that we suppose we toss darts randomly at a square dart board, whose bullseye is at the origin, and whose sides are 2 feet in length each. Suppose also that there is a circle inscribed in the square dartboard. The radius of the circle is 1 foot, and its area is pi squared feet. If the points that are hit by the darts are uniformly distributed (and we always hit the square), then the number of darts that hit inside the circle should approximately satisfy the equation:

(numberInCircle / numberOfTosses) = (pi / 4)

This is called a Monte Carlo simulation, since it uses randomness (the dart tosses).

Here’s what you need to do:

1. On the LittleFe machine, log in and create a new file called ‘mpi_pi.c’.

2. Implement the Monte Carlo algorithm for approximating pi using the following psudocode:

   numberInCircle = 0;
   
   for (toss = 0; toss < numberOfTosses; toss++) {
     x = random double between -1 and 1;
     y = random double between -1 and 1;
   
     distance_squared = x^2 + y^2;
   
     if (distance_squared <= 1) numberInCircle++;
   }
   
   pi_estimate = 4 * numberInCircle / ((double) numberOfTosses);

3. Once you get the serial program working, parallelize your implementation of the pi-approximation algorithm using MPI. Process 0 should read in the total number of tosses from the command line and broadcast it to the other processes. Use MPI_Reduce() to find the global sum of the local variable numberInCircle, and have process 0 print the result. You may want to use long long ints for the number of hits in the circle and the number of tosses, since both may have to be very large to get a reasonable estimate of π. Experiment with different numbers of processes for -n on LittleFe.

4. Your program should take one optional parameter (from the command line) when running it: the flag -d followed by how many darts you want to throw (use 100 as a default value if the flag isn’t provided).

5. Also compute the absolute error as compared to the number pi in C, as well as time your program.

6. The following would all be possible ways to run your program, so you’ll want to make sure each of these works:

   ./mcpi
   ./mcpi -d 1000
   ./mcpi -d 2500000
   ./mcpi -d 400

   Output your result in a format just like this:

   Throws: 100
   Approximation: 3.1415132123
   Absolute error is 0.000079
   
   The program finished running in 0.03 seconds.

Documentation

You should also document/comment your code. At the top of your source code file, give a description of the program, the author of the code, and the date the code was written. Also place comments throughout your program (you can decide when you have enough comments, but they should adequately describe your code).

Submit

Save your program as mpi_pi.c and submit it to Moodle by the due date at 11:59PM.