HPC - Monte Carlo estimation of the area of the union of circles

File mpi-circles.c contains a serial implementation of a Monte Carlo algorithm that estimates the area of ​​the union of \(N\) circles. Let cx[i], cy[i], and r[i] be the coordinates of the center of circle \(i\) and its radius. Assume that all circles are entirely contained within the bounding square with opposites corners \((0, 0)\) and \((1000, 1000)\). Since circles can be in any position, they may overlap in in whole or in part; therefore it is not easy to determine the area of their union.

We implement a Monte Carlo algorithm to estimate the area; the idea is similar to the one we used to estimate the value of \(\pi\) by generating random points:

• generate \(K\) randomly distributed points inside the bounding square \((0, 0)\), \((1000, 1000)\). Let \(C\) be the number of points that fall within at least one circle.

• The area \(A\) of the union of the circles is estimated as the product of the area of the bounding square and the fraction of points that fall within at least one circle: \(A = 1000000 \times C/S\);

Figure 1 illustrates the idea.

The file mpi-circles.c containing a serial program where process 0 performs the whole computation. The purpose of this exercise is to distribute the computation among all MPI processes. Assume that only process 0 can read the input file; this means that only process 0 knows the number \(N\) of circles and their coordinates. Should this information be needed by other processes, some explicit communication must be performed. The program must work correctly for any value of \(N\) and \(K\).

Hint. You might be tempted to to partition the circles among the MPI processes, in such a way that each process handles \(N/P\) circles. However, this solution would not work (or better, would be very inefficient): why?.

The correct approach is to let each process \(p\) generate \(K/P\) points and test each point with all the circles, and compute the number of points \(C_p\) that fall inside at least one circle. Then, the master computes the sum \(C = \sum_{p=0}^{P-1} C_p\) using a reduction, and estimates the area as above. To do this, each process must receive a copy of the arrays cx[], cy[] and r[] using three broadcast operations.

To compile:

    mpicc -std = c99 -Wall -Wpedantic mpi-circles.c -o mpi-circles

To execute:

    mpirun -n P ./mpi-circles N input_file_name

Example:

    mpirun -n 4 ./mpi-circles 10000 circles-1000.in

Files

• mpi-circles.c
• circles-gen.c (to generate random input data)
• circles-1000.in
• circles-10000.in