Example: Monte-carlo Approximation of Pi

Overview

  • Tutorial: 20 min

    Objectives:

    1. Learn how to use MPI to approximate Pi using the Monte Carlo method.

Monte Carlo Method: The Monte Carlo method is a statistical technique used to estimate the value of an unknown quantity using random sampling. In this example, we generate \(N\) random sampling points within a square, and count the number \(h\) of samples that fall in the unit circle. Then the approximation of \(\pi\) is given by: \(4h/N\).

../../_images/Monte-Carlo01.jpg

A serial implementation of the Monte Carlo method to approximate Pi may look like the following:

1seed = 1; // seed for random number generator
2for (i=0; i<N; i++) {
3    x = (double)rand_r(&seed)/(double)RAND_MAX; // RAND_MAX to normalise
4    y = (double)rand_r(&seed)/(double)RAND_MAX;
5
6    if (x*x + y*y <= 1.0) h++;
7}

Parallel Monte Carlo Pi Approximation: To parallelise the Monte Carlo method, we can divide the work among multiple processors. Each processor generates a subset of the total random samples and counts the number of samples that fall within the unit circle. The final approximation of Pi is obtained by summing the counts from all processors and dividing by the total number of samples.

Our first MPI code will look like this:

 1#include<mpi.h>
 2
 3int rank, size;
 4int count=0, count_tot=0;
 5MPI_Comm_rank(MPI_COMM_WORLD, &rank); // get the rank of the process
 6MPI_Comm_size(MPI_COMM_WORLD, &size); // get the total number of processes
 7
 8int start = rank * N /size; // the start index of the samples for this process
 9int end = (rank+1) * N /size; // the end index of the samples for this process
10
11for (i=start; i<end; i++) {
12    x = (double)rand_r(&seed)/(double)RAND_MAX;
13    y = (double)rand_r(&seed)/(double)RAND_MAX;
14
15    if (x*x + y*y <= 1.0) count++;
16
17    // sum the counts from all processes
18    MPI_Reduce(*count, &count_tot, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
19}

Note

The user organises the copies of data for each parallel process.

In